The Freeness Problem for Automaton Semigroups
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917926495322112 |
|---|---|
| author | D'Angeli, Daniele Rodaro, Emanuele Wächter, Jan Philipp |
| author_facet | D'Angeli, Daniele Rodaro, Emanuele Wächter, Jan Philipp |
| contents | We show that the freeness problems for automaton semigroups and for automaton monoids are undecidable and, thereby, solve an open problem listed by Grigorchuk, Nekrashevych and Sush\-chansk\uıi. We achieve this using a new technique to encode Post's Correspondence Problem into automaton semigroups and monoids and our result even holds if we restrict the alphabet of the input automata to a constant size. The encoding allows us to precisely control the relations in the generated semigroup/monoid and the construction is quite versatile. In fact, we obtain further undecidability results on various semigroup notions (left cancellativity, equidivisibility and extending homomorphisms). Our construction can also be adapted to show that the free presentation problem for automaton monoids is undecidable (and yields a weaker statement in the semigroup case). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_01372 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Freeness Problem for Automaton Semigroups D'Angeli, Daniele Rodaro, Emanuele Wächter, Jan Philipp Formal Languages and Automata Theory Group Theory 20F10 20F65 20M05 20M30 68Q17 68Q45 F.4.m We show that the freeness problems for automaton semigroups and for automaton monoids are undecidable and, thereby, solve an open problem listed by Grigorchuk, Nekrashevych and Sush\-chansk\uıi. We achieve this using a new technique to encode Post's Correspondence Problem into automaton semigroups and monoids and our result even holds if we restrict the alphabet of the input automata to a constant size. The encoding allows us to precisely control the relations in the generated semigroup/monoid and the construction is quite versatile. In fact, we obtain further undecidability results on various semigroup notions (left cancellativity, equidivisibility and extending homomorphisms). Our construction can also be adapted to show that the free presentation problem for automaton monoids is undecidable (and yields a weaker statement in the semigroup case). |
| title | The Freeness Problem for Automaton Semigroups |
| topic | Formal Languages and Automata Theory Group Theory 20F10 20F65 20M05 20M30 68Q17 68Q45 F.4.m |
| url | https://arxiv.org/abs/2402.01372 |