Language recognition power and succinctness of affine automata

DOI10.1007/S11047-017-9652-ZMaRDI QIDQ6061995zbMATH OpenOpenAlexFDO

Authors Marcos Villagra, Abuzer Yakaryılmaz

Publication date 30 November 2023

Published in Natural Computing (Search for Journal in Brave)

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

zbMATH Keywords

probabilistic automataquantum automatastate complexitybounded erroraffine automataone-sided errorstochastic language

Mathematics Subject Classification ID

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

Abstract: In this work we study a non-linear generalization based on affine transformations of probabilistic and quantum automata proposed recently by D'iaz-Caro and Yakary{i}lmaz cite{DCY16A} referred as affine automata. First, we present efficient simulations of probabilistic and quantum automata by means of affine automata which allows us to characterize the class of exclusive stochastic languages. Then, we initiate a study on the succintness of affine automata. In particular, we show that an infinite family of unary regular languages can be recognized by 2-state affine automata but the state numbers of quantum and probabilistic automata cannot be bounded. Finally, we present the characterization of all (regular) unary languages recognized by two-state affine automata.

Recommendations

• Language Recognition Power and Succinctness of Affine Automata
• On the computational power of affine automata
• Affine computation and affine automaton
• Exact Affine Counter Automata
• Exact affine counter automata

Cites work

• scientific article; zbMATH DE number 6515829 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Characterizations of one-way general quantum finite automata
• Exact affine counter automata
• Implications of quantum automata for contextuality
• Language Recognition Power and Succinctness of Affine Automata
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• Languages recognized by nondeterministic quantum finite automata
• Lower space bounds for randomized computation
• More on quantum, stochastic, and pseudo stochastic languages with few states
• On the computational power of affine automata
• Potential of quantum finite automata with exact acceptance
• Probabilistic automata
• Quantum automata and quantum grammars
• Quantum finite automata: a modern introduction
• Space-Efficient Deterministic Simulation of Probabilistic Automata
• Succinctness of two-way probabilistic and quantum finite automata
• Superiority of exact quantum automata for promise problems
• Unbounded-error quantum computation with small space bounds
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Word-functions of stochastic and pseudo stochastic automata

Cited in

(5)

• Language Recognition Power and Succinctness of Affine Automata
• Language recognition by two-way deterministic pushdown automata
• Computational limitations of affine automata and generalized affine automata
• Space-efficient recognition of sparse self-reducible languages
• Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition

This page was built for publication: Language recognition power and succinctness of affine automata

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