Théorème des variétés d'Eilenberg

En informatique théorique, et notamment en théorie de langages rationnels, le théorème des variétés d'Eilenberg, aussi appelé théorème des variétés d'Eilenberg et Schützenberger^[1] d'après leurs découvreurs Samuel Eilenberg et Marcel-Paul Schützenberger, établit une correspondance entre variétés de langages formels rationnels et (pseudo-) variétés de monoïdes finis. Ce théorème des variétés, établi dans les années 1970 et dont l'exposé systématique occupe une large part du volume B du traité d'Eilenberg^[2], constitue la base d'une théorie algébrique des langages rationnels qui s'est développée considérablement depuis. Il fournit le cadre qui permet de mettre en relation les propriétés algébriques de monoïdes et les propriétés combinatoires des langages rationnels.

Un exemple célèbre de cette correspondance, établi par Schützenberger en 1965, donc avant la formulation du théorème des variétés, est le théorème de qui caractérise les langages rationnels « sans étoile » par la propriété que leur monoïde syntaxique n'a que des « sous-groupes triviaux », en d'autres termes, les ${\mathcal {H}}$ -classes qui sont des groupes sont des singletons (monoïdes apériodiques finis). Un autre résultat de cette nature est dû à Imre Simon^[3] : un langage rationnel est testable par morceaux si et seulement si son monoïde syntaxique est ${\mathcal {J}}$ -trivial, c'est-à-dire sa relation ${\mathcal {J}}$ est l'identité. Il faut noter tout de suite que le théorème des variétés ne généralise pas ces résultats, et en particulier n'en fournit pas de preuve, mais permet de bien les formuler dans un cadre approprié.

La notion de variété de monoïdes finis utilisée dans l'énoncé diffère de la notion classique de variété d'algèbres par sa définition et ses propriétés : une variété de monoïdes finis est définie comme étant notamment fermées par produit direct fini, alors qu'une variété d'algèbres est défini par des équations, et c'est le théorème HSP de Birkhoff qui établit l'équivalence entre définition par équations et fermeture par produit direct quelconque. Pour marquer cette différence, les variétés de monoïdes finis ont été appelées pseudo-variétés. Une autre différence est que les variétés de monoïdes finis ne sont pas toujours définissables par des équations^[4]. L'étude des équations a conduit d'ailleurs à une formulation plus générale d'équations.


Samuel Eilenberg	Marcel-Paul Schützenberger

Variété de langages formels

Pour éviter des paradoxes de la théorie des ensembles, on se fixe ici un ensemble infini dénombrable noté $\Sigma$ , et on entend par alphabet toute partie finie de $\Sigma$ . Une classe de langages formels est une famille ${\mathcal {F}}$ de langages, chacun sur un alphabet, donc sur une partie finie de $\Sigma$ . On note ${\mathcal {F}}(A^{*})$ et ${\mathcal {F}}(A^{+})$ les langages de la famille sur l'alphabet $A$ , donc qui sont contenues dans $A^{*}$ et dans $A^{+}$ respectivement. On convient qui si $B$ est un alphabet en bijection avec $A$ , alors ${\mathcal {F}}(B^{*})$ et ${\mathcal {F}}(A^{*})$ sont égales à la bijection près.

Définition

Il y a en fait deux variantes de la définition, les $*$ -variétés et les $+$ -variétés.

Une $*$ -variété de langages est une famille de langages ${\mathcal {V}}$ telle que

pour tout alphabet $A$ , la famille ${\mathcal {V}}(A^{*})$ est une algèbre de Boole ;
pour tout morphisme de monoïdes $f:A^{*}\to B^{*}$ , si $X\in {\mathcal {V}}(B^{*})$ alors $f^{-1}(X)\in {\mathcal {V}}(A^{*})$ ;
pour tout alphabet $A$ , si $X\in {\mathcal {V}}(A^{*})$ , alors $u^{-1}X\in {\mathcal {V}}(A^{*})$ et $Xu^{-1}\in {\mathcal {V}}(A^{*})$ pour tout mot $u$ de $A^{*}$ .

Une $+$ -variété de langages est une famille de langages ${\mathcal {V}}$ telle que

