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 (11)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Language Recognition Power and Succinctness of Affine Automata