Language Recognition Power and Succinctness of Affine Automata
From MaRDI portal
Publication:2819147
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
state complexityquantum automataprobabilistic automatabounded-erroraffine automataone-sided errorstochastic language
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