pour tout alphabet $A$ , la famille ${\mathcal {V}}(A^{+})$ est une algèbre de Boole ;
pour tout morphisme de demi-groupes $f:A^{+}\to B^{+}$ , si $X\in {\mathcal {V}}(B^{+})$ alors $f^{-1}(X)\in {\mathcal {V}}(A^{+})$ ;
pour tout alphabet $A$ , si $X\in {\mathcal {V}}(A^{+})$ , alors $u^{-1}X\in {\mathcal {V}}(A^{+})$ et $Xu^{-1}\in {\mathcal {V}}(A^{+})$ pour tout mot $u$ de $A^{+}$ .

La première condition implique que la famille est fermée par union, complément, donc par intersection. La deuxième condition dit que la famille est fermée par image homomorphe inverse, et la troisième par quotient gauche et quotient droit par un mot.

La différence dans les deux définitions se situe dans la notion de morphisme. Un morphisme de demi-groupes est non effaçant ou croissant : l'image d'un mot est de longueur au moins égale à celle du mot de départ. Il en résulte notamment que l'ensemble $f^{-1}(X)$ est fini si $X$ est fini. Ceci n'est pas le cas pour les morphismes de monoïdes.

Exemples

La famille de tous les langages rationnels. C'est la plus grande variété.
La plus petite $*$ -variété est composée du langage vide et du langage $A^{*}$ pour tout alphabet $A$ . La plus petite $+$ -variété est composée du langage vide et du langage $A^{+}$ pour tout alphabet $A$ .
La famille des langages finis ou cofinis (compléments de langages finis) est une $+$ -variété. Cette famille n'est pas une $*$ -variété parce que l'image homomorphe inverse d'une partie finie peut être ni finie ni cofinie si le morphisme est effaçant.
La famille des langages rationnels sans étoile.
La famille des langages testables par morceaux. C'est la famille telle que ${\mathcal {V}}(A^{*})$ est l'algèbre de Boole engendrée par les langages $A^{*}a_{1}A^{*}a_{2}\cdots a_{n}A^{*}$ , où les $a_{i}$ sont des lettres.
La famille des langages localement testables. C'est la famille telle que ${\mathcal {V}}(A^{*})$ est l'algèbre de Boole engendrée par les langages $uA^{*}$ , $A^{*}v$ , $A^{*}wA^{*}$ pour des mots $u$ , $v$ , $w$ .
La famille des langages localement triviaux. C'est la $+$ -variété telle que ${\mathcal {V}}(A^{+})$ est l'algèbre de Boole engendrée par les langages $XA^{*}Y\cup Z$ , où $X$ , $Y$ , $Z$ sont des parties finies de $A^{+}$ .

Variété de monoïdes finis

Définition

Une classe $\mathbf {V}$ de monoïdes est une variété de monoïdes si elle a les propriétés suivantes:

Si $S$ est dans $\mathbf {V}$ , et si $T$ est un sous-monoïde de $S$ , alors $T$ est dans $\mathbf {V}$ .
Si $S$ est dans $\mathbf {V}$ , et si $T$ est un quotient de $S$ , alors $T$ est dans $\mathbf {V}$ .
Si $S_{1},\ldots ,S_{n}$ sont dans $\mathbf {V}$ , alors leur produit direct $S_{1}\times \cdots \times S_{n}$ est dans $\mathbf {V}$

Il faut noter que la dernière condition vaut aussi pour $n=0$ , ce qui plus simplement s'exprime en disant que le monoïdes réduit à un seul élément 1 est dans $\mathbf {V}$ .

On définit de la même manière une variété de demi-groupes, et des variétés de monoïdes ou de demi-groupes avec des propriétés additionnelles, comme les variétés de monoïdes ordonnées.

Exemples

Les exemples suivants sont des variétés de monoïdes.

La famille de tous les monoïdes finis. C'est la plus grande variété.
La famille formée du monoïde 1. C'est la plus petite variété.
La famille des demi-groupes nilpotents. Un demi-groupe $M$ est nilpotent s'il possède un zéro, c'est-à-dire un élément $0$ tel que $s0=0s=0$ pour tout $s$ dans $S$ , et s'il existe un entier $n$ tel que tout produit de $n$ éléments de $M$ est égal à $0$ .
La famille des monoïdes qui sont des demi-treillis. Un demi-treillis est un demi-groupe commutatif dont tous les éléments sont idempotents.
La famille des monoïdes commutatifs finis.
La famille des monoïdes apériodiques finis.
La famille des groupes finis.
La famille des monoïdes ${\mathcal {J}}$ -triviaux finis, c'est-à-dire tels que la relation de Green ${\mathcal {J}}$ est l'égalité.
La famille des monoïdes localement triviaux.
La famille des monoïdes localement idempotents et commutatifs.

