Résumé : La clôture d'un langage rationnel par
commutation ou commutation partielle a été
étudiée de façon intensive. Dans cet article, nous
présentons de nouveaux résultats sur deux problèmes du
domaine.
Problème 1. Dans quels cas la fermeture d'un langage
rationnel par commutation [partielle] est-elle encore rationnelle?
Problème 2. Y-a-t-il des classes robustes de langages
fermées
par commutation [partielle]?
Soit A un alphabet fini, I une relation de commutation
partielles sur A et D son complément dans A x
A. Nos résultats principaux sur les problèmes 1 et 2
peuvent être résumés ainsi:
La classe Pol G (polynômes de langages à groupe)
est fermée par commutation. Si D est transitive, elle est
aussi fermée par I-commutation.
Sous des conditions simples sur le graphe de I, la fermeture
d'un langage de Pol G par I-commutation est rationnelle.
Il existe une classe de langages très robuste W
fermée par commutation. Cette classe, qui contient Pol G,
est fermée par intersection, union, mélange, concatenation,
résiduels, morphismes lettre-à-lettre et inverses de
morphismes. De plus, cette classe est décidable et peut être
définie comme la plus grande variété positive de
langages ne contenant pas (ab)*.
Si I est transitive, la fermeture d'un langage de W par
I-commutation est rationnel.
Les preuves ne sont pas triviales et combinent plusieurs techniques,
notamment des arguments combinatoires de type Ramsey type, les
propriétés algébriques du monoïde syntactique,
des conditions de finitude sur les semigroupes et les properties des
systèmes d'insertion.
Abstract : The closure of a regular language under commutation or
partial commutation has been extensively studied. In this paper, we present
new advances on two problems of this area.
Problem 1. When is the closure of a regular language under [partial]
commutation still regular?
Problem 2. Are there any robust class of languages closed under
[partial] commutation?
Let A be a finite alphabet, I a partial commutation on
A and D be its complement in A x A. Our main
results on Problems 1 and 2 can be summarized as follows:
The class Pol G (polynomials of group languages) is closed
under commutation. If D is transitive, it is also closed under
I-commutation.
Under some simple conditions on the graph of I, the closure of
a language of Pol G under I-commutation is regular.
There is a very robust class of languages W which is closed
under commutation. This class, which contains Pol G, is closed
under intersection, union, shuffle, concatenation, residual, length
preserving morphisms and inverses of morphisms. Further, it is decidable
and can be defined as the largest positive variety of languages not
containing (ab)*.
If I is transitive, 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.