- Algebre de Kleene
-
Algèbre de Kleene
En mathématiques, une algèbre de Kleene (du nom du logicien américain Stephen Cole Kleene) correspond à l'un des deux concepts suivants :
- Un treillis ordonné et distributif avec une involution satisfaisant les lois de De Morgan et l'inégalité x∧−x ≤ y∨−y. Ce qui fait que chaque algèbre booléenne est une algèbre de Kleene, la réciproque étant fausse. A l'instar des algèbres de Boole qui sont basées sur les propositions logiques classiques, les algèbres de Kleene sont basées sur la logique ternaire de Kleene.
- Une structure algébrique qui généralise les opérations connues à partir d'expressions rationnelles. La suite de cet article traitera de cette notion d'algèbre de Kleene. À l'origine de cette notion on trouve le mathématicien John Horton Conway qui l'a introduite sous le nom d'algèbres régulières[1].
Sommaire
Définition
De nombreuses définitions non équivalentes des algèbres de Kleene et des structures liées ont été données dans la littérature[2]. Nous donnerons ici la définition qui semble la plus communément admise aujourd'hui.
Une algèbre de Kleene est un ensemble doté des deux lois de composition interne + : A × A → A et · : A × A → A et de l'opérateur * : A → A. Ces lois et cet opérateur sont notés a + b, ab et a* respectivement. Ces opérations satisfont les axiomes suivants :
- associativité de + et · : a + (b + c) = (a + b) + c et a(bc) = (ab)c pour tout a, b, c de A.
- commutativité de + : a + b = b + a pour tout a, b de A.
- distributivité : a(b + c) = (ab) + (ac) et (b + c)a = (ba) + (ca) pour tout a, b, c de A.
- éléments neutres pour + et · : il existe un élément 0 de A tel que pour tout a de A : a + 0 = 0 + a = a. Il existe un élément 1 de A tel que pour tout a de A : a1 = 1a = a.
- 0 est un élément absorbant : a0 = 0a = 0 pour tout a de A.
Les axiomes ci-dessus définissent un semi-anneau. On ajoute de plus :
- l'idempotence de + : pour tout a de A, a + a = a.
Il est dès lors possible de définir un préordre ≤ sur A en postulant a ≤ b si et seulement si a + b = b (ou de manière équivalente, a ≤ b si et seulement il existe c dans A tel que a + c = b). Cette relation d'ordre permet de poser les deux derniers axiomes sur l'opérateur * :
- 1 + a(a*) ≤ a* pour tout a de A.
- 1 + (a*)a ≤ a* pour tout a de A.
- si a et b sont deux éléments de A tels que ab ≤ b alors a*b ≤ b.
- si a et b sont deux éléments de A tels que ba ≤ b alors b(a*) ≤ b.
De manière intuitive, on peut penser à a + b comme l'union ou le plus petit majorant de a et b, et à ab comme une multiplication croissante, dans le sens où a ≤ b implique ax ≤ bx. L'idée sousjacente à l'opérateur « étoile » est que a*=1 + a + aa + aaa + ... Du point de vue de la théorie de la programmation, on peut interpréter + comme un opérateur de « choix » non déterministe, · comme la « composition séquentielle » et * comme l'« itération ».
Exemples
Soient Σ un ensemble fini (un « alphabet ») et A l'ensemble des expressions rationnelles sur Σ. Deux expressions rationnelles sont égales si elles décrivent le même langage rationnel. L'ensemble A forme une algèbre de Kleene. En fait, il s'agit même d'une algèbre libre de Kleene dans le sens où toute équation valide dans cette algèbre est valide dans toute algèbre de Kleene.
Soit Σ un alphabet. Soit A l'ensemble des langages rationnels sur Σ (ou bien l'ensemble des langages sans contextes sur Σ, ou bien encore l'ensemble de tous les langages récursifs, ou bien enfin l'ensemble de tous les langages sur Σ). L'union (écrite +) et la concaténation (écrite •) de deux éléments de A appartiennent à A, et ainsi l'opération de fermeture de Kleene est un endomorphisme de A. On obtient alors un algèbre de Kleene avec comme élément 0, l'ensemble vide et comme élément 1, l'ensemble qui contient uniquement la chaîne vide. Soit M un monoïde avec comme identité un élément e et soit A l'ensemble des sous-ensembles de M. Soient S et T deux sous-ensembles de M, soit S + T l'union de S et T et ST = {chaîne: s dans S et t dans T}. S* est défini comme le sous-monoïde de M généré par S, intuitivement il correspond à {e} ∪ S ∪ SS ∪ SSS ∪ ... A forme alors une algèbre de Kleene avec comme 0, l'ensemble vide et comme 1, le singleton {e}. On peut faire une construction similaire dans toute petite catégorie.
Supposons M un ensemble et A l'ensemble des relations binaires sur M. On peut munir M des trois opérations des algèbres de Kleene, à savoir l'union pour +, la composition pour • et la fermeture réflexive et transitive pour *. Les deux constantes sont pour 0 la relation vide (qui ne relie rien) et pour 1 la relation pleine (qui relie tout). Ainsi équipé, (M, +, •, *; 0, 1) est une algèbre de Kleene.
Toute algèbre de Boole munie des opérations v et ^ s'avère être une algèbre de Kleene si l'on identifie v à +, ^ à •, que l'on postule a* = 1 pour tout a et que le 0 pour l'algèbre de Kleene est le 0 de l'algèbre de Boole et de même pour 1.
Une algèbre de Kleene spécifique est utile lorsqu'il s'agit de calculer des plus courts chemins dans les graphes orientés pondérés : soit A la droite réelle achevée, posons que a + b est le minimum de a et b et que ab est la somme du réel a et du réel b (la somme de +∞ et -∞ étant par définition +∞). a* est le nombre réel zéro si a est positif ou nul et -∞ si a est strictement négatif. A est une algèbre de Kleene dans laquelle 0 est la valeur -∞ et 1 est le nombre réel zéro.
Propriétés
Zéro, noté 0, est le plus petit élément de l'ensemble, autrement dit 0 ≤ a pour tout a dans A.
La somme a + b est le petit majorant de a et b : on a a ≤ a + b et b ≤ a + b et si x est un élément de A avec a ≤ x et b ≤ x, alors a + b ≤ x. De manière similaire, a1 + ... + an est le plus petit majorant des éléments a1, ..., an.
La multiplication et l'addition sont monotoniques : si a ≤ b, alors a + x ≤ b + x, ax ≤ bx et xa ≤ xb pour tout x de A.
Considérant l'opération *, nous avons 0* = 1 et 1* = 1, ce * est croissant (a ≤ b implique a* ≤ b*), et que an ≤ a* pour tout entier naturel n. De plus, (a*)(a*) = a*, (a*)* = a*, et a ≤ b* si et seulement si a* ≤ b*.
Les séries formelles forment une algèbre de Kleene à condition de prendre pour f * la série (1 - f )-1.
Si A est une algèbre de Kleene et n un entier naturel, on peut considérer l'ensemble Mn(A) constituées de toutes les matrices n par n avec entrées dans A. En utilisant les notions ordinaires d'additions et de multiplications matricielles, on peut définir une opération * unique telle que Mn(A) devienne une algèbre de Kleene.
Histoire
Les algèbres de Kleene n'ont pas été définies par Kleene. Il a introduit les expressions rationnelles et a postulé l'existence d'un ensemble complet d'axiomes qui permettrait de dériver toutes les équations valides dans les expressions rationnelles. Les premiers axiomes ont été proposés par John H. Conway et un système d'axiomes complets définissant les algèbres de Kleene et résolvant le problème a été proposé par Dexter Kozen. qui a démontré leur complétude.
Voir aussi
Notes et références
- ↑ Dans le fameux livre : J. H. Conway, Regular Algebra and Finite Machines, Chapman and Hall, London, 1971.
- ↑ Pour un survol, on pourra se reporter à : Dexter Kozen, On Kleene algebras and closed semirings. In Rovan, editor, Proc. Math. Found. Comput. Sci., volume 452 of Lecture Notes in Computer Science, pages 26-47. Springer, 1990. En ligne sur [1]
- (en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en anglais intitulé « Kleene algebra ».
Portail des mathématiques
Portail de la logique
Portail de l’informatique
Catégories : Algèbre | Langage formel | Stephen Cole Kleene
Wikimedia Foundation. 2010.
