Résumé : Dans les année soixante-dix, on a
proposé différents schémas de classification pour les
langages rationnels, basés sur l'utilisation alternée de
certains opérateurs (union, complémentation, produit et
étoile). Quelques trente ans plus tard, malgré des
progrès sensibles, plusieurs des problèmes originaux sont
toujours ouverts. De plus, leur importance s'est considérablement
accrue au fil des découvertes successives de surprenantes connexions
avec d'autres domaines tels que l'algèbre non commutative, la
théorie des modèles finis, la complexité structurelle
et la topologie. Dans cet article, on résout positivement une
question, posée en 1985, relative aux hiérarchies de
concaténation des langages rationnels, qui sont construites en
alternant opérations booléennes et produit de
concaténation. On établit une connexion algébrique
simple entre la hiérarchie de Straubing-Thérien, dont le
niveau de base est la variété triviale, et la
hiérarchies des groupes, dont le niveau de base est la
variétés des langages à groupe. En nous appuyant sur
un résultat d'Almeida et Steinberg, nous réduisons les
problèmes de décidabilité de la hiérarchie des
groupes à une propriété plus forte que la
décidabilité pour la hiérarchie de la
hiérarchie de Straubing-Thérien.
Abstract : In the seventies, several classification schemes for the
rational languages were proposed, based on the alternate use of certain
operators (union, complementation, product and star). Some thirty years
later, although much progress has been done, several of the original
problems are still open. Furthermore, their significance has grown
considerably over the years, on account of the successive discoveries of
surprising links with other fields, like non commutative algebra, finite
model theory, structural complexity and topology. In this article, we
solve positively a question raised in 1985 about concatenation hierarchies
of rational languages, which are constructed by alternating boolean
operations and concatenation products. We establish a simple algebraic
connection between the Straubing-Thérien hierarchy, whose basis is
the trivial variety, and the group hierarchy, whose basis is the variety of
group languages. Thanks to a recent result of Almeida and Steinberg, this
reduces the decidability problem for the group hierarchy to a property
stronger than decidability for the Straubing-Thérien hierarchy.