Brückensätze für Gruppentheorie und formale Sprachen

Gibt es eine natürliche oder bemerkenswerte Möglichkeit, mathematische Gruppen und formale CS- Sprachen oder ein anderes zentrales CS-Konzept, z. B. Turing-Maschinen , in Beziehung zu setzen oder zu verknüpfen ?

Ich suche Referenzen / Bewerbungen. Beachten Sie jedoch, dass mir die Verbindung zwischen Halbgruppen und CS-Sprachen bekannt ist (nämlich über endliche Automaten ). (Betrachtet diese Literatur zu Halbautomaten jemals "Gruppenautomaten"?)

Ich habe vor vielen Jahren einen Aufsatz gesehen, der sich dem nähern könnte und der TM-Übergangstabellen in eine binäre Operation umwandelt, möglicherweise manchmal eine Gruppe, möglicherweise basierend auf einer Art von Symmetrie in der TM-Zustandstabelle. Das hat es nicht sonderlich untersucht, aber auch nicht ausgeschlossen.

Hat oder könnte dies insbesondere im Hinblick auf die umfangreiche mathematische Forschung zur Klassifizierung endlicher Gruppen eine Bedeutung oder Interpretation in TCS haben? Wie sieht die "algorithmische Linse" dieses gewaltigen mathematischen Forschungsgebäudes aus? Was sagt es über eine mögliche verborgene Struktur in der Berechnung aus?

Diese Frage ist teilweise von einigen anderen Anmerkungen inspiriert, zB:

• Verwendung algebraischer Strukturen in TCS

• RJ Lipton über Gromovs Theorem

Lassen Sie mich zunächst Ihre Unterfrage beantworten: Betrachtet die Literatur zu Halbautomaten jemals "Gruppenautomaten"? . Die Antwort ist ja. In seinem Buch (Automaten, Sprachen und Maschinen. Bd. B, Academic Press) beschrieb S. Eilenberg die regulären Sprachen, die von endlichen kommutativen Gruppen und Gruppen erkannt werden . Ähnliche Ergebnisse sind für endliche nichtpotente Gruppen, lösliche Gruppen und überlösliche Gruppen bekannt.$p$

Endliche Gruppen spielen auch eine wichtige Rolle bei der Suche nach vollständigen Identitäten für reguläre Ausdrücke. Ein unendliches vollständiges Set wurde von John Conway vorgeschlagen und diese Vermutung wurde letztendlich von D. Krob bewiesen. Es gibt eine endliche Anzahl von "grundlegenden" Identitäten sowie eine Identität für jede endliche einfache Gruppe . Siehe meine Antwort auf diese Frage für Referenzen.

In umgekehrter Richtung führt die endliche Automatentheorie zu einem elementaren Beweis grundlegender Ergebnisse der kombinatorischen Gruppentheorie wie der Schreier-Formel. Basierend auf Stallings 'wegweisender Arbeit Topology of Finite Graphs .

Auch in umgekehrter Richtung werden automatische Gruppen als endliche Automaten definiert.

Profinite Gruppen spielen auch in der Automatentheorie eine wichtige Rolle. Ein Beispiel ist die Charakterisierung der regulären Sprachen, die von übergangsreversiblen Automaten mit möglicherweise mehreren Anfangs- und Endzuständen erkannt werden.

Für eine sehr schöne Verbindung zwischen kontextfreien Sprachen, Gruppen und Logik siehe den Artikel von David E. Muller und Paul E. Schupp, Kontextfreie Sprachen, Gruppen, Endtheorie, Logik zweiter Ordnung, Kachelprobleme, Zellular Automaten und Vektoradditionssysteme .

Barringtons berühmter Satz reduziert die Berechnung in NC 1 auf die Berechnung iterierter Produkte in der Gruppe S 5 (oder A 5)$^1$$S_5$$A_5$ oder in der Tat jeder nicht lösbaren Gruppe). In Shielding Circuits with Groups von Miles and Viola (2012) gibt es auch eine Verbindung zu leckresistenten Berechnungen .

Bezüglich der Klassifikation der endlichen einfachen Gruppen wird, soweit ich mich erinnere, in einigen Algorithmen für die Gruppenisomorphie implizit ein Problem im Zusammenhang mit der Graphisomorphie verwendet.

$g_1, ..., g_m$$a_1 = b_1, ..., a_n = b_n$$x, y \in \{g_1, ..., g_m\}^*$$\{g_1, ..., g_m\}$$x = y$

Es gibt viele tiefgreifende Ergebnisse, die Bedingungen für Gruppen mit lösbaren Wortproblemen liefern. Es ist auch interessant, die Komplexität der Entscheidung von Wortproblemen zu untersuchen (für Gruppen mit einem entscheidbaren Wortproblem), siehe z . B. hier .

Bei Google fand ich die Arbeit Relativ freie profinite Monoide: eine Einführung und Beispiele in Semigroups, Formal Languages ​​and Groups von Jorge Almeida (englische Übersetzung im Journal of Mathematical Sciences , 144 (2): 3881–3903, 2007) Dieses Thema.