Free group languages: Rational versus recognizable
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 38, Issue: 1, page 49-67
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topSilva, Pedro V.. "Free group languages: Rational versus recognizable." RAIRO - Theoretical Informatics and Applications 38.1 (2010): 49-67. <http://eudml.org/doc/92733>.
@article{Silva2010,
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},
keywords = {Free group; rational subsets; recognizable subsets.; recognizability},
language = {eng},
month = {3},
number = {1},
pages = {49-67},
publisher = {EDP Sciences},
title = {Free group languages: Rational versus recognizable},
url = {http://eudml.org/doc/92733},
volume = {38},
year = {2010},
}
TY - JOUR
AU - Silva, Pedro V.
TI - Free group languages: Rational versus recognizable
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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/92733
ER -
References
top- J. Berstel, Transductions and Context-free Languages. Teubner (1979).
- 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.
- M. Hall Jr., The Theory of Groups. AMS Chelsea Publishing (1959).
- R.C. Lyndon and P.E. Schupp, Combinatorial Group Theory. Springer-Verlag (1977).
- J. Sakarovitch, Syntaxe des langages de Chomsky, essai sur le déterminisme. Ph.D. thesis, Université Paris VII (1979).
- J. Sakarovitch, A problem on rational subsets of the free group. Amer. Math. Monthly91 (1984) 499-501.
- G. Sénizergues, On the rational subsets of the free group. Acta Informatica33 (1996) 281-296.
- P.V. Silva, On free inverse monoid languages. RAIRO: Theoret. Informatics Appl.30 (1996) 349-378.
- P.V. Silva, Recognizable subsets of a group: finite extensions and the abelian case. Bulletin of the EATCS77 (2002) 195-215.
Citations in EuDML Documents
topNotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.