Free group languages : rational versus recognizable

Pedro V. Silva

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2004)

  • Volume: 38, Issue: 1, page 49-67
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Silva, Pedro V.. "Free group languages : rational versus recognizable." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 38.1 (2004): 49-67. <http://eudml.org/doc/245649>.

@article{Silva2004,
abstract = {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.},
author = {Silva, Pedro V.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {free group; rational subsets; recognizable subsets; recognizability},
language = {eng},
number = {1},
pages = {49-67},
publisher = {EDP-Sciences},
title = {Free group languages : rational versus recognizable},
url = {http://eudml.org/doc/245649},
volume = {38},
year = {2004},
}

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
PB - EDP-Sciences
VL - 38
IS - 1
SP - 49
EP - 67
AB - 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.
LA - eng
KW - free group; rational subsets; recognizable subsets; recognizability
UR - http://eudml.org/doc/245649
ER -

References

top
  1. [1] J. Berstel, Transductions and Context-free Languages. Teubner (1979). Zbl0424.68040MR549481
  2. [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. MR1334115
  3. [3] M. Hall Jr., The Theory of Groups. AMS Chelsea Publishing (1959). Zbl0919.20001MR103215
  4. [4] R.C. Lyndon and P.E. Schupp, Combinatorial Group Theory. Springer-Verlag (1977). Zbl0368.20023MR577064
  5. [5] J. Sakarovitch, Syntaxe des langages de Chomsky, essai sur le déterminisme. Ph.D. thesis, Université Paris VII (1979). 
  6. [6] J. Sakarovitch, A problem on rational subsets of the free group. Amer. Math. Monthly 91 (1984) 499-501. Zbl0604.20024MR1540497
  7. [7] G. Sénizergues, On the rational subsets of the free group. Acta Informatica 33 (1996) 281-296. Zbl0858.68044MR1393764
  8. [8] P.V. Silva, On free inverse monoid languages. RAIRO: Theoret. Informatics Appl. 30 (1996) 349-378. Zbl0867.68074MR1427939
  9. [9] P.V. Silva, Recognizable subsets of a group: finite extensions and the abelian case. Bulletin of the EATCS 77 (2002) 195-215. Zbl1015.20049MR1920336

NotesEmbed ?

top

You must be logged in to post comments.