Languages recognized by nondeterministic quantum finite automata

MaRDI QIDQ3171611zbMATH OpenFDO

Authors Abuzer Yakaryılmaz, A. C. Cem Say

Publication date 5 October 2011

zbMATH Keywords

probabilistic automatanondeterministic quantum finite automataone-sided unbounded errorsublogarithmic space complexitytwo-sided unbounded error

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Error bounds for numerical methods for ordinary differential equations (65L70) Cellular automata (computational aspects) (68Q80)

Recommendations

• Implementation and Application of Automata
• scientific article; zbMATH DE number 1688355
• Two-way finite automata with quantum and classical states.
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• The complexity of probabilistic versus quantum finite automata

Cited in

(27)

• Improved constructions for succinct affine automata
• Language recognition power and succinctness of affine automata
• State succinctness of two-way finite automata with quantum and classical states
• STACS 2004
• The complexity of probabilistic versus quantum finite automata
• Affine computation and affine automaton
• Computational limitations of affine automata and generalized affine automata
• scientific article; zbMATH DE number 1688355 (Why is no real title available?)
• Quantum finite automata: a modern introduction
• More on quantum, stochastic, and pseudo stochastic languages with few states
• Nondeterministic unitary OBDDs
• scientific article; zbMATH DE number 1405684 (Why is no real title available?)
• Looking for Pairs that Hard to Separate: A Quantum Approach
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Exponentially more concise quantum recognition of non-RMM regular languages
• Affine automata verifiers
• Implementation and Application of Automata
• Quantum alternation
• scientific article; zbMATH DE number 7104930 (Why is no real title available?)
• Language Recognition Power and Succinctness of Affine Automata
• scientific article; zbMATH DE number 35744 (Why is no real title available?)
• Uncountable classical and quantum complexity classes
• Unbounded-error quantum computation with small space bounds
• scientific article; zbMATH DE number 6533717 (Why is no real title available?)
• On a conjecture by Christian Choffrut
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• Deterministic construction of QFAs based on the quantum fingerprinting technique

This page was built for publication: Languages recognized by nondeterministic quantum finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3171611)