Extended models of finite automata

Abstract

Many of the numerous automaton models proposed in the literature can be regarded as a nite automaton equipped with an additional storage mechanism. In this thesis, we focus on two such models, namely the nite automata over groups and the homing vector automata. A nite automaton over a group G is a nondeterministic nite automaton equipped with a register that holds an element of the group G. The register is initialized to the identity element of the group and a computation is successful if the register is equal to the identity element at the end of the computation after being multiplied with a group element at every step. We investigate the language recognition power of nite automata over integer and rational matrix groups and reveal new relationships between the language classes corresponding to these models. We examine the e ect of various parameters on the language recognition power. We establish a link between the decision problems of matrix semigroups and the corresponding automata. We present some new results about valence pushdown automata and context-free valence grammars. We also propose the new homing vector automaton model, which is a nite automaton equipped with a vector that can be multiplied with a matrix at each step. The vector can be checked for equivalence to the initial vector and the acceptance criterion is ending up in an accept state with the value of the vector being equal to the initial vector. We examine the e ect of various restrictions on the model by con ning the matrices to a particular set and allowing the equivalence test only at the end of the computation. We de ne the di erent variants of the model and compare their language recognition power with that of the classical models.