Les deux derniers exemples font intervenir des propriétés de monoïdes ou de demi-groupes que l'on qualifie de locales, au sens précis suivant : on dit qu'un demi-groupe $S$ vérifie localement une propriété $P$ si, pour tout idempotent $e$ de $S$ , le demi-groupe $eSe$ vérifie la propriété $P$ . Par exemple, une monoïde (ou demi-groupe) $S$ est localement trivial si $eSe=e$ .

Variété engendrée par une famille de monoïdes

Soit $\mathbf {C}$ une classe de monoïdes ou de demi-groupes. La variété engendrée par $\mathbf {C}$ est la plus petite variété de monoïdes ou de demi-groupes contenant $\mathbf {C}$ . C'est aussi l'intersection des variétés de monoïdes ou de demi-groupes contenant $\mathbf {C}$ .

Une façon concrète de voir la variété engendrée par $\mathbf {C}$ est : c'est l'ensemble des images homomorphes des sous-monoïdes ou de demi-groupes de produits directs d'éléments de $\mathbf {C}$ . On dit qu'un demi-groupe $M$ divise un demi-groupe $N$ si $M$ est l'image homomorphe d'un sous-demi-groupe de $N$ . Ainsi, un demi-groupe appartient à la variété engendrée par $\mathbf {C}$ si et seulement s'il divise un produit direct d'éléments de $\mathbf {C}$ .

Théorème des variétés

Le théorème des variétés met en correspondance les variétés de langages et les variétés de monoïdes (demi-groupes). On considère d'une part l'application

{\mathcal {V}}\mapsto \mathbf {V}

qui associe à une $*$ -variété ( $+$ -variété) de langages ${\mathcal {V}}$ la variété de monoïdes (demi-groupes) $\mathbf {V}$ engendrée par les monoïdes (demi-groupes) syntaxiques des langages de ${\mathcal {V}}$ .

D'autre part, on considère l'application

\mathbf {V} \mapsto {\mathcal {V}}

qui associe à la variété de monoïdes (de demi-groupes) $\mathbf {V}$ la $*$ -variété ( $+$ -variété) des langages ${\mathcal {V}}$ dont le monoïde (demi-groupe) syntaxique est dans $\mathbf {V}$ .

Énoncé

Théorème des variétés (Eilenberg & Schützenberger) — Les correspondances

{\mathcal {V}}\mapsto \mathbf {V}

et

\mathbf {V} \mapsto {\mathcal {V}}

sont des bijections réciproques l'une de l'autre.

Cet énoncé en recouvre en fait deux : le premier met en bijection les $+$ -variétés et les variétés de demi-groupes, l'autre les $*$ -variétés et les variétés de monoïdes.

Exemples

Nous groupons en un tableau les variétés de langages et de monoïdes (demi-groupes) qui se correspondent. D'autres exemples sont donnés dans (Pin 1995) et (Pin 2012) :

Variétés de langages rationnels et de monoïdes finis
Langages	Monoïdes
Tous les langages	Tous les monoïdes
Langage vide et son complément	Monoïde singleton
Langages engendrés par $L(a,k,n)$ ⁽¹⁾	Groupes commutatifs
Langages engendrés par $L(a,k)$ ⁽²⁾	Monoïdes commutatifs apériodiques
Langages engendrés par $L(a,k,n)$ et $L(a,k)$	Monoïdes commutatifs
Langages sans étoile	Monoïdes apériodique
Langages engendrés par $A^{}aA^{}$	Monoïdes demi-treillis (idempotents commutatifs)
Langages engendrés par $A^{}a_{1}A^{}a_{2}\cdots a_{n}A^{*}$	Monoïdes ${\mathcal {J}}$ -triviaux
Langages finis et cofinis	Demi-groupes nilpotents
Langages localement testables	Demi-groupes localement idempotents et commutatifs
Langages localement triviaux	Demi-groupes localement triviaux

