Monoïde apériodique
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En mathématiques, un demi-groupe apériodique est un demi-groupe S tel que pour tout élément x de S, il existe un entier naturel n tel que xn = xn+1. Un monoïde apériodique est un demi-groupe apériodique unifère.
Un sous-demi-groupe G d'un demi-groupe S est un groupe de S ou un groupe dans S s'il existe un idempotent e tel que (G, e) soit un groupe.
Monoïde apériodique fini
Un demi-groupe fini S est apériodique si et seulement si les groupes de S sont triviaux, c'est-à-dire réduits à un élément.
On peut exprimer l'apériodicité comme suit au moyen des relations de Green : un demi-groupe fini est apériodique si et seulement si sa relation de Green ℋ est triviale.
Un célèbre résultat de la théorie des automates, dû à Marcel-Paul Schützenberger[1], est le suivant :
Théorème (Schützenberger 1965) — Un langage rationnel est sans étoile si et seulement si son monoïde syntaxique est fini et apériodique.
Une des conséquences du théorème de Krohn-Rhodes (en) est que tout monoïde apériodique fini divise le produit en couronne de plusieurs copies du monoïde à 3 éléments formé d'un élément neutre et de deux zéros à droite.
Références
- ↑ (en) Marcel-Paul Schützenberger, « On finite monoids having only trivial subgroups », Information and Control, vol. 8, no 2, , p. 190-194.
Article lié
- Mot synchronisant
- Portail de l'informatique théorique
- Portail de l’algèbre