Error-Free Affine, Unitary, and Probabilistic OBDDs

DOI10.1142/S0129054121500246MaRDI QIDQ6169903zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

quantum computationstate complexityprobabilistic computationOBDDszero-errorLas-Vegas algorithmsaffine automata

Mathematics Subject Classification ID

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)

Recommendations

• Error-free affine, unitary, and probabilistic OBDDs
• Nondeterministic unitary OBDDs
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• scientific article; zbMATH DE number 2123421

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 2102760 (Why is no real title available?)
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Affine computation and affine automaton
• Automata and quantum computing
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• Comparative complexity of quantum and classical OBDDs for total and partial functions
• Computational limitations of affine automata
• Developments in Language Theory
• Error-free affine, unitary, and probabilistic OBDDs
• Exact affine counter automata
• Language Recognition Power and Succinctness of Affine Automata
• Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
• Lower Bounds for Las Vegas Automata by Information Theory
• Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test
• Nondeterministic unitary OBDDs
• On a conjecture by Christian Choffrut
• On quantum and probabilistic communication: Las Vegas and one-way protocols
• On the computational power of affine automata
• On the computational power of probabilistic and quantum branching program
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Quantum automata and quantum grammars
• Quantum branching programs and space-bounded nonuniform quantum complexity
• Quantum finite automata: a modern introduction
• Randomization and nondeterminism are comparable for ordered read-once branching programs
• Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
• Two-way finite automata with quantum and classical states.
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs

Cited in

(4)

• Nondeterministic unitary OBDDs
• Quantum algorithm for dynamic programming approach for DAGs and applications
• Deterministic construction of QFAs based on the quantum fingerprinting technique
• Error-free affine, unitary, and probabilistic OBDDs

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)