(1) Pour tout alphabet $A$ , on pose : $L(a,k,n)=\{u\in A^{*}\mid |u|_{a}\equiv k{\bmod {n}}\}$ , avec $a$ une lettre et $k<n$ ; $|u|_{a}$ dénote le nombre d'occurrences de la lettre $a$ dans le mot $u$ .

(2) Pour tout alphabet $A$ , on pose : $L(a,k)=\{u\in A^{*}\mid |u|_{a}=k\}$ , avec $a$ une lettre.

Le théorème des variétés ne prouve pas la correspondance dans chacun des exemples; il prouve seulement l'existence et la correction des deux correspondances de l'énoncé. chaque exemple particulier demande une preuve particulière, et elles sont souvent bien plus difficiles que l'énoncé général.

Équations

On peut associer à une variété de monoïdes des équations qui la définissent. Considérons d'abord la version développée par Eilenberg et Schützenberger.

Soit $\Sigma$ un alphabet de variables. Étant donné deux mots $x$ et $y$ sur $\Sigma$ , on dit qu'un monoïde $M$ satisfait l'équation $x=y$ si, pour tout morphisme $f:\Sigma ^{*}\to M$ , on a $f(x)=f(y)$ . Ainsi, un monoïde commutatif est un monoïde qui satisfait l'équation $xy=yx$ . Il est facile de vérifier que la famille des monoïdes qui satisfont une équation $x=y$ forment une variété. Plus généralement, étant donné une suite $x_{n}=y_{n}$ d'équations pour $n\geq 1$ , la famille des monoïdes qui satisfont ces équations est encore une variété.

Exemples

La variété des monoïdes commutatifs est donnée par l'équation $xy=yx$ .
La variété des demi-treillis (monoïdes idempotents commutatifs) est donnée par les équations $x^{2}=x$ et $xy=yx$ .

Énoncé

Étant donné une suite $x_{n}=y_{n}$ d'équations pour $n\geq 1$ , on dit qu'un monoïde $M$ vérifie ultimement ces équations s'il vérifie ces équations à partir d'un certain entier $N$ . La famille des monoïdes qui vérifient ultimement une suite d'équations est encore une variété. Par exemple, les monoïdes apériodiques vérifient ultimement les équations $x^{n}=x^{n+1}$ .

Théorème — Toute variété de monoïdes est définie ultimement par une suite d'équations.

Une formulation plus contemporaine, et plus riche en résultats, fait appel à des considérations topologiques.

Notes et références

↑ Par exemple (Lawson 2003), alors que (Pin 1995) parle simplement du théorème d'Eilenberg. Eilenberg lui-même, dans son livre, reconnaît les contributions de Schützenberger, notamment pour la formulation par équations.
↑ (Eilenberg 1976), chapitres V, VII et VIII, sans compter les applications.
↑ (Simon 1975)
↑ L'objectif de l'article (Eilenberg et Schützenberger 1976) est de décrire cette relation.

Littérature

Traités

(en) Gracinda M. S. Gomes, Jean-Éric Pin et Pedro V. Silva (éditeurs), Semigroups, algorithms, automata, and languages : : Coimbra, Portugal, May-July 2001, World Scientific, 2002, 515 p. (ISBN 978-981-238-099-9, présentation en ligne)

(en) Mark V. Lawson, Finite Automata, Boca Raton/London/New York etc., Chapman and Hall/CRC, 2003, 320 p. (ISBN 1-58488-255-7, présentation en ligne)

(en) Jean-Éric Pin, Varieties of formal languages, Plenum Publishing Corp., coll. « Foundations of Computer Science », 1986, x+138 (ISBN 0-306-42294-8, MR 89a:68125)

Jean-Éric Pin, « Finite semigroups and recognizable languages: an introduction », dans J. Fountain (éditeur), Semigroups, Formal Languages and Groups : York, 1993, Dordrecht, Kluwer Academic Publishers, coll. « NATO Advanced Study Institute Series C » (n^o 466), 1995 (lire en ligne), p. 1-32

(en) Jean-Éric Pin, Mathematical Foundations of Automata Theory, Support de cours du Master Parisien de Recherche en Informatique (MPRI), 2012, 310 p. (lire en ligne), p. 95-124

Sources

(en) Samuel Eilenberg, Automata, Languages and Machines, Vol. B, Academic Press, coll. « Pure and Applied Mathematics » (n^o 59), 1976, xiii+387 (MR 0530383)

