On the computational power of affine automata

DOI10.1007/978-3-319-53733-7_30zbMATH Open1485.68096arXiv1612.01870OpenAlexW2584948573MaRDI QIDQ5739014FDOQ5739014

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)

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.

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

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

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)

Cites Work

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

Cited In (12)

• Exact affine counter automata
• Exact Affine Counter Automata
• Affine computation and affine automaton
• Title not available (Why is that?)
• 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
• Language Recognition Power and Succinctness of Affine Automata

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)