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

affine automataLas-Vegas algorithmsOBDDsprobabilistic computationquantum computationstate complexityzero-error

Mathematics Subject Classification ID

Data structures (68P05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Formal languages and automata (68Q45)

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

• 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
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 2102760 (Why is no real title available?)
• 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 and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test
• Lower Bounds for Las Vegas Automata by Information Theory
• 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

(5)

• Nondeterministic unitary OBDDs
• Quantum algorithm for dynamic programming approach for DAGs and applications
• Deterministic construction of QFAs based on the quantum fingerprinting technique
• Real-valued affine automata compute beyond Turing machines
• 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)