6533b85efe1ef96bd12bfade

RESEARCH PRODUCT

Language Recognition Power and Succinctness of Affine Automata

Abuzer YakaryilmazMarcos Villagra

subject

Discrete mathematicsNested word0102 computer and information sciences02 engineering and technologyω-automatonNonlinear Sciences::Cellular Automata and Lattice Gases01 natural sciencesMobile automaton010201 computation theory & mathematicsContinuous spatial automaton0202 electrical engineering electronic engineering information engineeringAutomata theoryQuantum finite automata020201 artificial intelligence & image processingAffine transformationComputer Science::Formal Languages and Automata TheoryMathematicsQuantum cellular automaton

description

In this work we study a non-linear generalization based on affine transformations of probabilistic and quantum automata proposed recently by Diaz-Caro and Yakaryilmaz [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.

yearjournalcountryeditionlanguage
2016-01-01
https://doi.org/10.1007/978-3-319-41312-9_10