On the orbits of automaton semigroups and groups
We investigate the orbits of automaton semigroups and groups to obtain algorithmic and structural results, both for general automata but also for some special subclasses.First, we show that a more general version of the finiteness problem for automaton groups is undecidable. This problem is equivale...
Збережено в:
| Дата: | 2022 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Lugansk National Taras Shevchenko University
2022
|
| Теми: | |
| Онлайн доступ: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1692 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Algebra and Discrete Mathematics |
Репозитарії
Algebra and Discrete Mathematics| _version_ | 1856543380995047424 |
|---|---|
| author | D'Angeli, D. Francoeur, D. Rodaro, E. Wächter, J. Ph. |
| author_facet | D'Angeli, D. Francoeur, D. Rodaro, E. Wächter, J. Ph. |
| author_sort | D'Angeli, D. |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2023-02-23T09:59:31Z |
| description | We investigate the orbits of automaton semigroups and groups to obtain algorithmic and structural results, both for general automata but also for some special subclasses.First, we show that a more general version of the finiteness problem for automaton groups is undecidable. This problem is equivalent to the finiteness problem for left principal ideals in automaton semigroups generated by complete and reversible automata.Then, we look at \(\omega\)-word (i.\,e.\ right infinite words) with a finite orbit. We show that every automaton yielding an \(\omega\)-word with a finite orbit already yields an ultimately periodic one, which is not periodic in general, however. On the algorithmic side, we observe that it is not possible to decide whether a given periodic \(\omega\)-word has an infinite orbit and that we cannot check whether a given reversible and complete automaton admits an \(\omega\)-word with a finite orbit, a reciprocal problem to the finiteness problem for automaton semigroups in the reversible case.Finally, we look at automaton groups generated by reversible but not bi-reversible automata and show that many words have infinite orbits under the action of such automata. |
| first_indexed | 2025-12-02T15:42:17Z |
| format | Article |
| id | admjournalluguniveduua-article-1692 |
| institution | Algebra and Discrete Mathematics |
| language | English |
| last_indexed | 2025-12-02T15:42:17Z |
| publishDate | 2022 |
| publisher | Lugansk National Taras Shevchenko University |
| record_format | ojs |
| spelling | admjournalluguniveduua-article-16922023-02-23T09:59:31Z On the orbits of automaton semigroups and groups D'Angeli, D. Francoeur, D. Rodaro, E. Wächter, J. Ph. automaton groups, automaton semigroups, orbits, Schreier graphs, orbital graphs, reversible 20E99, 20F10, 20M30, 20M35, 68Q70 We investigate the orbits of automaton semigroups and groups to obtain algorithmic and structural results, both for general automata but also for some special subclasses.First, we show that a more general version of the finiteness problem for automaton groups is undecidable. This problem is equivalent to the finiteness problem for left principal ideals in automaton semigroups generated by complete and reversible automata.Then, we look at \(\omega\)-word (i.\,e.\ right infinite words) with a finite orbit. We show that every automaton yielding an \(\omega\)-word with a finite orbit already yields an ultimately periodic one, which is not periodic in general, however. On the algorithmic side, we observe that it is not possible to decide whether a given periodic \(\omega\)-word has an infinite orbit and that we cannot check whether a given reversible and complete automaton admits an \(\omega\)-word with a finite orbit, a reciprocal problem to the finiteness problem for automaton semigroups in the reversible case.Finally, we look at automaton groups generated by reversible but not bi-reversible automata and show that many words have infinite orbits under the action of such automata. Lugansk National Taras Shevchenko University 2022-06-15 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1692 10.12958/adm1692 Algebra and Discrete Mathematics; Vol 33, No 1 (2022) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1692/pdf_1 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/1692/773 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/1692/774 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/1692/775 Copyright (c) 2022 Algebra and Discrete Mathematics |
| spellingShingle | automaton groups automaton semigroups orbits Schreier graphs orbital graphs reversible 20E99 20F10 20M30 20M35 68Q70 D'Angeli, D. Francoeur, D. Rodaro, E. Wächter, J. Ph. On the orbits of automaton semigroups and groups |
| title | On the orbits of automaton semigroups and groups |
| title_full | On the orbits of automaton semigroups and groups |
| title_fullStr | On the orbits of automaton semigroups and groups |
| title_full_unstemmed | On the orbits of automaton semigroups and groups |
| title_short | On the orbits of automaton semigroups and groups |
| title_sort | on the orbits of automaton semigroups and groups |
| topic | automaton groups automaton semigroups orbits Schreier graphs orbital graphs reversible 20E99 20F10 20M30 20M35 68Q70 |
| topic_facet | automaton groups automaton semigroups orbits Schreier graphs orbital graphs reversible 20E99 20F10 20M30 20M35 68Q70 |
| url | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1692 |
| work_keys_str_mv | AT dangelid ontheorbitsofautomatonsemigroupsandgroups AT francoeurd ontheorbitsofautomatonsemigroupsandgroups AT rodaroe ontheorbitsofautomatonsemigroupsandgroups AT wachterjph ontheorbitsofautomatonsemigroupsandgroups |