Algebraische Entscheidungsprobleme über der Aktivitätshierarchie von Automatenstrukturen

• Antragsteller: Dr. Jan Philipp Wächter
• Fachliche Zuordnung: Theoretische Informatik ; Mathematik
• Förderung: Förderung von 2021 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 492814705

• Erstellungsjahr: 2024

Zusammenfassung der Projektergebnisse

Das Projekt trug zur signifikanten Vergrößerung unseres Wissens über algorithmische Fragestellungen zu selbst-ähnlichen und Automatenstrukturen bei. Besonders bemerkenswert sind hierbei das Unentscheidbarkeitsergebnis für das Freiheitsproblem von Automatenhalbgruppen und -monoiden (was eine Lösung der Halbgruppen- und Monoid-Fälle eines von Grigorchuk, Nekrashevych und Sushchanskĭi aufgeführten offenen Problems darstellt) sowie die Entscheidbarkeit des Endlichkeitsproblems für Automatenhalbgruppen (erweiterter) beschränkter Aktivität (was ein offenes Problem von Bartholdi, Godin, Klimann, und Picantin löst). Das Projekt klärte auch die Komplexität des uniformen Wortproblems für finitäre Automatengruppen (die eine kompaktere Alternative zur Darstellung endlicher Gruppen liefern) und ergab eine neue Konstruktion, die zeigt, dass das freie Produkt vieler selbst-ähnlicher Halbgruppen selbst selbst-ähnlich ist. Schließlich ergab das Projekt auch ein Übersichtsbuchkapitel zum Wortproblem für Automatengruppen, das die verwendeten Techniken einem größeren Teil der interessierten Öffentlichkeit in Mathematik und Informatik näherbringt. Themen des Projekts wurden auch international in Seminaren und bei Konferenzen vorgestellt.

Projektbezogene Publikationen (Auswahl)

• 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