|
Algebra and Discrete Mathematics, 2015, Volume 19, Issue 1, Pages 48–57
(Mi adm506)
|
|
|
|
RESEARCH ARTICLE
Symmetries of automata
Attila Egri-Nagya, Chrystopher L. Nehanivb a Centre for Research in Mathematics, University of Western Sydney
b Centre for Computer Science \& Informatics Research, University of Hertfordshire
Abstract:
For a given reachable automaton AA, we prove that the (state-) endomorphism monoid End(A)End(A) divides its characteristic monoid M(A)M(A). Hence so does its (state-)automorphism group Aut(A)Aut(A), and, for finite AA, Aut(A)Aut(A) is a homomorphic image of a subgroup of the characteristic monoid. It follows that in the presence of a (state-) automorphism group GG of AA, a finite automaton AA (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(A)M(A), namely the symmetry group GG and the quotient of M(A)M(A) induced by the action of GG. Moreover, this division is an embedding if M(A)M(A) is transitive on states of AA. 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.
Received: 02.05.2014 Revised: 12.01.2015
Citation:
Attila Egri-Nagy, Chrystopher L. Nehaniv, “Symmetries of automata”, Algebra Discrete Math., 19:1 (2015), 48–57
Linking options:
https://www.mathnet.ru/eng/adm506 https://www.mathnet.ru/eng/adm/v19/i1/p48
|
Statistics & downloads: |
Abstract page: | 331 | Full-text PDF : | 110 | References: | 73 |
|