Shuffle on positive varieties of languages.

Antonio Cano Gómez et Jean-Éric Pin



Résumé : Nous montrons qu'il existe une variété positive de langages maximale parmi celles qui ne contiennent pas le langage (ab)*. Cette variété est l'unique variété positive maximale vérifiant les deux conditions suivantes: elle est strictement contenue dans la classe des langages rationnels et elle est fermée pour l'opération de mélange. C'est également l'unique variété positive maximale fermée par morphisme littéral. La variété de monoïdes ordonnés qui correspond à cette variété est constituée par les monoïdes ordonnés vérifiant la propriété suivante: pour chaque couple (a,b) d'éléments mutuellement inverses, et pour chaque élément z de l'idéal minimal du sous monoïde engendré par a et b, (abzab)ω ≤ ab. En particulier, cette variété est décidable.

Abstract : We show there is a unique maximal positive variety of languages which does not contain the language (ab)*. This variety is the unique maximal positive variety satisfying the two following conditions: it is strictly included in the class of rational languages and is closed under the shuffle operation. It is also the unique maximal proper positive variety closed under length preserving morphims. The ordered monoids of the corresponding variety of ordered monoids are characterized as follows: for every pair (a, b) of mutually inverse elements, and for every element z of the minimal ideal of the submonoid generated by a and b, (abzab)ω ≤ ab. In particular this variety is decidable.

PostScript file compressed with gzip, PDF file


Valid HTML 4.01!