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

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.

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^{+}}$.

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.

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}$.

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} }$.

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.

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.

• 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}$.

É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.

• (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

• (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

• Demi-groupe
• Monoïde syntaxique