Automatische Gruppe
In der Mathematik ist eine automatische Gruppe eine Gruppe, die durch endliche Automaten beschrieben wird . Das Interesse automatischer Gruppen besteht darin, dass das Wortproblem entscheidbar ist. Dies ist ein Sonderfall einer automatischen Struktur .
Definition
Sei G eine Gruppe, die eine endliche Menge A von erzeugenden Elementen zulässt. Die Gruppe G ist automatisch bezüglich A, wenn es einen Automaten M auf dem Alphabet A und Automaten M x auf dem Alphabet A 2 für alle x in A e {e} gibt, wobei e das neutrale Element ist, so dass:
- die Sprache des Automaten M akzeptiert mindestens einen Vertreter für jedes Element der Gruppe. Genauer gesagt erkennt der Automat für jedes Element g von G mindestens ein endliches Wort auf A, das das Element g repräsentiert;
- Der Automat M a akzeptiert ein Paar ( w 1 , w 2 ) genau dann, wenn w 1 a = w 2 in G und w1 und w 2 von M akzeptiert werden.
Beispiele
Die endlichen Gruppen sind automatisch.
Quadratischer Algorithmus für die Wortaufgabe
Bei einer gegebenen Gruppe G besteht das Wortproblem darin, algorithmisch zu bestimmen, ob zwei Wörter w 1 , w 2 dasselbe Element in der Gruppe darstellen. Bei einer automatischen Gruppe G gibt es einen quadratischen Zeitalgorithmus (in den Längen der beiden zu testenden Wörter), der das Wortproblem löst. Wir können zeigen, dass es einen Algorithmus gibt, der als Eingabe ein Wort w auf A nimmt und in der Zeit O (| w | 2 ) ein Wort von L (M) berechnet, das dasselbe Element darstellt. Der Algorithmus zur Lösung des Wortproblems funktioniert also wie folgt:
- berechne w 1 ' in L (M), was w 1 darstellt ;
- berechne w 2 ' in L (M), was w 2 darstellt ;
- Teste, ob ( w 1 ', w 2 ') in L (M e ) ist.
Hinweise und Referenzen
-
(in) David BA Epstein , MS Paterson , JW Cannon und DF Holt , Textverarbeitung in Gruppen , Boston / London, AK Peters, Ltd.,1 st Januar 1992, 330 S. ( ISBN 0-86720-244-0 , online lesen )
Literaturverzeichnis
-
.
-
Colin M. Campbell , Edmund F. Robertson , Nikola Ruškuc und Richard M. Thomas , „ Automatische Halbgruppen “, Theoretische Informatik , vol. 250, n Knochen 1-2,2001, s. 365–391 ( DOI 10.1016 / S0304-3975 (99) 00151-6 ).
-
Andrew J. Duncan, Edmund Frederick Robertson und Nikola Ruškuc, „ Automatische Monoide und Wechsel von Generatoren “, Mathematical Proceedings of the Cambridge Philosophical Society , vol. 127, n O 3,1999, s. 403–409 ( Mathe-Rezensionen 1713118 , zbMATH 0941.20065 ).
-
Michael Hoffmann und Richard M. Thomas , „ Eine geometrische Charakterisierung automatischer Halbgruppen “, Theoretische Informatik , vol. 369, n Knochen 1-3,2006, s. 300–313 ( DOI 10.1016 / j.tcs.2006.09.008 ).
-
Maryse Pelletier und Jacques Sakarovitch , „ Einfache Multiplikationen II. Erweiterungen rationaler Halbgruppen ”, Information and Computation , vol. 88, n o 1,1990, s. 18–59 ( DOI 10.1016 / 0890-5401 (90) 90003-Z ).
-
Pedro V. Silva und Benjamin Steinberg, „ Eine geometrische Charakterisierung automatischer Monoide “, Quarterly Journal of Mathematics (en) , vol. 55, n O 3,2004, s. 333-356 ( zbMATH 1076.20041 ).
-
Lin Wei, Xiaofeng Wang und Li Deng, „ Geometrische Eigenschaften und asynchron automatische Halbgruppen “, Southeast Asian Bulletin of Mathematics , vol. 34, n o 6,2010, s. 1043–1054 ( zbMATH 1224.20081 ).
Zum Thema passende Artikel