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.