Abstract:
Finite automaton has been one of the most studied models in automata theory. The limited power of the standard model has led researchers to make various extensions to the standard model. Counter automaton, automaton with multiplication, nite automaton over groups are some of the examples of such extensions. In this thesis, we study the computational power of real-time nite automaton that has been augmented with a vector of dimension k, and programmed to multiply this vector at each step by an appropriately selected k k matrix. Only one entry of the vector can be tested for equality to 1 at any time. We study the classes of languages recognized by deterministic, nondeterministic, and "blind" versions of these machines and compare them with each other. It turns out that these machines are closely related to some of the classical models like counter automata and generalized nite automata.
