Error-Free Affine, Unitary, and Probabilistic OBDDs
DOI10.1142/S0129054121500246zbMATH Open1522.68172OpenAlexW3162642540MaRDI QIDQ6169903FDOQ6169903
Authors: Rishat Ibrahimov, Kamil Khadiev, Krišjānis Prūsis, Abuzer Yakaryılmaz 
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
Recommendations
quantum computationstate complexityprobabilistic computationOBDDszero-errorLas-Vegas algorithmsaffine automata
Formal languages and automata (68Q45) Data structures (68P05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12)
Cites Work
- Two-way finite automata with quantum and classical states.
- Title not available (Why is that?)
- Branching Programs and Binary Decision Diagrams
- Communication Complexity
- On quantum and probabilistic communication: Las Vegas and one-way protocols
- 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
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- 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
- On the computational power of probabilistic and quantum branching program
- Exact affine counter automata
- Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Error-free affine, unitary, and probabilistic OBDDs
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- Affine computation and affine automaton
- On a conjecture by Christian Choffrut
- Quantum finite automata: a modern introduction
- Title not available (Why is that?)
- On the computational power of affine automata
- Language Recognition Power and Succinctness of Affine Automata
- Randomization and nondeterminism are comparable for ordered read-once branching programs
- Developments in Language Theory
- Automata and quantum computing
- Computational limitations of affine automata
- Nondeterministic unitary OBDDs
- Lower Bounds for Las Vegas Automata by Information Theory
Cited In (4)
This page was built for publication: Error-Free Affine, Unitary, and Probabilistic OBDDs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169903)
