Extended models of finite automata

Many of the numerous automaton models proposed in the literature can be regarded as a finite automaton equipped with an additional storage mechanism. In this thesis, we focus on two such models, namely the finite automata over groups and the homing vector automata. A finite automaton over a group $ G $ is a nondeterministic finite automaton equipped with a register that can hold an element of the group $ G $. Initially 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 finite automata over integer and rational matrix groups and reveal new relationships between the language classes corresponding to these models. We look at various parameters such as the growth rate of the groups and the run-time of the machines, to discover the effects of these parameters on the language recognition power. We establish a link between the decision problems of matrix semigroups and the decision problems of corresponding automata. We look at some computational models which are closely related to finite automata over groups, namely the valence pushdown automata and the context-free valence grammars and present some new results. We also propose the new homing vector automaton model, which is a finite automaton equipped with a vector, and which can multiply this vector with an appropriate 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 effect of various restrictions on the model by confining the matrices to a particular set and allowing the equivalence test only at the end of the computation. We define the different variants of the model and compare their language recognition power with that of the classical models. We establish a link between finite automata over matrix groups and one-way nondeterministic blind homing vector automata which extends our knowledge on the latter. We pay special attention to real-time homing vector automata and analyze their stateless versions and closure properties. We develop a method for encoding strings into vectors, based on the Stern-Brocot Tree, which may be of independent interest.