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 (2)

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

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