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

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{ADM_2015_19_1_a6,
     author = {Attila Egri-Nagy and Chrystopher L. Nehaniv},
     title = {Symmetries of automata},
     journal = {Algebra and discrete mathematics},
     pages = {48--57},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADM_2015_19_1_a6/}
}
TY  - JOUR
AU  - Attila Egri-Nagy
AU  - Chrystopher L. Nehaniv
TI  - Symmetries of automata
JO  - Algebra and discrete mathematics
PY  - 2015
SP  - 48
EP  - 57
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ADM_2015_19_1_a6/
LA  - en
ID  - ADM_2015_19_1_a6
ER  - 
%0 Journal Article
%A Attila Egri-Nagy
%A Chrystopher L. Nehaniv
%T Symmetries of automata
%J Algebra and discrete mathematics
%D 2015
%P 48-57
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ADM_2015_19_1_a6/
%G en
%F ADM_2015_19_1_a6
Attila Egri-Nagy; Chrystopher L. Nehaniv. Symmetries of automata. Algebra and discrete mathematics, Tome 19 (2015) no. 1, pp. 48-57. http://geodesic.mathdoc.fr/item/ADM_2015_19_1_a6/

[1] J. Araújo, P. V. Bünau, J. D. Mitchell, and M. Neunhöffer, “Computing automorphisms of semigroups”, Journal of Symbolic Computation, 45:3 (2010), 373–392 | DOI | MR | Zbl

[2] Pál Dömösi and Chrystopher L. Nehaniv, Algebraic Theory of Finite Automata Networks: An Introduction, SIAM Series on Discrete Mathematics and Applications, 11, Society for Industrial and Applied Mathematics, 2005 | MR

[3] Samuel Eilenberg, Automata, Languages and Machines, v. B, Academic Press, 1976 | Zbl

[4] A. C. Fleck, “On the automorphism group of an automaton”, Journal of the Association for Computing Machinery, 12:4 (1965), 566–569 | DOI | MR | Zbl

[5] Kenneth Krohn, John L. Rhodes, and Bret R. Tilson, “The prime decomposition theorem of the algebraic theory of machines”, Algebraic Theory of Machines, Languages, and Semigroups, chapter 5, ed. Michael A. Arbib, Academic Press, 1968, 81–125

[6] Chrystopher L. Nehaniv, “Algebra and formal models of understanding” (RIMS Kokyuroku, August 1996), Semigroups, Formal Languages and Computer Systems, 960, ed. Masami Ito, Kyoto Research Institute for Mathematics Sciences, 145–154 | MR

[7] John Rhodes, Applications of Automata Theory and Algebra via the Mathematical Theory of Complexity to Biology, Physics, Psychology, Philosophy, and Games, Foreword by Morris W. Hirsch, ed. Chrystopher L. Nehaniv, World Scientific Press, 2010 (Unpublished version: University of California at Berkeley, Mathematics Library, circa 1971) | MR | Zbl