Growth of semigroups generated by Mealy automata








Vitaly Sushchanskyy






We study only Mealy automata, in which the input and the output alphabets coincide. Such an automaton $A$ over an alphabet $X, \vert X\vert<\infty$, with a fixed initial state $q$ defines a transformation $t_{A,q}$ on the sets of fnite and infinite words $X^*$ and $X^\omega$ respectively. The semigroup $TA(X)$ of all automaton transformations on $X^*$ and $X^\omega$ can be described as a semigroup of elliptic endomorphisms [1], of rooted tree, corresponding to poset $X^*$ with respect to the prefix order. We consider the structure of this semigroup: some standard subsemigroups, Green relations, the conjugation relation and representations of abstract semigroups by automaton transformations. For every automaton $A$ with the set of inside states $Q$, we denote $S_A$ - the semigroup generated by transformations $t_{A,q}$, $q\in Q$. We consider the growth function of the automaton $A$ and the semigroup $S_A$ , in particular, we describe all semigroups generated by automata with two states over a $2$-element alphabet, and we compute the growth function of these semigroups and automata [2],[3],[4].






Sponsored in part by the FCT approved projects POCTI 32817/99 and POCTI/MAT/37670/2001 in participation with the European Community Fund FEDER and by FCT through Centro de Matemática da Universidade do Porto. Also sponsored in part by FCT, the Faculdade de Ciências da Universidade do Porto, Programa Operacional Ciência, Tecnologia, Inovação do Quadro Comunitário de Apoio III, and by Caixa Geral de Depósitos.