2026-07-21T14:14:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20600 2024-08-23T05:50:29Z ddc:004 open_access

The Freeness Problem for Automaton Semigroups D'Angeli, Daniele Rodaro, Emanuele Wächter, Jan Philipp Automaton Monoid Automaton Semigroup Freeness Problem Free Presentation We present a new technique to encode Post’s Correspondence Problem into automaton semigroups and monoids. The encoding allows us to precisely control whether there exists a relation in the generated semigroup/monoid and thus show that the freeness problems for automaton semigroups and for automaton monoids (listed as open problems by Grigorchuk, Nekrashevych and Sushchanskĭi) are undecidable. The construction seems to be quite versatile and we obtain the undecidability of further problems: Is a given automaton semigroup (monoid) (left) cancellative? Is it equidivisible (which - together with the existence of a (proper) length function - characterizes free semigroups and monoids)? Does a given map extend into a homomorphism between given automaton semigroups? Finally, our construction can be adapted 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniele D'Angeli and Emanuele Rodaro and Jan Philipp Wächter 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.44 urn:nbn:de:0030-drops-206002 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.44 eng https://creativecommons.org/licenses/by/4.0/legalcode