On the minimization of (complete) ordered binary decision diagrams

DOI10.1007/S00224-015-9657-XMaRDI QIDQ503467zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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