@inproceedings{fabdf7f3bafa42649ff1b797d300c2ad,
title = "Language recognition power and succinctness 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{\'i}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.",
keywords = "Affine automata, Bounded-error, One-sided error, Probabilistic automata, Quantum automata, State complexity, Stochastic language",
author = "Marcos Villagra and Abuzer Yakaryılmaz",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 15th International Conference on Unconventional Computation and Natural Computation, UCNC 2016 ; Conference date: 11-07-2016 Through 15-07-2016",
year = "2016",
doi = "10.1007/978-3-319-41312-9\_10",
language = "English",
isbn = "9783319413112",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "116--129",
editor = "Anne Condon and Martyn Amos",
booktitle = "Unconventional Computation and Natural Computation - 15th International Conference, UCNC 2016, Proceedings",
address = "Germany",
}