A robust class of regular languages

Antonio Cano Gómez et Jean-Éric Pin

PostScript file compressed with gzip, PDF file


Résumé : Nous présentons dans cet article de synthèse les résultats connus et les problèmes ouverts relatifs à une sous-classe propre des langages rationnels. Cette classe, notée W, est particulièrement robuste, puisqu'elle est fermée par union, intersection, produit, mélange, quotients à droite et à gauche, inverse de morphismes, morphismes lettre-à-lettre et fermeture commutative. Elle peut être définie comme la plus grande variété positive de langages ne contenant pas le langage (ab)*. Elle admet une caractérisation algébrique non triviale en termes de monoïdes ordonnés finis, ce qui permet de montrer que W est décidable: étant donné un langage rationnel, on peut décider de manière effective s'il appartient à W. Finalement, nous proposons deux problèmes ouverts relatifs à cette classe: trouver une description constructive et une caractérisation logique de W.


Abstract : In this survey paper, we present known results and open questions on a proper subclass of the class of regular languages. This class, denoted by W, is especially robust: it is closed under union, intersection, product, shuffle, left and right quotients, inverse of morphisms, length preserving morphisms and commutative closure. It can be defined as the largest positive variety of languages not containing the language (ab)*. It admits a nontrivial algebraic characterization in terms of finite ordered monoids, which implies that W is decidable: given a regular language, one can effectively decide whether or not it belongs to W. We propose as a challenge to find a constructive description and a logical characterization of W.

PostScript file compressed with gzip, PDF file

Valid HTML 4.01!