An improved hierarchy result for partitioned BDDs

DOI10.1007/S002240010005zbMATH Open0961.68056OpenAlexW2057257783MaRDI QIDQ1587372FDOQ1587372

Authors: Martin Sauerhoff 

Publication date: 7 December 2000

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

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

Recommendations

• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• On the hierarchy of nondeterministic branching k-programs
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• On the size of binary decision diagrams representing Boolean functions
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs

zbMATH Keywords

complexity of Boolean functionpartitioned binary decision diagrams

Mathematics Subject Classification ID

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

Cited In (7)

• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
• Formal Methods in Computer-Aided Design
• A hierarchy result for read-once branching programs with restricted parity nondeterminism
• On domain-partitioning induction criteria: worst-case bounds for the worst-case based
• Width hierarchy for \(k\)-OBDD of small width

This page was built for publication: An improved hierarchy result for partitioned BDDs

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