Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams

DOI10.1007/S002240000128MaRDI QIDQ1293553zbMATHOpenAlexFDO

Authors 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

zbMATH Keywords

ordered binary decision diagrams

Mathematics Subject Classification ID

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

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

Cited in

(13)

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

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)