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 complément. À 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.
De nombreuses définitions non équivalentes des algèbres de Kleene et des structures liées ont été données dans la littérature. 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 aux 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 demi-anneau. On ajoute :
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 page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in
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 complément. À 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.
En mathématiques, un demi-anneau, ou semi-anneau, est une structure algébrique qui a les propriétés suivantes : constitue un monoïde commutatif ; forme un monoïde ; est distributif par rapport à + ; 0 est absorbant pour le produit, autrement dit: pour tout . Ces propriétés sont proches de celles d'un anneau, la différence étant qu'il n'y a pas nécessairement d'inverses pour l’addition dans un demi-anneau. Un demi-anneau est commutatif quand son produit est commutatif ; il est idempotent quand son addition est idempotente.
En théorie des langages, les langages rationnels ou langages réguliers ou encore langages reconnaissables peuvent être décrits de plusieurs façons équivalentes : ce sont les langages décrits par les expressions régulières ou rationnelles, d'où le nom de langages réguliers ; ce sont les langages obtenus, à partir des lettres et de l'ensemble vide, par les opérations rationnelles, à savoir l'union, le produit et l'étoile de Kleene, d'où le nom de langages rationnels ; ce sont les langages reconnus par des auto