On free inverse monoid languages
Pedro V. Silva · RAIRO - Theoretical Informatics and Applications · 1996
This is a study on the class of FIM(X)-languages and its important subfamily consisting of inverse automata languages (i-languages).Both algebraic and combinatorial approaches are used to obtain several results concerning closure operators on (X U X" 1 )* -languages, including a classification of FIM(X)-languages by i-languages.In particular, it is proved thaï the i-closure of a recognizable (X U X -1 )* -language is at most deterministic context-free.Infinité trees are an essential tool in this process, and they are also helpful in producing counterexamples for other closure problems.Applications to X*-languages are also produced, involving particular classes of codes. Résumé. -Nous étudions la classe des langages dans FIM(X) et la sous-famille importante des langages à automates inverses {^langages). Les approches algébrique et combinatoire sont utilisées pour obtenir plusieurs résultats concernant la fermeture par certains opérateurs des langages de {X U X" 1 )* et entre autre une classification des langages des FIM(X)par les i-langages.En particulier, il est prouvé que la i-fermeture des langages reconnaissables de (X U J" 1 )* est au plus algébrique déterministe.Les arbres infinis sont un outil essentiel dans cette démarche et ils sont aussi utiles pour produire des contre-exemples pour les autres propriétés de fermeture.Des applications aux langages de X* sont aussi exhibées dont des clases particulières de codes.