Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance

DOI10.1016/J.IPL.2005.11.011MaRDI QIDQ844146zbMATH OpenOpenAlexFDO

Authors Henrik Brosenne, Matthias Homeister, Stephan Waack

Publication date 18 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2005.11.011

zbMATH Keywords

computational complexitytheory of computationparitybranching programsuniversalexistentialordered binary decision diagrams with repeated tests

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• An improved hierarchy result for partitioned BDDs
• Publication:4934627
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs

Cites work

• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 1775455 (Why is no real title available?)
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• Graph-Based Algorithms for Boolean Function Manipulation
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• Lower bounds for depth-restricted branching programs
• Mathematical Foundations of Computer Science 2003
• Meanders and their applications in lower bounds arguments
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On oblivious branching programs of linear length
• On relations between counting communication complexity classes
• Rounds in Communication Complexity Revisited
• The power of nondeterminism and randomness for oblivious branching programs

Cited in

(3)

• Classical and Quantum Computations with Restricted Memory
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
• Reordering method and hierarchies for quantum and classical ordered binary decision diagrams

This page was built for publication: Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance

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