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

DOI10.1016/j.ipl.2005.11.011zbMath1187.68247MaRDI QIDQ844146

Matthias Homeister, Henrik Brosenne, 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 complexity; theory of computation; branching programs; parity; universal; existential; ordered binary decision diagrams with repeated tests

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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