(en) Samuel Eilenberg et Marcel-Paul Schützenberger, « On pseudovarieties », Advances in Math., vol. 19, n^o 3,‎ 1976, p. 413–418 (DOI 10.1016/0001-8708(76)90029-3, MR 0401604)

(en) Marcel-Paul Schützenberger, « On finite monoids having only trivial subgroups », Information and Control, vol. 8, n^o 2,‎ 1965, p. 190-194

Imre Simon, « Piecewise testable events », dans H. Brakhage (éditeur), Proceedings 2nd GI Conference, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 33), 1975, p. 214-222

Articles connexes

[1] Par exemple (Lawson 2003), alors que (Pin 1995) parle simplement du théorème d'Eilenberg. Eilenberg lui-même, dans son livre, reconnaît les contributions de Schützenberger, notamment pour la formulation par équations.

[2] (Eilenberg 1976), chapitres V, VII et VIII, sans compter les applications.

[3] (Simon 1975)

[4] L'objectif de l'article (Eilenberg et Schützenberger 1976) est de décrire cette relation.

[1]

[2]

[3]

[4]

v · m Automates finis et langages réguliers
Articles généraux	Théorie des automates Automate fini Machine abstraite
Automates finis	Automate fini déterministe Automate fini inambigu Automate fini non déterministe Construction par sous-ensembles Automate sur les mots infinis
Automates finis particuliers	Automate alternant Automate bidirectionnel Automate pondéré Automate probabiliste Automate quantique Automate temporisé Automate de Büchi Automate de Muller Modèle de Markov caché Système de transition d'états Structure de Kripke Machine à états abstraits Machine de Mealy Machine de Moore Transducteur fini Automate séquentiel
Langages réguliers	Langage rationnel Langage sans étoile Langage local Langage congruentiel Langage stochastique Lemme de l'étoile Lemme d'Arden ω-langage rationnel
Des automates aux langages	Expression régulière Algorithme de Conway Algorithme de McNaughton et Yamada Méthode de Brzozowski et McCluskey
Des langages aux automates	Dérivée de Brzozowski Algorithme de Thompson Construction de Glushkov Complexité en états
Minimisation	Théorème de Myhill-Nerode Équivalence de Nerode Minimisation d'un automate fini déterministe Algorithme de Moore Algorithme de Brzozowski Algorithme de Hopcroft
Équivalences	Théorème de Kleene Étoile de Kleene Monoïde syntaxique Théorème des variétés d'Eilenberg

v · m Informatique théorique
Codage	Codage de l'information Compression de données Chiffrement Cryptanalyse Cryptographie Théorie de l'information
Modèles de calcul	Calculabilité Décidabilité et indécidabilité Ensemble récursif Problème de l'arrêt Ensemble récursivement énumérable Machine de Turing Thèse de Church Automate cellulaire Réseau de neurones artificiels Réduction polynomiale Problème NP-complet Principe de Church-Turing-Deutsch
Algorithmique	Algorithmique Algorithme glouton Algorithme probabiliste Algorithme génétique Complexité algorithmique Analyse d'algorithme Diviser pour régner Heuristique Programmation dynamique Géométrie algorithmique Algorithmes de tri Algorithmique du texte Exploration de données Science des données Apprentissage profond Test de primalité Structure de données Arbre enraciné Concurrence Parallélisme
Syntaxe	Réécriture Compilation Expression régulière Grammaire formelle Langage rationnel Ensemble rationnel Théorie des langages Théorie des automates Automate fini Automate sur les mots infinis Automate d'arbres Automate à pile Hiérarchie de Chomsky Linguistique informatique
Sémantique	Interprétation abstraite Méthodes formelles Vérification de modèles Sémantique des langages de programmation Sémantique dénotationnelle Sémantique axiomatique Sémantique opérationnelle
Logique mathématique	Assistant de preuve Calcul des prédicats Correspondance de Curry-Howard Fonction récursive Lambda-calcul Théorèmes d'incomplétude de Gödel Théorie des types
Mathématiques discrètes	Combinatoire Algorithme du simplexe Optimisation combinatoire Théorie des graphes Algorithmes de la théorie des graphes Recherche opérationnelle Théorie de la décision Analyse numérique