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 -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 -trivial, c'est-à-dire sa relation 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é , et on entend par alphabet toute partie finie de . Une classe de langages formels est une famille de langages, chacun sur un alphabet, donc sur une partie finie de . On note et les langages de la famille sur l'alphabet , donc qui sont contenues dans et dans respectivement. On convient qui si est un alphabet en bijection avec , alors et 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 telle que
- pour tout alphabet , la famille est une algèbre de Boole ;
- pour tout morphisme de monoïdes , si alors ;
- pour tout alphabet , si , alors et pour tout mot de .
Une -variété de langages est une famille de langages telle que
- pour tout alphabet , la famille est une algèbre de Boole ;
- pour tout morphisme de demi-groupes , si alors ;
- pour tout alphabet , si , alors et pour tout mot de .
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 est fini si 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 pour tout alphabet . La plus petite -variété est composée du langage vide et du langage pour tout alphabet .
- 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 est l'algèbre de Boole engendrée par les langages , où les sont des lettres.
- La famille des langages localement testables. C'est la famille telle que est l'algèbre de Boole engendrée par les langages , , pour des mots , , .
- La famille des langages localement triviaux. C'est la -variété telle que est l'algèbre de Boole engendrée par les langages , où , , sont des parties finies de .
Variété de monoïdes finis
Définition
Une classe de monoïdes est une variété de monoïdes si elle a les propriétés suivantes :
- Si est dans , et si est un sous-monoïde de , alors est dans .
- Si est dans , et si est un quotient de , alors est dans .
- Si sont dans , alors leur produit direct est dans
Il faut noter que la dernière condition vaut aussi pour , ce qui plus simplement s'exprime en disant que le monoïdes réduit à un seul élément 1 est dans .
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 est nilpotent s'il possède un zéro, c'est-à-dire un élément tel que pour tout dans , et s'il existe un entier tel que tout produit de éléments de est égal à .
- 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 -triviaux finis, c'est-à-dire tels que la relation de Green 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 vérifie localement une propriété si, pour tout idempotent de , le demi-groupe vérifie la propriété . Par exemple, une monoïde (ou demi-groupe) est localement trivial si .
Variété engendrée par une famille de monoïdes
Soit une classe de monoïdes ou de demi-groupes. La variété engendrée par est la plus petite variété de monoïdes ou de demi-groupes contenant . C'est aussi l'intersection des variétés de monoïdes ou de demi-groupes contenant .
Une façon concrète de voir la variété engendrée par est : c'est l'ensemble des images homomorphes des sous-monoïdes ou de demi-groupes de produits directs d'éléments de . On dit qu'un demi-groupe divise un demi-groupe si est l'image homomorphe d'un sous-demi-groupe de . Ainsi, un demi-groupe appartient à la variété engendrée par si et seulement s'il divise un produit direct d'éléments de .
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
qui associe à une -variété (-variété) de langages la variété de monoïdes (demi-groupes) engendrée par les monoïdes (demi-groupes) syntaxiques des langages de .
D'autre part, on considère l'application
qui associe à la variété de monoïdes (de demi-groupes) la -variété (-variété) des langages dont le monoïde (demi-groupe) syntaxique est dans .
Énoncé
Théorème des variétés (Eilenberg & Schützenberger) — Les correspondances
et
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 (1) Groupes commutatifs Langages engendrés par (2) Monoïdes commutatifs apériodiques Langages engendrés par et Monoïdes commutatifs Langages sans étoile Monoïdes apériodique Langages engendrés par Monoïdes demi-treillis (idempotents commutatifs) Langages engendrés par Monoïdes -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 , on pose : , avec une lettre et ; dénote le nombre d'occurrences de la lettre dans le mot .
(2) Pour tout alphabet , on pose : , avec 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 un alphabet de variables. Étant donné deux mots et sur , on dit qu'un monoïde satisfait l'équation si, pour tout morphisme , on a . Ainsi, un monoïde commutatif est un monoïde qui satisfait l'équation . Il est facile de vérifier que la famille des monoïdes qui satisfont une équation forment une variété. Plus généralement, étant donné une suite d'équations pour , 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 .
- La variété des demi-treillis (monoïdes idempotents commutatifs) est donnée par les équations et .
Énoncé
Étant donné une suite d'équations pour , on dit qu'un monoïde vérifie ultimement ces équations s'il vérifie ces équations à partir d'un certain entier . 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 .
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, , 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, , 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 », , 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 » (no 466), (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), , 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 » (no 59), , xiii+387 (MR 0530383)
- (en) Samuel Eilenberg et Marcel-Paul Schützenberger, « On pseudovarieties », Advances in Math., vol. 19, no 3, , 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, no 2, , p. 190-194
- Imre Simon, « Piecewise testable events », dans H. Brakhage (éditeur), Proceedings 2nd GI Conference, Springer-Verlag, coll. « Lecture Notes in Computer Science » (no 33), , 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 », , article no 104916 (DOI 10.1016/j.ic.2022.104916)
Articles connexes
v · m Automates finis et langages réguliers | |
---|---|
Articles généraux | |
Automates finis | |
Automates finis particuliers |
|
Langages réguliers | |
Des automates aux langages | |
Des langages aux automates | |
Minimisation | |
Équivalences |
|
v · m | |
---|---|
Codage | |
Modèles de calcul | |
Algorithmique |
|
Syntaxe | |
Sémantique | |
Logique mathématique | |
Mathématiques discrètes |
Portail de l’algèbre
Portail de l'informatique théorique