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 ${\displaystyle {\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 ${\displaystyle {\mathcal {J}}}$-trivial, c'est-à-dire sa relation ${\displaystyle {\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é ${\displaystyle \Sigma }$, et on entend par alphabet toute partie finie de ${\displaystyle \Sigma }$. Une classe de langages formels est une famille ${\displaystyle {\mathcal {F}}}$ de langages, chacun sur un alphabet, donc sur une partie finie de ${\displaystyle \Sigma }$. On note ${\displaystyle {\mathcal {F}}(A^{*})}$ et ${\displaystyle {\mathcal {F}}(A^{+})}$ les langages de la famille sur l'alphabet ${\displaystyle A}$, donc qui sont contenues dans ${\displaystyle A^{*}}$ et dans ${\displaystyle A^{+}}$ respectivement. On convient qui si ${\displaystyle B}$ est un alphabet en bijection avec ${\displaystyle A}$, alors ${\displaystyle {\mathcal {F}}(B^{*})}$ et ${\displaystyle {\mathcal {F}}(A^{*})}$ sont égales à la bijection près.

Définition

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

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

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

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

1. pour tout alphabet ${\displaystyle A}$, la famille ${\displaystyle {\mathcal {V}}(A^{+})}$ est une algèbre de Boole ;
2. pour tout morphisme de demi-groupes ${\displaystyle f:A^{+}\to B^{+}}$, si ${\displaystyle X\in {\mathcal {V}}(B^{+})}$ alors ${\displaystyle f^{-1}(X)\in {\mathcal {V}}(A^{+})}$ ;
3. pour tout alphabet ${\displaystyle A}$, si ${\displaystyle X\in {\mathcal {V}}(A^{+})}$, alors ${\displaystyle u^{-1}X\in {\mathcal {V}}(A^{+})}$ et ${\displaystyle Xu^{-1}\in {\mathcal {V}}(A^{+})}$ pour tout mot ${\displaystyle u}$ de ${\displaystyle 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 ${\displaystyle f^{-1}(X)}$ est fini si ${\displaystyle X}$ est fini. Ceci n'est pas le cas pour les morphismes de monoïdes.

Exemples

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

Variété de monoïdes finis

Définition

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

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

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

1. La famille de tous les monoïdes finis. C'est la plus grande variété.
2. La famille formée du monoïde 1. C'est la plus petite variété.
3. La famille des demi-groupes nilpotents. Un demi-groupe ${\displaystyle M}$ est nilpotent s'il possède un zéro, c'est-à-dire un élément ${\displaystyle 0}$ tel que ${\displaystyle s0=0s=0}$ pour tout ${\displaystyle s}$ dans ${\displaystyle S}$, et s'il existe un entier ${\displaystyle n}$ tel que tout produit de ${\displaystyle n}$ éléments de ${\displaystyle M}$ est égal à ${\displaystyle 0}$.
4. 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.
5. La famille des monoïdes commutatifs finis.
6. La famille des monoïdes apériodiques finis.
7. La famille des groupes finis.
8. La famille des monoïdes ${\displaystyle {\mathcal {J}}}$-triviaux finis, c'est-à-dire tels que la relation de Green ${\displaystyle {\mathcal {J}}}$ est l'égalité.
9. La famille des monoïdes localement triviaux.
10. 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 ${\displaystyle S}$ vérifie localement une propriété ${\displaystyle P}$ si, pour tout idempotent ${\displaystyle e}$ de ${\displaystyle S}$, le demi-groupe ${\displaystyle eSe}$ vérifie la propriété ${\displaystyle P}$. Par exemple, une monoïde (ou demi-groupe) ${\displaystyle S}$ est localement trivial si ${\displaystyle eSe=e}$.

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

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

Une façon concrète de voir la variété engendrée par ${\displaystyle \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 ${\displaystyle \mathbf {C} }$. On dit qu'un demi-groupe ${\displaystyle M}$ divise un demi-groupe ${\displaystyle N}$ si ${\displaystyle M}$ est l'image homomorphe d'un sous-demi-groupe de ${\displaystyle N}$. Ainsi, un demi-groupe appartient à la variété engendrée par ${\displaystyle \mathbf {C} }$ si et seulement s'il divise un produit direct d'éléments de ${\displaystyle \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

${\displaystyle {\mathcal {V}}\mapsto \mathbf {V} }$

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

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

${\displaystyle \mathbf {V} \mapsto {\mathcal {V}}}$

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

Énoncé

Cet énoncé en recouvre en fait deux : le premier met en bijection les ${\displaystyle +}$-variétés et les variétés de demi-groupes, l'autre les ${\displaystyle *}$-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 ${\displaystyle L(a,k,n)}$ (1)	Groupes commutatifs
Langages engendrés par ${\displaystyle L(a,k)}$ (2)	Monoïdes commutatifs apériodiques
Langages engendrés par ${\displaystyle L(a,k,n)}$ et ${\displaystyle L(a,k)}$	Monoïdes commutatifs
Langages sans étoile	Monoïdes apériodique
Langages engendrés par ${\displaystyle A^{*}aA^{*}}$	Monoïdes demi-treillis (idempotents commutatifs)
Langages engendrés par ${\displaystyle A^{*}a_{1}A^{*}a_{2}\cdots a_{n}A^{*}}$	Monoïdes ${\displaystyle {\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 ${\displaystyle A}$, on pose : ${\displaystyle L(a,k,n)=\{u\in A^{*}\mid |u|_{a}\equiv k{\bmod {n}}\}}$, avec ${\displaystyle a}$ une lettre et ${\displaystyle k<n}$; ${\displaystyle |u|_{a}}$ dénote le nombre d'occurrences de la lettre ${\displaystyle a}$ dans le mot ${\displaystyle u}$.

(2) Pour tout alphabet ${\displaystyle A}$, on pose : ${\displaystyle L(a,k)=\{u\in A^{*}\mid |u|_{a}=k\}}$, avec ${\displaystyle 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 ${\displaystyle \Sigma }$ un alphabet de variables. Étant donné deux mots ${\displaystyle x}$ et ${\displaystyle y}$ sur ${\displaystyle \Sigma }$, on dit qu'un monoïde ${\displaystyle M}$ satisfait l'équation ${\displaystyle x=y}$ si, pour tout morphisme ${\displaystyle f:\Sigma ^{*}\to M}$, on a ${\displaystyle f(x)=f(y)}$. Ainsi, un monoïde commutatif est un monoïde qui satisfait l'équation ${\displaystyle xy=yx}$. Il est facile de vérifier que la famille des monoïdes qui satisfont une équation ${\displaystyle x=y}$ forment une variété. Plus généralement, étant donné une suite ${\displaystyle x_{n}=y_{n}}$ d'équations pour ${\displaystyle 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 ${\displaystyle xy=yx}$.
• La variété des demi-treillis (monoïdes idempotents commutatifs) est donnée par les équations ${\displaystyle x^{2}=x}$ et ${\displaystyle xy=yx}$.

Énoncé

Étant donné une suite ${\displaystyle x_{n}=y_{n}}$ d'équations pour ${\displaystyle n\geq 1}$, on dit qu'un monoïde ${\displaystyle M}$ vérifie ultimement ces équations s'il vérifie ces équations à partir d'un certain entier ${\displaystyle 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 ${\displaystyle x^{n}=x^{n+1}}$.

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

Notes et références

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

• Fabian Birkmann, Stefan Milius et Henning Urbat, « Eilenberg's variety theorem without Boolean operations », Information and Computation, vol. 295 « Selected papers of the 15th International Conference on Language and Automata Theory and Applications, LATA 2021 »,‎ 1^er décembre 2023, article n^o 104916 (DOI 10.1016/j.ic.2022.104916)

Articles connexes

• Demi-groupe
• Monoïde syntaxique

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

• Portail de l’algèbre
• Portail de l'informatique théorique