Language Recognition Power and Succinctness of Affine Automata

DOI10.1007/978-3-319-41312-9_10zbMath1476.68139arXiv1602.05432OpenAlexW2275579475MaRDI QIDQ2819147

Marcos Villagra, Abuzer Yakaryılmaz

Publication date: 28 September 2016

Published in: Unconventional Computation and Natural Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.05432

zbMATH Keywords

state complexityquantum automataprobabilistic automatabounded-erroraffine automataone-sided errorstochastic language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Related Items

Affine automata verifiers, Language recognition power and succinctness of affine automata, Computational limitations of affine automata and generalized affine automata, Exact Affine Counter Automata, Error-Free Affine, Unitary, and Probabilistic OBDDs, Unnamed Item, On the Computational Power of Affine Automata, Affine Computation and Affine Automaton, Language Recognition Power and Succinctness of Affine Automata, Looking for Pairs that Hard to Separate: A Quantum Approach, Improved constructions for succinct affine automata

Cites Work

• Superiority of exact quantum automata for promise problems
• Unbounded-error quantum computation with small space bounds
• Characterizations of one-way general quantum finite automata
• Quantum automata and quantum grammars
• Unary probabilistic and quantum automata on promise problems
• Language Recognition Power and Succinctness of Affine Automata
• Looking for Pairs that Hard to Separate: A Quantum Approach
• Quantum Finite Automata: A Modern Introduction
• Potential of Quantum Finite Automata with Exact Acceptance
• Implications of Quantum Automata for Contextuality
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• Word-functions of stochastic and pseudo stochastic automata
• Space-Efficient Deterministic Simulation of Probabilistic Automata
• Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs
• Probabilistic automata
• Affine Computation and Affine Automaton
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item