On the minimization of (complete) ordered binary decision diagrams

DOI10.1007/s00224-015-9657-xzbMath1401.68051OpenAlexW2186363574MaRDI QIDQ503467

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

zbMATH Keywords

NP-completenessordered binary decision diagramslayout problemscomplexity theorynonuniform finite automata

Mathematics Subject Classification ID

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

Related Items

Second-Order Finite Automata ⋮ Second-order finite automata

Cites Work

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