Error-Free Affine, Unitary, and Probabilistic OBDDs
DOI10.1142/s0129054121500246zbMath1522.68172OpenAlexW3162642540MaRDI QIDQ6169903
Kamil Khadiev, Rishat Ibrahimov, Abuzer Yakaryılmaz, Krišjānis Prūsis
Publication date: 15 August 2023
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054121500246
quantum computationstate complexityOBDDsprobabilistic computationzero-errorLas-Vegas algorithmsaffine automata
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Data structures (68P05) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Error-free affine, unitary, and probabilistic OBDDs
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- Quantum automata and quantum grammars
- A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
- Quantum branching programs and space-bounded nonuniform quantum complexity
- Two-way finite automata with quantum and classical states.
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Automata and quantum computing
- Computational limitations of affine automata
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
- Nondeterministic unitary OBDDs
- Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
- On the computational power of probabilistic and quantum branching program
- Language Recognition Power and Succinctness of Affine Automata
- Quantum Finite Automata: A Modern Introduction
- On quantum and probabilistic communication
- Lower Bounds for Las Vegas Automata by Information Theory
- Branching Programs and Binary Decision Diagrams
- Randomization and nondeterminism are comparable for ordered read-once branching programs
- On a Conjecture by Christian Choffrut
- Communication Complexity
- Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
- Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
- Developments in Language Theory
- Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs
- On the Computational Power of Affine Automata
- Affine Computation and Affine Automaton
This page was built for publication: Error-Free Affine, Unitary, and Probabilistic OBDDs
