Voir la source de Théorème des variétés d'Eilenberg

En [[informatique théorique]], et notamment en théorie de [[langage rationnel|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'''<ref>Par exemple {{harv|Lawson|2003}}, alors que {{harv|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.</ref> 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ïde]]s 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<ref>{{harv|Eilenberg|1976}}, chapitres V, VII et VIII, sans compter les applications.</ref>, 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 [[langage sans étoile|langages rationnels {{Citation|sans étoile}}]] par la propriété que leur [[monoïde syntaxique]] n'a que des {{Citation|sous-groupes triviaux}}, en d'autres termes, les  <math>\mathcal{H}</math>-classes qui sont des groupes sont des singletons ([[monoïde apériodique|monoïdes apériodiques]] finis). 
Un autre résultat de cette nature est dû à Imre Simon<ref>{{harv |Simon | 1975}}</ref> : un langage rationnel est ''testable par morceaux''  si et seulement si son monoïde syntaxique est <math>\mathcal{J}</math>-trivial, c'est-à-dire sa relation <math>\mathcal{J}</math> 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é (algèbre) | 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 [[Garrett Birkhoff |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<ref>L'objectif de l'article  {{harv|Eilenberg|Schützenberger|1976}} est de décrire cette relation.</ref>. L'étude des équations a conduit d'ailleurs à une formulation plus générale d'équations.

{| align="right" 
|-
| [[File:Samuel Eilenberg MFO.jpeg|150px]] || [[Fichier:Schützenberger.jpeg|200px]]
|-
| align="center" |[[Samuel Eilenberg]]|| align="center" |[[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é <math>\Sigma</math>, et on entend par ''alphabet'' toute partie finie de <math>\Sigma</math>.
Une ''classe de langages formels'' est une famille <math>\mathcal{F}</math> de langages, chacun sur un alphabet, donc sur une partie finie de <math>\Sigma</math>. On note  <math>\mathcal{F}(A^*)</math>  et <math>\mathcal{F}(A^+)</math> les langages de la famille sur l'alphabet <math>A</math>, donc qui sont contenues dans <math>A^*</math> et dans <math>A^+</math> respectivement. On convient qui si <math>B</math> est un alphabet en [[bijection]] avec <math>A</math>, alors <math>\mathcal{F}(B^*)</math> et <math>\mathcal{F}(A^*)</math> sont égales à la bijection près.

=== Définition ===
Il y a en fait deux variantes de la définition, les <math>*</math>-variétés et les <math>+</math>-variétés. 

Une <math>*</math>-''variété'' de langages est une famille de langages <math>\mathcal{V}</math> telle que
# pour tout alphabet <math>A</math>, la famille <math>\mathcal{V}(A^*)</math> est une algèbre de Boole ;
# pour tout morphisme de monoïdes <math>f: A^*\to B^*</math>, si <math>X\in \mathcal{V}(B^*)</math> alors <math>f^{-1}(X)\in \mathcal{V}(A^*)</math> ;
# pour tout alphabet <math>A</math>, si <math>X \in \mathcal{V}(A^*)</math>, alors <math>u^{-1}X \in \mathcal{V}(A^*)</math> et <math>Xu^{-1} \in \mathcal{V}(A^*)</math> pour tout mot <math>u</math> de <math>A^*</math>.
Une <math>+</math>-''variété'' de langages est une famille de langages <math>\mathcal{V}</math> telle que
# pour tout alphabet <math>A</math>, la famille <math>\mathcal{V}(A^+)</math> est une algèbre de Boole ;
# pour tout morphisme de demi-groupes <math>f: A^+\to B^+</math>, si <math>X\in \mathcal{V}(B^+)</math> alors <math>f^{-1}(X)\in \mathcal{V}(A^+)</math> ;
# pour tout alphabet <math>A</math>, si <math>X \in \mathcal{V}(A^+)</math>, alors <math>u^{-1}X \in \mathcal{V}(A^+)</math> et <math>Xu^{-1} \in \mathcal{V}(A^+)</math> pour tout mot <math>u</math> de <math>A^+</math>.

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 [[mot (mathématiques) | 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 <math>f^{-1}(X)</math>  est fini si <math>X</math> 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 <math>*</math>-variété est composée du langage vide et du langage <math>A^*</math> pour tout alphabet <math>A</math>. La plus petite <math>+</math>-variété est composée du langage vide et du langage <math>A^+</math> pour tout alphabet <math>A</math>.
# La famille des langages finis ou cofinis (compléments de langages finis) est une <math>+</math>-variété. Cette famille n'est pas une  <math>*</math>-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 [[langage sans étoile | langages rationnels sans étoile]].
# La famille des langages ''testables par morceaux''. C'est la famille telle que <math>\mathcal{V}(A^*)</math> est l'algèbre de Boole engendrée par les langages <math>A^*a_1A^*a_2\cdots a_nA^*</math>, où les <math>a_i</math> sont des lettres. 
# La famille des langages ''localement testables''. C'est la famille telle que <math>\mathcal{V}(A^*)</math> est l'algèbre de Boole engendrée par les langages <math>uA^*</math>, <math>A^*v</math>, <math>A^*wA^*</math> pour des mots <math>u</math>, <math>v</math>, <math>w</math>.
# La famille des langages ''localement triviaux''. C'est la <math>+</math>-variété telle que <math>\mathcal{V}(A^+)</math> est l'algèbre de Boole engendrée par les langages <math>XA^*Y\cup Z</math>, où <math>X</math>, <math>Y</math>, <math>Z</math> sont des parties finies de <math>A^+</math>.

== Variété de monoïdes finis ==
=== Définition ===

Une classe <math>\mathbf{V}</math> de monoïdes est une ''variété de monoïdes'' si elle a les propriétés suivantes :
# Si <math>S</math> est dans <math>\mathbf{V}</math>, et si <math>T</math> est un sous-monoïde de <math>S</math>, alors <math>T</math> est dans <math>\mathbf{V}</math>.
# Si <math>S</math> est dans <math>\mathbf{V}</math>, et si <math>T</math> est un quotient de <math>S</math>, alors <math>T</math> est dans <math>\mathbf{V}</math>.
# Si <math>S_1,\ldots,S_n</math> sont dans <math>\mathbf{V}</math>, alors leur produit direct <math>S_1\times\cdots\times S_n</math> est dans <math>\mathbf{V}</math>
Il faut noter que la dernière condition vaut aussi pour <math>n=0</math>, ce qui plus simplement s'exprime en disant que le monoïdes réduit à un seul élément 1 est dans <math>\mathbf{V}</math>.

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 <math>M</math> est ''nilpotent'' s'il possède un ''zéro'', c'est-à-dire un élément <math>0</math> tel que <math>s0=0s=0</math> pour tout <math>s</math> dans <math>S</math>, et s'il existe un entier <math>n</math> tel que tout produit de <math>n</math> éléments de <math>M</math> est égal à <math>0</math>.
# 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ïde apériodique|monoïdes apériodiques]] finis.
# La famille des groupes finis.
# La famille des monoïdes <math>\mathcal{J}</math>-triviaux finis, c'est-à-dire tels que la [[relation de Green]] <math>\mathcal{J}</math> 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 <math>S</math> ''vérifie localement'' une propriété <math>P</math> si, pour tout idempotent <math>e</math> de <math>S</math>, le demi-groupe <math>eSe</math> vérifie la propriété <math>P</math>. Par exemple, une monoïde (ou demi-groupe) <math>S</math>  est ''localement trivial'' si <math>eSe=e</math>. 

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

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

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

== 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
:<math>\mathcal{V}\mapsto \mathbf{V}</math> 
qui associe à une <math>*</math>-variété (<math>+</math>-variété) de langages <math>\mathcal{V}</math> la variété de monoïdes (demi-groupes) <math>\mathbf{V}</math> engendrée par les monoïdes (demi-groupes) syntaxiques des langages de <math>\mathcal{V}</math>. 

D'autre part, on considère l'application
:<math>\mathbf{V} \mapsto \mathcal{V}</math>
qui associe à la variété de monoïdes (de demi-groupes) <math>\mathbf{V}</math> la <math>*</math>-variété (<math>+</math>-variété) des langages <math>\mathcal{V}</math> dont le monoïde (demi-groupe) syntaxique est dans <math>\mathbf{V}</math>.
=== Énoncé ===
{{théorème|Théorème des variétés (Eilenberg & Schützenberger)| Les correspondances 
:<math>\mathcal{V}\mapsto \mathbf{V}</math>
et 
:<math>\mathbf{V} \mapsto \mathcal{V}</math>
sont des bijections réciproques l'une de l'autre.}}
Cet énoncé en recouvre en fait deux : le premier met en bijection les <math>+</math>-variétés et les variétés de demi-groupes, l'autre les <math>*</math>-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 {{harv|Pin|1995}} et {{harv|Pin|2012}} :
{|
|-
|
|
|}
:{| class="wikitable"
|+ 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 <math>L(a,k,n)</math> {{Exp|(1)}}
| Groupes commutatifs
|-----
| Langages engendrés par <math>L(a,k)</math> {{Exp|(2)}}
| Monoïdes commutatifs apériodiques
|-----
| Langages engendrés par <math>L(a,k,n)</math> et  <math>L(a,k)</math>
| Monoïdes commutatifs
|-----
| Langages sans étoile
| Monoïdes apériodique
|-----
| Langages engendrés par <math>A^*aA^*</math>
| Monoïdes demi-treillis (idempotents commutatifs)
|-----
| Langages engendrés par <math>A^*a_1A^*a_2\cdots a_nA^*</math>
| Monoïdes <math>\mathcal{J}</math>-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 <math>A</math>, on pose :  <math>L(a,k,n)=\{u\in A^*\mid |u|_a\equiv k \bmod n\}</math>, avec <math>a</math> une lettre et  <math>k<n</math>; <math>|u|_a</math> dénote le nombre d'occurrences de la lettre <math>a</math> dans le mot <math>u</math>.

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

=== Énoncé ===

Étant donné une suite <math>x_n=y_n</math> d'équations pour <math>n\ge1</math>, on dit qu'un monoïde <math>M</math> ''vérifie ultimement'' ces équations s'il vérifie ces équations à partir d'un certain entier <math>N</math>. La famille des monoïdes qui vérifient ultimement une suite d'équations est encore une variété. Par exemple, les [[monoïde apériodique |monoïdes apériodiques]] vérifient ultimement les équations <math>x^n=x^{n+1}</math>.

{{théorème|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 ==
{{Références}}

=== Littérature ===

==== Traités ====

<!-- G -->
* {{Ouvrage
|langue=en
|prénom1=Gracinda M. S.
|nom1=Gomes
|prénom2=Jean-Éric
|nom2=Pin
|prénom3=Pedro V.
|nom3=Silva (éditeurs)
|titre=Semigroups, algorithms, automata, and languages
|sous-titre=: Coimbra, Portugal, May-July 2001
|éditeur=[[World Scientific]]
|année=2002
|pages totales=515
|isbn=978-981-238-099-9
|présentation en ligne={{Google Livres|IL58mAsfXOgC}}
|id=GomesPinSilva
}}

<!-- L -->
*{{Ouvrage|langue=en|prénom1=Mark V.|nom1=Lawson|titre=Finite Automata|lieu=Boca Raton/London/New York etc.|éditeur=Chapman and Hall/CRC|année=2003|pages totales=320|isbn=1-58488-255-7}}{{plume}}

<!-- P -->
* {{Ouvrage|langue=en|prénom1=Jean-Éric|nom1=Pin|titre=Varieties of formal languages|éditeur=Plenum Publishing Corp.|collection=Foundations of Computer Science|année=1986|pages totales=x+138|isbn=0-306-42294-8|math reviews=89a:68125}}

* {{chapitre |prénom1=Jean-Éric|nom1=Pin 
 |titre chapitre= Finite semigroups and recognizable languages: an introduction
 |auteurs ouvrage= J. Fountain (éditeur)|titre ouvrage= Semigroups, Formal Languages and Groups
 |sous-titre ouvrage= York, 1993 |collection=  NATO Advanced Study Institute Series C
 |numéro dans collection= 466|lieu= Dordrecht
 |éditeur= Kluwer Academic Publishers |année= 1995|passage= 1-32
 |lire en ligne= http://www.liafa.univ-paris-diderot.fr/~jep/PDF/York1.pdf}}{{plume}}

* {{Ouvrage|langue=en|prénom1=Jean-Éric|nom1=Pin|titre=Mathematical Foundations of Automata Theory|éditeur=Support de cours du Master Parisien de Recherche en Informatique (MPRI)|année=2012|pages totales=310|passage=95-124|isbn=|lire en ligne=http://www.liafa.univ-paris-diderot.fr/~jep/PDF/MPRI/MPRI.pdf|consulté le=20 juin 2012}}

==== Sources ====
*{{Ouvrage|langue=en|prénom1=Samuel|nom1=Eilenberg|titre=Automata, Languages and Machines, Vol. B|éditeur=[[Academic Press]]|collection=Pure and Applied Mathematics|numéro dans collection=59|année=1976|pages totales=xiii+387|isbn=|math reviews=0530383}}

*{{Article|langue=en
|prénom1=Samuel|nom1= Eilenberg|lien auteur1=Samuel Eilenberg
|prénom2=Marcel-Paul|nom2=Schützenberger|lien auteur=Marcel-Paul Schützenberger
| titre=On pseudovarieties| périodique=Advances in Math.| année=1976| volume=19| numéro=3| pages=413–418| mr=0401604| doi=10.1016/0001-8708(76)90029-3}}

*{{Article|langue=en |prénom1=Marcel-Paul|nom1=Schützenberger
| lien auteur1=Marcel-Paul Schützenberger | titre=On finite monoids having only trivial subgroups | périodique=''[[Information and Computation|Information and Control]]'' | année=1965|volume=8|numéro=2|pages=190-194
}}

*{{Chapitre |prénom1= Imre |nom1= Simon|titre chapitre= Piecewise testable events|auteurs ouvrage= H. Brakhage (éditeur)|titre ouvrage= Proceedings 2nd GI Conference
 |collection= Lecture Notes in Computer Science |numéro dans collection=33 
 |éditeur= Springer-Verlag|année= 1975|passage= 214-222}}

==== Articles ====

* {{Article 
|prénom1=Fabian |nom1=Birkmann 
|prénom2=Stefan |nom2=Milius 
|prénom3=Henning |nom3=Urbat 
|titre=Eilenberg's variety theorem without Boolean operations |périodique=Information and Computation |titre volume= Selected papers of the 15th International Conference on Language and Automata Theory and Applications, LATA 2021 |volume=295 |numéro article =104916 |date=2023-12-01 |doi=10.1016/j.ic.2022.104916 }}

=== Articles connexes ===
* [[Demi-groupe]]
* [[Monoïde syntaxique]]

{{Palette Automates finis et langages réguliers}}
{{Palette|Informatique théorique}}
{{Portail|algèbre|informatique théorique}}

[[Catégorie:Théorème d'informatique|Eilenberg]]
[[Catégorie:Langage formel]]
[[Catégorie:Théorie des automates]]