Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams

DOI10.1007/S002240000128zbMATH Open0934.68048OpenAlexW1998134727MaRDI QIDQ1293553FDOQ1293553

Beate Bollig, Ingo Wegener

Publication date: 28 June 1999

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

Full work available at URL: https://doi.org/10.1007/s002240000128

Recommendations

• On the complexity of constructing optimal ordered binary decision diagrams
• The Boolean hierarchy of NP-partitions
• scientific article; zbMATH DE number 1500515
• On the size of binary decision diagrams representing Boolean functions
• Complexity Based on Partitioning of Boolean Circuits and their Relation to Multivalued Circuits
• A characterization of binary decision diagrams
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• Integer multiplication and the complexity of binary decision diagrams
• On the minimization of (complete) ordered binary decision diagrams

zbMATH Keywords

ordered binary decision diagrams

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (11)

• On the relative succinctness of sentential decision diagrams
• On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
• Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
• Functions that have read-once branching programs of quadratic size are not necessarily testable
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• A hierarchy result for read-once branching programs with restricted parity nondeterminism
• An improved hierarchy result for partitioned BDDs
• Connecting knowledge compilation classes and width parameters
• Knowledge compilation meets database theory: compiling queries to decision diagrams
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
• BDDs -- design, analysis, complexity, and applications.

This page was built for publication: Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams

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