Language recognition power and succinctness of affine automata

DOI10.1007/S11047-017-9652-ZzbMATH Open1528.68130arXiv1602.05432OpenAlexW3100394160MaRDI QIDQ6061995FDOQ6061995

Authors: Marcos Villagra, Abuzer Yakaryılmaz 

Publication date: 30 November 2023

Published in: Natural Computing (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (5)

• 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
• Language Recognition Power and Succinctness of Affine Automata

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)