DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.44

The Freeness Problem for Automaton Semigroups

Authors: Daniele D'Angeli, Emanuele Rodaro, and Jan Philipp Wächter

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

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 Sushchanskĭ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.

Cite as

Daniele D'Angeli, Emanuele Rodaro, and Jan Philipp Wächter. The Freeness Problem for Automaton Semigroups. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dangeli_et_al:LIPIcs.MFCS.2024.44,
  author =	{D'Angeli, Daniele and Rodaro, Emanuele and W\"{a}chter, Jan Philipp},
  title =	{{The Freeness Problem for Automaton Semigroups}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.44},
  URN =		{urn:nbn:de:0030-drops-206002},
  doi =		{10.4230/LIPIcs.MFCS.2024.44},
  annote =	{Keywords: Automaton Monoid, Automaton Semigroup, Freeness Problem, Free Presentation}
}

Search Results

Documents authored by D'Angeli, Daniele

The Freeness Problem for Automaton Semigroups

Abstract

Cite as

Thanks for your feedback!

Could not send message