Free group languages : rational versus recognizable
Silva, Pedro V.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004), p. 49-67 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We provide alternative proofs and algorithms for results proved by Sénizergues on rational and recognizable free group languages. We consider two different approaches to the basic problem of deciding recognizability for rational free group languages following two fully independent paths: the symmetrification method (using techniques inspired by the study of inverse automata and inverse monoids) and the right stabilizer method (a general approach generalizable to other classes of groups). Several different algorithmic characterizations of recognizability are obtained, as well as other decidability results.

Publié le : 2004-01-01
DOI : https://doi.org/10.1051/ita:2004003
Classification:  20E05,  20F10,  68Q45 
@article{ITA_2004__38_1_49_0,
     author = {Silva, Pedro V.},
     title = {Free group languages : rational versus recognizable},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {38},
     year = {2004},
     pages = {49-67},
     doi = {10.1051/ita:2004003},
     mrnumber = {2059028},
     zbl = {1082.68071},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2004__38_1_49_0}
}

Silva, Pedro V. Free group languages : rational versus recognizable. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) pp. 49-67. doi : 10.1051/ita:2004003. http://gdmltest.u-ga.fr/item/ITA_2004__38_1_49_0/

[1] J. Berstel, Transductions and Context-free Languages. Teubner (1979). | MR 549481 | Zbl 0424.68040

[2] J.C. Birget, S. Margolis, J. Meakin and P. Weil, PSPACE-completeness of certain algorithmic problems on the subgroups of the free groups, in Proc. ICALP 94. Lect. Notes Comput. Sci. (1994) 274-285. | MR 1334115

[3] M. Hall Jr., The Theory of Groups. AMS Chelsea Publishing (1959). | MR 103215 | Zbl 0919.20001

[4] R.C. Lyndon and P.E. Schupp, Combinatorial Group Theory. Springer-Verlag (1977). | MR 577064 | Zbl 0368.20023

[5] J. Sakarovitch, Syntaxe des langages de Chomsky, essai sur le déterminisme. Ph.D. thesis, Université Paris VII (1979).

[6] J. Sakarovitch, A problem on rational subsets of the free group. Amer. Math. Monthly 91 (1984) 499-501. | MR 1540497 | Zbl 0604.20024

[7] G. Sénizergues, On the rational subsets of the free group. Acta Informatica 33 (1996) 281-296. | MR 1393764 | Zbl 0858.68044

[8] P.V. Silva, On free inverse monoid languages. RAIRO: Theoret. Informatics Appl. 30 (1996) 349-378. | Numdam | MR 1427939 | Zbl 0867.68074

[9] P.V. Silva, Recognizable subsets of a group: finite extensions and the abelian case. Bulletin of the EATCS 77 (2002) 195-215. | MR 1920336 | Zbl 1015.20049