Jean Berstel, Luc Boasson, Olivier Carton, Jean-Éric Pin, Antonio
Restivo
Résumé : Le produit de mélange (ou shuffle) des
langages est de plus en plus étudié, car il constitue un
outil standard pour la modélisation des algèbres de
processus. Il demeure en même temps l'une des opérations les
plus mystérieuses sur les langages réguliers. Antonio
Restivo a lancé le défi de caracteriser la plus petite
classe de langages contenant les singletons et fermé pour les
opérations booléennes, le produit et le produit de
mélange. Nous présentons une série de résultats
partiels sur ce problème, qui demeure cependant largement ouvert.
Nous étudions par ailleurs des classes de langages plus petites,
notamment la plus petite classe contenant les langages réduits
à un mot de longueur 2 et qui est fermée pour les
opérations booléennes et le produit de mélange par une
lettre (resp. par une lettre et par l'étoile d'une lettre). Les
techniques de preuve sont de nature à la fois algébriques et
combinatoires.
Abstract : There is an increasing interest in the shuffle product on
formal languages, mainly because it is a standard tool for modeling process
algebras. It still remains a mysterious operation on regular languages.
Antonio Restivo proposed as a challenge to characterize the
smallest class of languages containing the singletons and closed under
Boolean operations, product and shuffle. This problem is still widely
open, but we present some partial results on it. We also study some
other smaller classes, including the smallest class containing the
languages composed of a single word of length 2 which is closed under
Boolean operations and shuffle by a letter (resp. shuffle by a letter
and by the star of a letter). The proof techniques have both an algebraic
and a combinatorial flavour.