Algebraic Decision Problems over the Activity Hierarchy of Automaton Structures

• Applicant: Dr. Jan Philipp Wächter
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: from 2021 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 492814705

• Final Report Year: 2024

Final Report Abstract

The project made significant contributions to our knowledge on algorithmic questions for self-similar and automaton structures. Most noteworthy are the undecidability result for the freeness problem for automaton semigroups and monoids (which solves the semigroup and monoid cases of an open problem listed by Grigorchuk, Nekrashevych and Sushchanskĭi) and the decidability of the finiteness problem for automaton semigroups of (extended) bounded activity (solving an open problem by Bartholdi, Godin, Klimann, and Picantin). The project also settled the question on the complexity of the uniform word problem for finitary automaton groups (as an alternative, more succinct way of presenting finite groups) and resulted in a new construction for showing that the free product of many self-similar semigroups is itself self-similar. Finally, the project also resulted in a survey on the word problem for automaton groups that aims at disseminating the used techniques to a wider audience in Mathematics and Computer Science. Topics of the project were presented at seminars and conferences internationally.

Publications

• Decidability Results and Open Problems for Automaton Structures Seminario Al@Bicocca, Università degli Studi di Milano-Bicocca, Italy
  Wächter, Jan Philipp
  
• Decision Problems for Automaton Groups and Monoids of Bounded Activity Noon Seminar, Universität des Saarlandes (Saarbrücken), Germany
  Wächter, Jan Philipp
  
• Every numerical semigroup arises as an automaton monoid.
  Tara Macalister Brough, Alan J. Cain & Jan Philipp Wächter
  
• The Word Problem for Finitary Automaton Groups 25th International Conference on Descriptional Complexity of Formal Systems (DCFS 2023) Universität Potsdam, Germany
  Wächter, Jan Philipp
  
• The Word Problem for Finitary Automaton Groups. Lecture Notes in Computer Science, 94-108. Springer Nature Switzerland.
  Kotowsky, Maximilian & Wächter, Jan Philipp
  
• 6 The word problem for automaton groups. Languages and Automata, 265-396. De Gruyter.
  Wächter, Jan Philipp & Weiß, Armin
  
• Decision Problems for Automaton Semigroups and Groups North British Semigroups and Applications Network (NBSAN) Satellite Meeting to the 75th British Mathematical Colloquium (BMC 2024) University of Manchester, UK
  Wächter, Jan Philipp
  
• Recent Developments on Decision Problems for Automaton Groups and Semigroups Geometric and Asymptotic Group Theory with Applications (GAGTA) 2024 Centre International de Rencontres Mathématiques (CIRM), Marseille, France
  Wächter, Jan Philipp
  
• The Finiteness Problem for Automaton Semigroups of Extended Bounded Activity.
  Daniele D’Angeli, Emanuele Rodaro & Jan Philipp Wächter
  
• ‘The Freeness Problem for Automaton Semigroups’. In: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) (Bratislava, Slovakia, 26th–30th Aug. 2024). Ed. by Rastislav Královič and Antonín Kučera. Vol. 306. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz- Zentrum für Informatik, 2024.
  Daniele D’Angeli, Emanuele Rodaro & Jan Philipp Wächter
  
• Preserving self-similarity in free products of semigroups. International Journal of Algebra and Computation, 35(08), 1091-1121.
  Brough, Tara Macalister; Wächter, Jan Philipp & Welker, Janette