Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams

DOI10.1007/s002240000128zbMath0934.68048OpenAlexW1998134727MaRDI QIDQ1293553

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)

Related Items

Knowledge compilation meets database theory: compiling queries to decision diagrams ⋮ BDDs -- design, analysis, complexity, and applications. ⋮ Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication ⋮ On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision ⋮ Functions that have read-once branching programs of quadratic size are not necessarily testable ⋮ On the relative succinctness of sentential decision diagrams ⋮ Connecting knowledge compilation classes and width parameters ⋮ A hierarchy result for read-once branching programs with restricted parity nondeterminism ⋮ On the descriptive and algorithmic power of parity ordered binary decision diagrams