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...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Lugansk National Taras Shevchenko University
2018
|
| Теми: | |
| Онлайн доступ: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1175 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Algebra and Discrete Mathematics |
Репозитарії
Algebra and Discrete Mathematics| _version_ | 1856543132038987776 |
|---|---|
| author | Egri-Nagy, Attila Nehaniv, Chrystopher L. |
| author_facet | Egri-Nagy, Attila Nehaniv, Chrystopher L. |
| author_sort | Egri-Nagy, Attila |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2018-05-17T07:50:53Z |
| description | 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. |
| first_indexed | 2026-02-08T07:57:37Z |
| format | Article |
| id | admjournalluguniveduua-article-1175 |
| institution | Algebra and Discrete Mathematics |
| language | English |
| last_indexed | 2026-02-08T07:57:37Z |
| publishDate | 2018 |
| publisher | Lugansk National Taras Shevchenko University |
| record_format | ojs |
| spelling | admjournalluguniveduua-article-11752018-05-17T07:50:53Z Symmetries of automata Egri-Nagy, Attila Nehaniv, Chrystopher L. 20B25, 20E22, 20M20, 20M35, 68Q70 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. Lugansk National Taras Shevchenko University 2018-05-17 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1175 Algebra and Discrete Mathematics; Vol 19, No 1 (2015) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1175/664 Copyright (c) 2018 Algebra and Discrete Mathematics |
| spellingShingle | 20B25 20E22 20M20 20M35 68Q70 Egri-Nagy, Attila Nehaniv, Chrystopher L. Symmetries of automata |
| title | Symmetries of automata |
| title_full | Symmetries of automata |
| title_fullStr | Symmetries of automata |
| title_full_unstemmed | Symmetries of automata |
| title_short | Symmetries of automata |
| title_sort | symmetries of automata |
| topic | 20B25 20E22 20M20 20M35 68Q70 |
| topic_facet | 20B25 20E22 20M20 20M35 68Q70 |
| url | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1175 |
| work_keys_str_mv | AT egrinagyattila symmetriesofautomata AT nehanivchrystopherl symmetriesofautomata |