Hiérarchies de concaténation

Jean-Éric Pin

PostScript file compressed with gzip, PDF file



Résumé : On sait qu'il existe une correspondance bijective entre les variétés de langages reconnaissables et les variétés de semigroupes finis. Dans cet article, je définis des hiérarchies de variétés de langages basées sur le produit de concaténation et je donne une description purement algébrique des hiérarchies de semigroupe correspondantes. On retrouve ainsi comme cas particuliers diverses hiérarchies déjà connues. La construction proposée repose sur le résultat suivant: tout langage reconnu par le produit de Schützenberger des monoïdes M0, ..., Mn est dans l'algèbre de Boole engendrée par les langages de la forme Li0a1Li1 ... arLir (0 ≤ i0 < i1 < ... < ir ≤ n) où les ak sont des lettres et les Lik des langages reconnus par Mik (0 ≤ k ≤ r). Enfin je montre un résultat général de décidabilité qui permet de retrouver un résultat de théorie des semigroupes: étant donné un semigroupe fini S et un entier n, on peut décider si S divise un produit en couronne de n demi-treillis.


Abstract : Is it well-known that there exists a one-to-one correspondence between varieties of recognizable languages and varieties of finite semigroups. New hierarchies of varieties of languages (based on the concatenation product) are defined and an algebraic description of the corresponding hierarchies of varieties of semigroups is given. Various well-known hierarchies are obtained as particular cases. The construction is based on the following result: if a language L is recognized by the Schützenberger product of the monoids M0, ..., Mn, then L belongs to the Boolean closure of the set of languages of the form Li0a1Li1 ... arLir (0 ≤ i0 < i1 < ... < ir ≤ n) where the ak are letters and the Lik are recognized by Mik (0 ≤ k ≤ r). Decidability and inclusion problems are also discussed.

PostScript file compressed with gzip, PDF file


Valid HTML 4.01!