Kleene algebra

[share]

Kleene algebra (/ˈkleɪni/ KLAY-nee; named after Stephen Cole Kleene)
is an idempotent (and thus partially ordered) semiring endowed
with a closure operator.[1]
It generalizes the operations known from regular expressions.

Various inequivalent definitions of Kleene algebras and
related structures have been given in the literature.[2]
Here we will give the definition that seems to be the most common nowadays.

A Kleene algebra is a set A together with two binary operations + : A × A → A
and · : A × A → A and one function * : A → A, written as a + b, ab and a* respectively.

Wiki



1. Definition
A Kleene algebra is a de Morgan algebra D satisfying x∧¬x≤y∨¬y for all x,y∈D. Since the order is definable in terms of the lattice operators, this can be stated as the equation

x∧¬x∧(y∨¬y)=x∧¬x.
2. Examples
Any Boolean algebra is a Kleene algebra, with ¬ the logical negation.
The unit interval [0,1] is a Kleene algebra, with ¬x=(1−x).

https://ncatlab.org/nlab/show/Kleene+algebra

[share]

Kleene algebras are a particular case of closed semirings,
also called quasi-regular semirings or Lehmann semirings,
which are semirings in which every element has at least one quasi-inverse satisfying the equation:
a* = aa* + 1 = a*a + 1.

This quasi-inverse is not necessarily unique.[14][15] In a Kleene algebra,
a* is the least solution to the fixpoint equations: X = aX + 1 and X = Xa + 1.[15]

Closed semirings and Kleene algebras appear in algebraic path problems,
a generalization of the shortest path problem.[15]

Wiki