Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
From MaRDI portal
Publication:844146
DOI10.1016/j.ipl.2005.11.011zbMath1187.68247MaRDI QIDQ844146
Stephan Waack, Henrik Brosenne, Matthias Homeister
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
computational complexity; theory of computation; branching programs; parity; universal; existential; ordered binary decision diagrams with repeated tests
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
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