Symmetries of automata

Attila Egri-Nagy ; Chrystopher L. Nehaniv

Algebra and discrete mathematics, Tome 19 (2015) no. 1, pp. 48-57

Résumé

For a given reachable automaton $\mathcal{A}$, we prove that the (state-) endomorphism monoid $\operatorname{End}({\mathcal{A}})$ divides its characteristic monoid $M({\mathcal{A}})$. Hence so does its (state-)automorphism group $\operatorname{Aut}({\mathcal{A}})$, and, for finite $\mathcal{A}$, $\operatorname{Aut}(\mathcal{A})$ is a homomorphic image of a subgroup of the characteristic monoid. It follows that in the presence of a (state-) automorphism group $G$ of $\mathcal{A}$, a finite automaton $\mathcal{A}$ (and its transformation monoid) always has a decomposition as a divisor of the wreath product of two transformation semigroups whose semigroups are divisors of $M(\mathcal{A})$, namely the symmetry group $G$ and the quotient of $M(\mathcal{A})$ induced by the action of $G$. Moreover, this division is an embedding if $M(\mathcal{A})$ is transitive on states of $\mathcal{A}$. For more general automorphisms, which may be non-trivial on input letters, counterexamples show that they need not be induced by any corresponding characteristic monoid element.