Algèbre de Kleene - Kleene algebra

En mathématiques , une algèbre de Kleene ( / k l eɪ n i / KLAY -neE ; nom Stephen Cole Kleene ) est un idempotent (et donc partiellement ordonnée) semi - anneau doté d'un opérateur de fermeture . Il généralise les opérations connues des expressions régulières .

Définition

Diverses définitions inéquivalentes des algèbres de Kleene et des structures associées ont été données dans la littérature. Nous allons donner ici la définition qui semble être la plus courante de nos jours.

Une algèbre de Kleene est un ensemble A avec deux opérations binaires +: A × A → A et ·: A × A → A et une fonction ^* : A → A , écrites respectivement par a + b , ab et a ^* , de sorte que les axiomes suivants sont satisfaits.

Associativité de + et ·: a + ( b + c ) = ( a + b ) + c et un ( bc ) = ( ab ) c pour tout un , b , c dans A .
Commutativité de +: a + b = b + a pour tout a , b dans A
Distributivité : a ( b + c ) = ( ab ) + ( ac ) et ( b + c ) a = ( ba ) + ( ca ) pour tout a , b , c dans A
Éléments d'identité pour + et ·: Il existe un élément 0 dans A tel que pour tout a dans A : a + 0 = 0 + a = a . Il existe un élément 1 dans A tel que pour tout a dans A : a 1 = 1 a = a .
Annihilation par 0: a 0 = 0 a = 0 pour tout un en A .

Les axiomes ci-dessus définissent un semiring . Nous avons en outre besoin:

+ Est idempotent : a + a = a pour tout un dans A .

Il est maintenant possible de définir un ordre partiel ≤ sur A en posant a ≤ b si et seulement si a + b = b (ou de manière équivalente: a ≤ b si et seulement s'il existe un x dans A tel que a + x = b ; quelle que soit la définition, a ≤ b ≤ a implique a = b ). Avec cet ordre, nous pouvons formuler les quatre derniers axiomes sur l'opération ^* :

1 + a ( a ^* ) ≤ a ^* pour tout un en A .
1 + ( a ^* ) un ≤ a ^* pour tout un en A .
si a et x sont dans A tels que ax ≤ x , alors a ^* x ≤ x
si a et x sont dans A tels que xa ≤ x , alors x ( a ^* ) ≤ x

Intuitivement, on devrait penser à a + b comme "l'union" ou à la "moindre borne supérieure" de a et b et de ab comme une multiplication monotone , en ce sens que a ≤ b implique ax ≤ bx . L'idée derrière l'opérateur étoile est a ^* = 1 + a + aa + aaa + ... Du point de vue de la théorie du langage de programmation , on peut aussi interpréter + comme "choix", · comme "séquençage" et ^* comme "itération" .

Exemples

Correspondance notationnelle entre
Algèbres de Kleene et	+	·	^*	0	1
Expressions régulières	\|	pas écrit	^*	∅	ε

Soit Σ un ensemble fini (un «alphabet») et soit A l'ensemble de toutes les expressions régulières sur Σ. Nous considérons deux de ces expressions régulières comme égales si elles décrivent le même langage . Alors A forme une algèbre de Kleene. En fait, il s'agit d'une algèbre de Kleene libre dans le sens où toute équation parmi les expressions régulières découle des axiomes de l'algèbre de Kleene et est donc valable dans chaque algèbre de Kleene.

Encore une fois, soit Σ un alphabet. Soit A l'ensemble de toutes les langues régulières sur Σ (ou l'ensemble de toutes les langues sans contexte sur Σ; ou l'ensemble de toutes les langues récursives sur Σ; ou l'ensemble de toutes les langues sur Σ). Ensuite , le syndicat (écrit +) et la concaténation (écrit ·) de deux éléments de A nouveau appartiennent à A , et fait donc l' étoile de Kleene opération appliquée à tout élément de A . Nous obtenons une algèbre de Kleene A avec 0 étant l' ensemble vide et 1 étant l'ensemble qui ne contient que la chaîne vide .

Que M soit un monoïde avec l' élément identité e et laisser A l'ensemble de tous les sous - ensembles de M . Pour deux de ces sous-ensembles S et T , soit S + T l'union de S et T et posons ST = { st : s dans S et t dans T }. S ^* est défini comme le sous-monoïde de M généré par S , qui peut être décrit comme { e } ∪ S ∪ SS ∪ SSS ∪ ... Alors A forme une algèbre de Kleene avec 0 étant l'ensemble vide et 1 étant { e }. Une construction analogue peut être réalisée pour n'importe quelle petite catégorie .

Les sous - espaces linéaires d'une algèbre unitale sur un champ forment une algèbre de Kleene. Étant donné les sous-espaces linéaires V et W , définissez V + W comme étant la somme des deux sous-espaces et 0 comme le sous-espace trivial {0}. Définissez V · W = span {v · w | v ∈ V, w ∈ W}, l' étendue linéaire du produit des vecteurs de V et W respectivement. Définissez 1 = span {I}, l'étendue de l'unité de l'algèbre. La fermeture de V est la somme directe de tous les pouvoirs de V .

{\ displaystyle V ^ {*} = \ bigoplus _ {i = 0} ^ {\ infty} V ^ {i}}

On suppose que M est un ensemble et A est l'ensemble de toutes les relations binaires sur M . En prenant + pour être l'union, · pour être la composition et ^* pour être la fermeture transitive réflexive , nous obtenons une algèbre de Kleene.

