Symmetries of automata
For a given reachable automaton A, we prove that the (state-) endomorphism monoid End(A) divides its characteristic monoid M(A). Hence so does its (state-)automorphism group Aut(A), and, for finite A, Aut(A) is a homomorphic image of a subgroup of the characteristic monoid. It follows that in the pr...
Збережено в:
| Опубліковано в: : | Algebra and Discrete Mathematics |
|---|---|
| Дата: | 2015 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2015
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/152786 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Symmetries of automata / A. Egri-Nagy, C.L. Nehaniv // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 48-57. — Бібліогр.: 7 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862698341025972224 |
|---|---|
| author | Egri-Nagy, A. Nehaniv, C.L. |
| author_facet | Egri-Nagy, A. Nehaniv, C.L. |
| citation_txt | Symmetries of automata / A. Egri-Nagy, C.L. Nehaniv // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 48-57. — Бібліогр.: 7 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | For a given reachable automaton A, we prove that the (state-) endomorphism monoid End(A) divides its characteristic monoid M(A). Hence so does its (state-)automorphism group Aut(A), and, for finite 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 G of A, a finite automaton 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(A), namely the symmetry group G and the quotient of M(A) induced by the action of G. Moreover, this division is an embedding if M(A) is transitive on states of 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 | 2025-12-07T16:32:42Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-152786 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-07T16:32:42Z |
| publishDate | 2015 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Egri-Nagy, A. Nehaniv, C.L. 2019-06-12T20:52:55Z 2019-06-12T20:52:55Z 2015 Symmetries of automata / A. Egri-Nagy, C.L. Nehaniv // Algebra and Discrete Mathematics. — 2015. — Vol. 19, № 1. — С. 48-57. — Бібліогр.: 7 назв. — англ. 1726-3255 2010 MSC:20B25, 20E22, 20M20, 20M35, 68Q70. https://nasplib.isofts.kiev.ua/handle/123456789/152786 For a given reachable automaton A, we prove that the (state-) endomorphism monoid End(A) divides its characteristic monoid M(A). Hence so does its (state-)automorphism group Aut(A), and, for finite 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 G of A, a finite automaton 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(A), namely the symmetry group G and the quotient of M(A) induced by the action of G. Moreover, this division is an embedding if M(A) is transitive on states of 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. This work was in part supported by the EU FP6 Project OPAALS (Contract No
 IST-034824) and the FP7 EU Project BIOMICS (contract number CNECT-318202).
 This support is gratefully acknowledged. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Symmetries of automata Article published earlier |
| spellingShingle | Symmetries of automata Egri-Nagy, A. Nehaniv, C.L. |
| 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 |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/152786 |
| work_keys_str_mv | AT egrinagya symmetriesofautomata AT nehanivcl symmetriesofautomata |