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

DOI10.1016/j.ipl.2005.11.011zbMath1187.68247OpenAlexW1964040754MaRDI 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 complexitytheory of computationbranching programsparityuniversalexistentialordered binary decision diagrams with repeated tests

Mathematics Subject Classification ID

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

Related Items (3)

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 ⋮ Classical and Quantum Computations with Restricted Memory

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

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