Chaque algèbre booléenne avec des opérations et se transforme en une algèbre de Kleene si nous utilisons pour +, pour · et posons a ^* = 1 pour tout a . ${\ displaystyle \ lor}$ ${\ displaystyle \ land}$ ${\ displaystyle \ lor}$ ${\ displaystyle \ land}$

Une algèbre de Kleene tout à fait différente peut être utilisée pour implémenter l' algorithme Floyd – Warshall , calculant la longueur du chemin le plus court pour tous les deux sommets d'un graphe orienté pondéré , par l'algorithme de Kleene , calculant une expression régulière pour tous les deux états d'un automate fini déterministe . En utilisant la droite étendue des nombres réels , prenons a + b pour être le minimum de a et b et ab pour être la somme ordinaire de a et b (la somme de + ∞ et −∞ étant définie comme + ∞). un ^* est défini comme étant le nombre zéro réel non négatif pour un et -∞ pour le négatif a . C'est une algèbre de Kleene avec zéro élément + ∞ et un élément le nombre réel zéro. Un graphe orienté pondéré peut alors être considéré comme un automate fini déterministe, chaque transition étant étiquetée par son poids. Pour deux nœuds de graphe quelconques (états d'automate), les expressions régulières calculées à partir de l'algorithme de Kleene évaluent, dans cette algèbre de Kleene particulière, la longueur de chemin la plus courte entre les nœuds.

Propriétés

Zero est le plus petit élément: 0 ≤ a pour tous un dans A .

La somme a + b est la plus petite borne supérieure 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 même, a ₁ + ... + a _n est la plus petite borne supérieure des éléments a ₁ , ..., a _n .

La multiplication et l'addition sont monotones: si a ≤ b , alors

a + x ≤ b + x ,
ax ≤ bx , et
xa ≤ xb

pour tout x dans A .

En ce qui concerne l'opération star, nous avons

0 ^* = 1 et 1 ^* = 1,
a ≤ b implique a ^* ≤ b ^* (monotonicité),
a ⁿ ≤ a ^* pour tout nombre naturel n , où a ⁿ est défini comme multiplication par n de a ,
( a ^* ) ( a ^* ) = a ^* ,
( a ^* ) ^* = a ^* ,
1 + a ( a ^* ) = a ^* = 1 + ( a ^* ) a ,
ax = xb implique ( a ^* ) x = x ( b ^* ),
(( ab ) ^* ) a = a (( ba ) ^* ),
( a + b ) ^* = a ^* ( b ( a ^* )) ^* , et
pq = 1 = qp implique q ( a ^* ) p = ( qap ) ^* .

Si A est une algèbre Kleene et n est un nombre naturel, alors on peut considérer l'ensemble M _n ( A ) comprenant tous les n de n des matrices avec des entrées dans A . En utilisant les notions ordinaires d'addition et de multiplication de matrice, on peut définir une ^* -opération unique pour que M _n ( A ) devienne une algèbre de Kleene.

L'histoire

Kleene a introduit les expressions régulières et a donné certaines de leurs lois algébriques. Bien qu'il n'ait pas défini les algèbres de Kleene, il a demandé une procédure de décision pour l'équivalence des expressions régulières. Redko a prouvé qu'aucun ensemble fini d' axiomes équationnels ne peut caractériser l'algèbre des langages réguliers. Salomaa a donné des axiomatisations complètes de cette algèbre, mais en fonction de règles d'inférence problématiques. Le problème de la fourniture d'un ensemble complet d'axiomes, qui permettrait la dérivation de toutes les équations parmi les expressions régulières, a été intensivement étudié par John Horton Conway sous le nom d' algèbres régulières , cependant, l'essentiel de son traitement était infinitaire. En 1981, Kozen a donné un système déductif équationnel infini complet pour l'algèbre des langues régulières. En 1994, il a donné le système d'axiomes finis ci - dessus , qui utilise des égalités inconditionnelles et conditionnelles (en considérant a ≤ b comme une abréviation pour a + b = b ), et est équationnellement complet pour l'algèbre des langages réguliers, c'est-à-dire deux expressions régulières a et b désignent le même langage seulement si a = b découle des axiomes ci - dessus .

Généralisation (ou relation avec d'autres structures)

Les algèbres de Kleene sont un cas particulier de semirings fermés , également appelés semirings quasi-réguliers ou semirings de Lehmann , qui sont des semirings dans lesquels chaque élément a au moins un quasi-inverse satisfaisant l'équation: a * = aa * + 1 = a * a + 1. Ce quasi-inverse n'est pas nécessairement unique. Dans une algèbre de Kleene, a * est la moindre solution aux équations du point fixe : X = aX + 1 et X = Xa + 1.

Les semirings fermés et les algèbres de Kleene apparaissent dans les problèmes de chemin algébrique , une généralisation du problème de chemin le plus court .

Voir également

Notes et références

Kozen, Dexter . "CS786 Spring 04, Introduction à l'algèbre de Kleene" .

Lectures complémentaires

Peter Höfner (2009). Calculs algébriques pour les systèmes hybrides . BoD - Livres à la demande. pp. 10–13. ISBN 978-3-8391-2510-6 . L'introduction de ce livre passe en revue les progrès réalisés dans le domaine de l'algèbre de Kleene au cours des 20 dernières années, qui ne sont pas abordés dans l'article ci-dessus.

Languages

In other projects