On the Computational Power of Affine Automata

DOI10.1007/978-3-319-53733-7_30zbMath1485.68096arXiv1612.01870OpenAlexW2584948573MaRDI QIDQ5739014

Etienne Moutot, Abuzer Yakaryılmaz, Mika Hirvensalo

Publication date: 1 June 2017

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

compact setserror reductionbounded erroraffine automatacutpoint languagesnonclassical models of automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Other nonclassical models of computation (68Q09)

Related Items (6)

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 ⋮ Improved constructions for succinct affine automata

Cites Work

• Unnamed Item
• Unnamed Item
• Superiority of exact quantum automata for promise problems
• Characterizations of one-way general quantum finite automata
• On nonstochastic languages and homomorphic images of stochastic languages
• Algebraic results on quantum automata
• Topological automata
• Language Recognition Power and Succinctness of Affine Automata
• Looking for Pairs that Hard to Separate: A Quantum Approach
• Probabilistic automata
• Generalized Automata and Stochastic Languages
• Affine Computation and Affine Automaton

This page was built for publication: On the Computational Power of Affine Automata