On the minimization of (complete) ordered binary decision diagrams

DOI10.1007/S00224-015-9657-XzbMATH Open1401.68051OpenAlexW2186363574MaRDI QIDQ503467FDOQ503467

Authors: Beate Bollig 

Publication date: 12 January 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-015-9657-x

Recommendations

• On the Width of Ordered Binary Decision Diagrams
• The complexity of minimizing and learning OBDDs and FBDDs
• On the Complexity of Some Ordering Problems
• Improving the variable ordering of OBDDs is NP-complete
• On the complexity of constructing optimal ordered binary decision diagrams

zbMATH Keywords

complexity theoryNP-completenessordered binary decision diagramslayout problemsnonuniform finite automata

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Graph-Based Algorithms for Boolean Function Manipulation
• Branching Programs and Binary Decision Diagrams
• Symbolic topological sorting with OBDDs
• On the Complexity of Some Ordering Problems
• SOFSEM 2006: Theory and Practice of Computer Science
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• Improving the variable ordering of OBDDs is NP-complete
• Testing Membership in Languages that Have Small Width Branching Programs
• The nonapproximability of OBDD minimization
• Title not available (Why is that?)
• Exact OBDD bounds for some fundamental functions
• On the Width of Ordered Binary Decision Diagrams
• Lower Bounds for Testing Computability by Small Width OBDDs
• On testing computability by small width OBDDs
• The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions
• Testing computability by width-two OBDDs
• On the size of (generalized) OBDDs for threshold functions

Cited In (18)

• A reducibility concept for problems defined in terms of ordered binary decision diagrams
• On the complexity of constructing optimal ordered binary decision diagrams
• The complexity of minimizing and learning OBDDs and FBDDs
• Hardness of indentifying the minimum ordered binary decision diagram
• Optimization Bounds from Binary Decision Diagrams
• Optimal ordered binary decision diagrams for read-once formulas
• Improving the variable ordering of OBDDs is NP-complete
• On the Width of Ordered Binary Decision Diagrams
• Second-order finite automata
• Ordered binary decision diagrams and minimal trellises
• Minimization problems for parity OBDDs
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• Chain reduction for binary and zero-suppressed decision diagrams
• The nonapproximability of OBDD minimization
• Title not available (Why is that?)
• Minimization of Word-Level Decision Diagrams
• Second-Order Finite Automata
• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams

This page was built for publication: On the minimization of (complete) ordered binary decision diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q503467)