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

Das vorliegende Projekt bewegt sich im interdisziplinären Bereich zwischen theoretischer Informatik und Mathematik. Dabei soll es einen Beitrag zur Erforschung algebraischer Entscheidungsprobleme leisten, einem weit zurückreichenden und aktiven Forschungszweig, der bereits 1911 durch Max Dehn begründet wurde. Seine grundsätzlichen Fragestellungen betreffen die Entscheidbarkeit und Komplexität von Problemen über selbstähnlichen algebraischen Strukturen (insbesondere Gruppen und Halbgruppen), darunter insbesondere jene, die durch endliche Automaten erzeugt werden. Beispiele solcher Probleme bilden das Wortproblem mit der Frage, ob ein gegebenes Wort in den Erzeugern das neutrale Element darstellt, und das Endlichkeitsproblem, das nach der Endlichkeit des erzeugten Objekts fragt. Es gibt jedoch etliche mehr und einige davon sollen im Projekt betrachtet werden.Die Verwendung von Automaten – eigentlich einem Konzept aus der theoretischen Informatik – zum Erzeugen vorwiegend mathematischer algebraischer Objekte zog ab der zweiten Hälfte des 20. Jahrhunderts nicht nur durch die Verbreitung von Computertechnologie viel Interesse auf sich, sondern auch, weil klar wurde, dass viele komplexe Gruppen mit speziellen, überraschenden, sonderbaren und manchmal regelrecht bizarren Eigenschaften eine natürliche, oft simple Darstellung mittels endlicher Automaten besitzen. Während das historisch erste Beispiel einer Gruppe mit subexponentiellem aber superpolynomiellem Wachstum, die Grigorchuk-Gruppe, das bekannteste Beispiel hierfür ist, gibt es viele weitere. Automatenstrukturen verändern bis heute unsere Sichtweise auf Gruppen und andere algebraische Objekte. In diesem Licht scheint es wenig überraschend, dass viele Probleme in diesem Bereich – darunter auch einige scheinbar simple – weiterhin offen sind.Ziel dieses Projektes ist es einige dieser Probleme genauer zu untersuchen. Dadurch verspricht es nicht nur das Wissen über Automatenstrukturen für die Algebra zu vergrößern, sondern auch neue Werkzeuge und Einblicke zu algebraischen Entscheidungsproblemen in der Informatik zu liefern. Das Hauptaugenmerk liegt dabei auf Entscheidungsproblemen (wie den drei fundamentalen Problemen von Dehn, dem Freiheits- und Endlichkeitsproblem und gewissen Mitgliedschaftsproblemen) mit Bezug auf die sogenannte Aktivitätshierarchie. Diese wurde 2000 von Sidki eingeführt, um Gruppen basierend auf der Struktur der Kreise in ihren erzeugenden Automaten zu klassifizieren. Kürzlich wurde dieses Konzept von Bartholdi, Godin, Klimann und Picantin auf Monoide verallgemeinert und das vorliegende Projekt schlägt eine weitere Erweiterung vor. Darüber hinaus soll auch der Zusammenhang zwischen der Struktur des erzeugenden Automaten und der algebraischen Struktur des erzeugten Objekts untersucht werden, soweit dies für die Entscheidungsprobleme von Interesse ist. Diese Fragestellungen sollen dabei mit bestehenden aber auch neuen, noch zu entwickelnden Techniken gelöst werden.

• DFG-Verfahren: WBP Stipendium
• Internationaler Bezug: Italien
• Gastgeber: Professor Dr. Emanuele Rodaro