Search Results

Documents authored by Wächter, Jan Philipp

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 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.
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}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.6
An Automaton Group with PSPACE-Complete Word Problem

Authors: Jan Philipp Wächter and Armin Weiß

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
We construct an automaton group with a PSPACE-complete word problem, proving a conjecture due to Steinberg. Additionally, the constructed group has a provably more difficult, namely EXPSPACE-complete, compressed word problem. Our construction directly simulates the computation of a Turing machine in an automaton group and, therefore, seems to be quite versatile. It combines two ideas: the first one is a construction used by D'Angeli, Rodaro and the first author to obtain an inverse automaton semigroup with a PSPACE-complete word problem and the second one is to utilize a construction used by Barrington to simulate circuits of bounded degree and logarithmic depth in the group of even permutations over five elements.
Cite as

Jan Philipp Wächter and Armin Weiß. An Automaton Group with PSPACE-Complete Word Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wachter_et_al:LIPIcs.STACS.2020.6,
  author =	{W\"{a}chter, Jan Philipp and Wei{\ss}, Armin},
  title =	{{An Automaton Group with PSPACE-Complete Word Problem}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.6},
  URN =		{urn:nbn:de:0030-drops-118674},
  doi =		{10.4230/LIPIcs.STACS.2020.6},
  annote =	{Keywords: automaton group, word problem, PSPACE, compressed word problem}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact