Automatisk gruppe
I matematikk er en automatisk gruppe en gruppe beskrevet med endelige automata . Interessen for automatiske grupper er at ordet problemet er decidable. Dette er et spesielt tilfelle av en automatisk struktur .
Definisjon
La G være en gruppe som innrømmer et endelig sett A med genererende elementer. Gruppen G er automatisk med hensyn til A hvis det finnes en automat M på alfabetet A og automat M x på alfabetet A 2 for alle x i A e {e} hvor e er det nøytrale elementet slik at:
- språket til automaten M godtar minst en representant for hvert element i gruppen. Mer presist, for ethvert element g av G gjenkjenner automaten minst ett endelig ord på A som representerer elementet g;
- Automaton M en aksepterer et par ( w 1 , v 2 ) hvis og bare hvis w 1 a = w 2 i G og w1 og w 2 er akseptert av M.
Eksempler
De endelige gruppene er automatiske.
Kvadratisk algoritme for ordproblemet
Gitt en gruppe G, består ordproblemet i å bestemme algoritmisk om to ord w 1 , w 2 representerer det samme elementet i gruppen. Gitt en automatisk gruppe G, er det en kvadratisk tidsalgoritme (i lengden på de to ordene som skal testes) som løser ordproblemet. Vi kan vise at det eksisterer en algoritme som tar som input et ord w på A og som beregner i tid O (| w | 2 ) et ord på L (M) som representerer det samme elementet. Så algoritmen for å løse ordproblemet fungerer som følger:
- beregne w 1 'i L (M) som representerer w 1 ;
- beregne w 2 'i L (M) som representerer w 2 ;
- Undersøkelse av hvorvidt ( w 1 ' w 2 ') er i L (M e ).
Merknader og referanser
-
(in) David BA Epstein , MS Paterson , JW Cannon og DF Holt , tekstbehandling i grupper , Boston / London, AK Peters, Ltd.,1 st januar 1992, 330 s. ( ISBN 0-86720-244-0 , les online )
Bibliografi
-
.
-
Colin M. Campbell , Edmund F. Robertson , Nikola Ruškuc og Richard M. Thomas , “ Automatic semigroups ”, Theoretical Computer Science , vol. 250, n bein 1-2,2001, s. 365–391 ( DOI 10.1016 / S0304-3975 (99) 00151-6 ).
-
Andrew J. Duncan, Edmund Frederick Robertson og Nikola Ruškuc, “ Automatic monoids and change of generatorators ”, Mathematical Proceedings of the Cambridge Philosophical Society , vol. 127, n o 3,1999, s. 403–409 ( matematiske anmeldelser 1713118 , zbMATH 0941.20065 ).
-
Michael Hoffmann og Richard M. Thomas , “ A geometric characterization of automatic semigroups ”, Theoretical Computer Science , vol. 369, n bein 1-3,2006, s. 300–313 ( DOI 10.1016 / j.tcs.2006.09.008 ).
-
Maryse Pelletier og Jacques Sakarovitch , “ Enkel multiplikasjon II. Utvidelser av rasjonelle semigrupper ”, Information and Computation , vol. 88, n o 1,1990, s. 18–59 ( DOI 10.1016 / 0890-5401 (90) 90003-Z ).
-
Pedro V. Silva og Benjamin Steinberg, “ A geometric characterization of automatic monoids ”, Quarterly Journal of Mathematics (en) , vol. 55, n o 3,2004, s. 333-356 ( zbMATH 1076.20041 ).
-
Lin Wei, Xiaofeng Wang og Li Deng, “ Geometriske egenskaper og asynkront automatiske semigrupper ”, Southeast Asian Bulletin of Mathematics , vol. 34, n o 6,2010, s. 1043–1054 ( zbMATH 1224.20081 ).
Relaterte artikler