On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
From MaRDI portal
Publication:2361671
DOI10.1134/S1995080216060159zbMath1409.68105arXiv1612.06092MaRDI QIDQ2361671
Publication date: 30 June 2017
Published in: Lobachevskii Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1612.06092
computational complexitybinary decision diagramshierarchybranching programsOBDDdeterministic and nondeterministic models
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Related Items (5)
Reordering method and hierarchies for quantum and classical ordered binary decision diagrams ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ New size hierarchies for two way automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extension of the hierarchy for \(k\)-OBDDs of small width
- Width hierarchy for \(k\)-OBDD of small width
- Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
- Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
- The power of nondeterminism and randomness for oblivious branching programs
- An improved hierarchy result for partitioned BDDs
- Communication complexity method for measuring nondeterminism in finite automata
- On lower bounds for read-\(k\)-times branching programs
- On the computational power of probabilistic and quantum branching program
- Branching Programs and Binary Decision Diagrams
- Randomization and nondeterminism are comparable for ordered read-once branching programs
- On the hierarchy of nondeterministic branching k-programs
- Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs
This page was built for publication: On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
