Paper Info
Title
Language recognition power and succintness of affine automata.
Abstract
In this work we study a non-linear generalization based on affine transformations of probabilistic and quantum automata proposed recently by Díaz-Caro and Yakaryılmaz [6] 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, whereas the number of states of any quantum and probabilistic automata cannot be bounded. Finally, we present the characterization of all regular unary languages recognized by two-state affine automata.
Year
DOI
Venue
2016
10.1007/978-3-319-41312-9_10
Natural Computing
Keywords
DocType
Volume
Probabilistic automata,Quantum automata,Affine automata,State complexity,Stochastic language,Bounded-error,One-sided error
Conference
17
Issue
ISSN
ISBN
2
1567-7818
978-3-319-41311-2
Citations 
PageRank 
References 
0
0.34
16
Authors
2
Name
Order
Citations
PageRank
Marcos Villagra1146.62
Abuzer Yakaryilmaz216825.31