When does partial commutative closure preserve regularity?

Antonio Cano Gómez, Giovanna Guaiana et Jean-Éric Pin

PostScript file compressed with gzip, PDF file


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:
  1. 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.
  2. Sous des conditions simples sur le graphe de I, la fermeture d'un langage de Pol G par I-commutation est rationnelle.
  3. 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)*.
  4. 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:
  1. The class Pol G (polynomials of group languages) is closed under commutation. If D is transitive, it is also closed under I-commutation.
  2. Under some simple conditions on the graph of I, the closure of a language of Pol G under I-commutation is regular.
  3. 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)*.
  4. 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.

PostScript file compressed with gzip, PDF file

Valid HTML 4.01!