On the computational power of affine automata

DOI10.1007/978-3-319-53733-7_30MaRDI QIDQ5739014zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: We investigate the computational power of affine automata (AfAs) introduced in [4]. In particular, we present a simpler proof for how to change the cutpoint for any affine language and a method how to reduce error in bounded error case. Moreover, we address to the question of [4] by showing that any affine language can be recognized by an AfA with certain limitation on the entries of affine states and transition matrices. Lastly, we present the first languages shown to be not recognized by AfAs with bounded-error.

Recommendations

• Affine computation and affine automaton
• Language Recognition Power and Succinctness of Affine Automata
• Exact Affine Counter Automata
• Exact affine counter automata
• Affine Parikh automata

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Affine computation and affine automaton
• Algebraic results on quantum automata
• Characterizations of one-way general quantum finite automata
• Generalized Automata and Stochastic Languages
• Language Recognition Power and Succinctness of Affine Automata
• Looking for Pairs that Hard to Separate: A Quantum Approach
• On nonstochastic languages and homomorphic images of stochastic languages
• Probabilistic automata
• Superiority of exact quantum automata for promise problems
• Topological automata

Cited in

(12)

• Language Recognition Power and Succinctness of Affine Automata
• Exact affine counter automata
• Exact Affine Counter Automata
• Affine computation and affine automaton
• scientific article; zbMATH DE number 3911710 (Why is no real title available?)
• Error-Free Affine, Unitary, and Probabilistic OBDDs
• Language recognition power and succinctness of affine automata
• Computational limitations of affine automata and generalized affine automata
• Gaining Power by Input Operations: Finite Automata and Beyond
• On the power of alternation in automata theory
• Improved constructions for succinct affine automata
• Affine automata verifiers

This page was built for publication: On the computational power of affine automata

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