Free group languages : rational versus recognizable
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 1, pp. 49-67.

Voir la notice de l'article dans Numdam

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.

DOI : 10.1051/ita:2004003
Classification : 20E05, 20F10, 68Q45
Mots-clés : free group, rational subsets, recognizable subsets 
@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},
     pages = {49--67},
     publisher = {EDP-Sciences},
     volume = {38},
     number = {1},
     year = {2004},
     doi = {10.1051/ita:2004003},
     zbl = {1082.68071},
     mrnumber = {2059028},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2004003/}
}
TY  - JOUR
AU  - Silva, Pedro V.
TI  - Free group languages : rational versus recognizable
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2004
SP  - 49
EP  - 67
VL  - 38
IS  - 1
PB  - EDP-Sciences
UR  - https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2004003/
DO  - 10.1051/ita:2004003
LA  - en
ID  - ITA_2004__38_1_49_0
ER  - 
%0 Journal Article
%A Silva, Pedro V.
%T Free group languages : rational versus recognizable
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2004
%P 49-67
%V 38
%N 1
%I EDP-Sciences
%U https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2004003/
%R 10.1051/ita:2004003
%G en
%F 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) no. 1, pp. 49-67. doi : 10.1051/ita:2004003. https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2004003/

Cité par Sources :