| Autor: |
D'Angeli, Daniele, Rodaro, Emanuele, Wächter, Jan Philipp |
| Rok vydání: |
2024 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
We show that the freeness problems for automaton semigroups and for automaton monoids are undecidable by giving a reduction from Post's Correspondence Problem. This construction seems to be quite versatile and we also immediately obtain that the problems of testing whether a given automaton semigroup (monoid) is (left) cancellative or whether it is equidivisible are undecidable. We also obtain that it is undecidable whether a given map extends into a homomorphism of automaton semigroups. Finally, we adapt our construction to show that it is undecidable whether a given automaton generates a free monoid whose basis is given by the states (but where we allow one state to act as the identity). In the semigroup case, we show a weaker version of this statement. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
