Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-27T20:25:55.886Z Has data issue: false hasContentIssue false
  • English
  • Français

Free group languages: Rational versus recognizable

Published online by Cambridge University Press:  15 March 2004

Pedro V. Silva
Pedro V. Silva*
Affiliation:
Centro de Matemática, Faculdade de Ciências, Universidade do Porto, R. do Campo Alegre, 687, 4169-007 Porto, Portugal; [email protected].
Get access

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.

Keywords

Free grouprational subsetsrecognizable subsets.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 38 , Issue 1 , January 2004 , pp. 49 - 67
Copyright
© EDP Sciences, 2004

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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).
Sakarovitch, J., A problem on rational subsets of the free group. Amer. Math. Monthly 91 (1984) 499-501. CrossRef
Sénizergues, G., On the rational subsets of the free group. Acta Informatica 33 (1996) 281-296. CrossRef
Silva, P.V., On free inverse monoid languages. RAIRO: Theoret. Informatics Appl. 30 (1996) 349-378.
Silva, P.V., Recognizable subsets of a group: finite extensions and the abelian case. Bulletin of the EATCS 77 (2002) 195-215.