An improved hierarchy result for partitioned BDDs

DOI10.1007/S002240010005MaRDI QIDQ1587372zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

complexity of Boolean functionpartitioned binary decision diagrams

Mathematics Subject Classification ID

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

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

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)