Document Open Access Logo

The Freeness Problem for Automaton Semigroups

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

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2024.44.pdf
  • Filesize: 0.83 MB
  • 18 pages

Document Identifiers

Author Details

Daniele D'Angeli
  • Università degli Studi Niccolò Cusano, Roma, Italy
Emanuele Rodaro
  • Department of Mathematics, Politecnico di Milano, Italy
Jan Philipp Wächter
  • Fachrichtung Mathematik, Universität des Saarlandes, Saarbrücken, Germany

Funding

  • Wächter, Jan Philipp: funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 492814705 – while visiting the Department of Mathematics at Politecnico di Milano. The listed affiliation is his current one, partly funded by ERC grant 101097307.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.MFCS.2024.44

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Automaton Monoid
  • Automaton Semigroup
  • Freeness Problem
  • Free Presentation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Laurent Bartholdi, Thibault Godin, Ines Klimann, Camille Noûs, and Matthieu Picantin. A new hierarchy for automaton semigroups. International Journal of Foundations of Computer Science, 31(08):1069-1089, 2020. URL: https://doi.org/10.1142/S0129054120420046.
  2. Laurent Bartholdi and Ivan Mitrofanov. The word and order problems for self-similar and automata groups. Groups, Geometry, and Dynamics, 14:705-728, 2020. URL: https://doi.org/10.4171/GGD/560.
  3. Laurent Bartholdi and Pedro Silva. Groups defined by automata. In Jean-Éric Pin, editor, Handbook of Automata Theory, volume II, chapter 24, pages 871-911. European Mathematical Society, September 2021. Google Scholar
  4. Paul Bell and Igor Potapov. Reachability problems in quaternion matrix and rotation semigroups. Information and Computation, 206(11):1353-1361, 2008. URL: https://doi.org/10.1016/j.ic.2008.06.004.
  5. Ievgen V. Bondarenko. Growth of Schreier graphs of automaton groups. Mathematische Annalen, 354(2):765-785, 2012. URL: https://doi.org/10.1007/s00208-011-0757-x.
  6. Ievgen V. Bondarenko, Natalia V. Bondarenko, Said N. Sidki, and Flavia R. Zapata. On the conjugacy problem for finite-state automorphisms of regular rooted trees. Groups, Geometry, and Dynamics, 7:232-355, 2013. URL: https://doi.org/10.4171/GGD/184.
  7. Tara Brough and Alan J. Cain. Automaton semigroups: New constructions results and examples of non-automaton semigroups. Theoretical Computer Science, 674:1-15, 2017. URL: https://doi.org/10.1016/j.tcs.2017.02.003.
  8. Andrew M. Brunner and Said Sidki. The generation of GL(n, ℤ) by finite state automata. International Journal of Algebra and Computation, 08(01):127-139, 1998. URL: https://doi.org/10.1142/S0218196798000077.
  9. Alan J. Cain. Automaton semigroups. Theoretical Computer Science, 410(47):5022-5038, 2009. URL: https://doi.org/10.1016/j.tcs.2009.07.054.
  10. Julien Cassaigne, Tero Harju, and Juhani Karhumäki. On the undecidability of freeness of matrix semigroups. International Journal of Algebra and Computation, 09(03n04):295-305, 1999. URL: https://doi.org/10.1142/S0218196799000199.
  11. Daniele D'Angeli, Dominik Francoeur, Emanuele Rodaro, and Jan Philipp Wächter. Infinite automaton semigroups and groups have infinite orbits. Journal of Algebra, 553:119-137, 2020. URL: https://doi.org/10.1016/j.jalgebra.2020.02.014.
  12. Daniele D'Angeli, Emanuele Rodaro, and Jan Philipp Wächter. Automaton semigroups and groups: On the undecidability of problems related to freeness and finiteness. Israel Journal of Mathematics, 237:15-52, 2020. URL: https://doi.org/10.1007/s11856-020-1972-5.
  13. Daniele D'Angeli, Emanuele Rodaro, and Jan Philipp Wächter. Erratum to semigroups and groups: On the undecidability of problems related to freeness and finiteness. Israel Journal of Mathematics, 245:535-542, 2021. URL: https://doi.org/10.1007/s11856-021-2206-1.
  14. Daniele D'Angeli, Emanuele Rodaro, and Jan Philipp Wächter. On the complexity of the word problem for automaton semigroups and automaton groups. Advances in Applied Mathematics, 90:160-187, 2017. URL: https://doi.org/10.1016/j.aam.2017.05.008.
  15. Daniele D'Angeli, Emanuele Rodaro, and Jan Philipp Wächter. On the structure theory of partial automaton semigroups. Semigroup Forum, pages 51-76, 2020. URL: https://doi.org/10.1007/s00233-020-10114-5.
  16. Pierre Gillibert. The finiteness problem for automaton semigroups is undecidable. International Journal of Algebra and Computation, 24(01):1-9, 2014. URL: https://doi.org/10.1142/S0218196714500015.
  17. Pierre Gillibert. An automaton group with undecidable order and Engel problems. Journal of Algebra, 497:363-392, 2018. URL: https://doi.org/10.1016/j.jalgebra.2017.11.049.
  18. Yair Glasner and Shahar Mozes. Automata and square complexes. Geometriae Dedicata, 111:43-64, 2005. URL: https://doi.org/10.1007/s10711-004-1815-2.
  19. Rostislav I. Grigorchuk, Volodymyr V. Nekrashevych, and Vitaly I. Sushchanskĭi. Automata, dynamical systems, and groups. Proceedings of the Steklov Institute of Mathematics, 231:128-203, 2000. Google Scholar
  20. Rostislav I. Grigorchuk and Igor Pak. Groups of intermediate growth: an introduction. L’Enseignement Mathématique, 54:251-272, 2008. Google Scholar
  21. Rostislav I. Grigorchuk and Andrzej Żuk. The lamplighter group as a group generated by a 2-state automaton, and its spectrum. Geometriae Dedicata, 87:209-244, 2001. URL: https://doi.org/10.1023/A:1012061801279.
  22. Narain Gupta and Saïd Sidki. On the burnside problem for periodic groups. Mathematische Zeitschrift, 182(3):385-388, 1983. Google Scholar
  23. John M. Howie. Fundamentals of Semigroup Theory. London Mathematical Society Monographs. Clarendon Press, 1995. Google Scholar
  24. Kate Juschenko. Amenability of discrete groups by examples. American Mathematical Society, 2022. Google Scholar
  25. David A. Klarner, Jean-Camille Birget, and Wade Satterfield. On the undecidability of the freeness of integer matrix semigroups. International Journal of Algebra and Computation, 1(2):223-226, 1991. Google Scholar
  26. Ines Klimann. Automaton semigroups: The two-state case. Theory of Computing Systems, 58:664-680, 2016. URL: https://doi.org/10.1007/s00224-014-9594-0.
  27. Ines Klimann. To Infinity and Beyond. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 131:1-131:12, Dagstuhl, Germany, 2018. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.131.
  28. Maximilian Kotowsky and Jan Philipp Wächter. The word problem for finitary automaton groups. In Henning Bordihn, Nicholas Tran, and György Vaszil, editors, Descriptional Complexity of Formal Systems, pages 94-108, Cham, 2023. Springer Nature Switzerland. Google Scholar
  29. Roger Lyndon and Paul Schupp. Combinatorial Group Theory. Classics in Mathematics. Springer, 2001. First edition 1977. Google Scholar
  30. Tara Macalister Brough, Jan Philipp Wächter, and Janette Welker. Automaton semigroup free products revisited. arXiv preprint, 2023. URL: https://doi.org/10.48550/arXiv.2003.12810.
  31. Arnaldo Mandel and Imre Simon. On finite semigroups of matrices. Theoretical Computer Science, 5(2):101-111, 1977. URL: https://doi.org/10.1016/0304-3975(77)90001-9.
  32. Turlough Neary. Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of Leibniz International Proceedings in Informatics (LIPIcs), pages 649-661, Dagstuhl, Germany, 2015. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2015.649.
  33. Volodymyr V. Nekrashevych. Self-similar groups, volume 117 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2005. URL: https://doi.org/10.1090/surv/117.
  34. Matthieu Picantin. Automatic Semigroups vs Automaton Semigroups. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 124:1-124:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.124.
  35. Emil L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52:264-269, 1946. URL: https://doi.org/10.1090/s0002-9904-1946-08555-9.
  36. Emanuele Rodaro and Jan Philipp Wächter. The self-similarity of free semigroups and groups. In Munehiro Iwami, editor, Logic, Algebraic system, Language and Related Areas in Computer Science, volume 2229 of RIMS Kôkyûroku, pages 11-20. Research Institute for Mathematical Sciences, Kyoto University, 2022. URL: https://doi.org/10.48550/arXiv.2205.10248.
  37. Pedro V. Silva and Benjamin Steinberg. On a class of automata groups generalizing lamplighter groups. International Journal of Algebra and Computation, 15(05n06):1213-1234, 2005. URL: https://doi.org/10.1142/S0218196705002761.
  38. Rachel Skipper and Benjamin Steinberg. Lamplighter groups, bireversible automata, and rational series over finite rings. Groups, Geometry and Dynamics, 14(2):567-589, 2020. URL: https://doi.org/10.4171/GGD/555.
  39. Benjamin Steinberg, Mariya Vorobets, and Yaroslav Vorobets. Automata over a binary alphabet generating free groups of even rank. International Journal of Algebra and Computation, 21(01n02):329-354, 2011. URL: https://doi.org/10.1142/S0218196711006194.
  40. Zoran Šunić and Enric Ventura. The conjugacy problem in automaton groups is not solvable. Journal of Algebra, 364:148-154, 2012. URL: https://doi.org/10.1016/j.jalgebra.2012.04.014.
  41. Mariya Vorobets and Yaroslav Vorobets. On a free group of transformations defined by an automaton. Geometriae Dedicata, 124:237-249, 2007. URL: https://doi.org/10.1007/s10711-006-9060-5.
  42. Mariya Vorobets and Yaroslav Vorobets. On a series of finite automata defining free transformation groups. Groups, Geometry, and Dynamics, 4:337-405, 2010. URL: https://doi.org/10.4171/GGD/87.
  43. Jan Philipp Wächter. Automaton Structures - Decision Problems and Structure Theory. Doctoral thesis, Institut für Formale Methoden der Informatik, Universität Stuttgart, 2020. URL: https://doi.org/10.18419/opus-11267.
  44. Jan Philipp Wächter and Armin Weiß. Automata and Languages - GAGTA Book 3, chapter "The Word Problem for Automaton Groups". DeGruyter, 2024. In preparation. Google Scholar
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 Imprint Privacy Contact