Résumé : La fermeture d'un langage rationnel par
commutation [partielle] a été étudiée
dans de nombreux articles. Nous présentons ici quelques
résultats nouveaux sur deux problèmes centraux de ce domaine:
(1) Dans quels cas la fermeture d'un langage rationnel par
commutation [partielle] reste-t-elle rationnelle? (2) Y-a-t-il des
classes de langages robustes et fermées par commutation
[partielle]? Nous montrons que la classe Pol G des polynômes
de langages à groupe est fermée par commutation totale et
aussi par commutation partielle lorsque le complément de I
dans A2 est une relation transitive. Nous donnons aussi une
condition suffisante sur le graphe de I qui assure que la fermeture
d'un langage de Pol G par I-commutation est rationnelle. Nous
donnons une classe très robuste de langages W fermée
par commutation. Cette classe contient Pol G et est décidable.
Elle est aussi fermée par intersection, union, mélange,
concaténation, quotients, morphismes lettre-à-lettre et
inverses de morphismes. Si I est transitive, nous montrons que la
fermeture d'un langage de W par I-commutation est
rationnelle. Les démonstrations sont non triviales et
combinent plusieurs techniques, notamment des arguments combinatoires
à la Ramsey, des propriétés algébriques du
monoïde syntactique, des conditions de finitude sur les semigroupes et
des propriétés de systèmes d'insertion.
Abstract : The closure of a regular language under a
[partial] commutation I has been extensively studied. We present new
advances on two problems of this area: (1) When is the closure of a regular
language under [partial] commutation still regular? (2) Are there any
robust classes of languages closed under [partial] commutation? We show
that the class Pol G of polynomials of group languages is closed
under commutation, and under partial commutation when the complement of
I in A2 is a transitive relation. We also give a
sufficient graph theoretic condition on I to ensure that the closure
of a language of Pol G under I-commutation is regular. We
exhibit a very robust class of languages W which is closed under
commutation. This class contains Pol G and is decidable. It is also
closed under intersection, union, shuffle, concatenation, quotients,
length-decreasing morphisms and inverses of morphisms. If I is
transitive, we show that the closure of a language of W under
I-commutation is regular. The proofs are nontrivial and combine
several advanced techniques, including combinatorial Ramsey type arguments,
algebraic properties of the syntactic monoid, finiteness conditions on
semigroups and properties of insertion systems.