Symmetries of automata
For a given reachable automaton \(\mathcal A\), we prove that the (state-) endomorphism monoid \(End({\mathcal A})\) divides its characteristic monoid \(M({\mathcal A})\). Hence so does its (state-)automorphism group \(Aut({\mathcal A})\), and, for finite \(\mathcal A\), \(Aut(\mathcal A)\) is a hom...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Lugansk National Taras Shevchenko University
2018
|
| Schlagworte: | |
| Online Zugang: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1175 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Algebra and Discrete Mathematics |
Institution
Algebra and Discrete Mathematics| Zusammenfassung: | For a given reachable automaton \(\mathcal A\), we prove that the (state-) endomorphism monoid \(End({\mathcal A})\) divides its characteristic monoid \(M({\mathcal A})\). Hence so does its (state-)automorphism group \(Aut({\mathcal A})\), and, for finite \(\mathcal A\), \(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. |
|---|