In mathematics, a

**Kleene algebra**(named after Stephen Cole Kleene, pronounced "clay-knee") is either of two different things:

- A bounded distributive lattice with an involution satisfying certain laws weaker than those governing lattice-theoretic complementations. Thus every Boolean algebra is a Kleene algebra, but most Kleene algebras are not Boolean algebras.
- An algebraic structure that generalizes the operations known from regular expressions. The remainder of this article deals with this notion of Kleene algebra.

Table of contents |

2 Examples 3 Properties 4 History 5 References |

## Definition

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, so that the following axioms are satisfied.

- Associativity of + and ·:
*a*+ (*b*+*c*) = (*a*+*b*) +*c*and*a*(*bc*) = (*ab*)*c*for all*a*,*b*,*c*in*A*. - Commutativity of +:
*a*+*b*=*b*+*a*for all*a*,*b*in*A* - Distributivity:
*a*(*b*+*c*) = (*ab*) + (*ac*) and (*b*+*c*)*a*= (*ba*) + (*ca*) for all*a*,*b*,*c*in*A* - Identity elements for + and ·: There exists an element 0 in
*A*such that for all*a*in*A*:*a*+ 0 = 0 +*a*=*a*. There exists an element 1 in*A*such that for all*a*in*A*:*a*1 = 1*a*=*a*. -
*a*0 = 0*a*= 0 for all*a*in*A*.

- + is idempotent:
*a*+*a*=*a*for all*a*in*A*.

*A*by setting

*a*≤

*b*iff

*a*+

*b*=

*b*(or equivalently:

*a*≤

*b*iff there exists an

*x*in

*A*such that

*a*+

*x*=

*b*). With this order we can formulate the last two axioms about the operation *:

- 1 +
*a*(*a**) ≤*a** for all*a*in*A*. - 1 + (
*a**)*a*≤*a** for all*a*in*A*. - if
*a*and*x*are in*A*such that*ax*≤*x*, then*a***x*≤*x* - if
*a*and*x*are in*A*such that*xa*≤*x*, then*x*(*a**) ≤*x*

*a*+

*b*as the "union" or the "least upper bound" of

*a*and

*b*and of

*ab*as some multiplication which is monotonic, in the sense that

*a*≤

*b*implies

*ax*≤

*bx*. The idea behind the star operator is

*a** = 1 +

*a*+

*aa*+

*aaa*+ ... From the standpoint of programming theory, one may also interpret + as "choice", · as "sequencing" and * as "iteration".

## Examples

Let Σ be a finite set (an "alphabet") and let *A* be the set of all regular expressions over Σ. We consider two such regular expressions equal if they describe the same language. Then *A* forms a Kleene algebra. In fact, this is a "free" Kleene algebra in the sense that any equation among regular expressions follows from the Kleene algebra axioms and is therefore valid in every Kleene algebra.

Again let Σ be an alphabet. Let *A* be the set of all regular languages over Σ (or the set of all context-free languages over Σ; or the set of all recursive languages over Σ; or the set of *all* languages over Σ). Then the union (written as +) and the concatenation (written as ·) of two elements of *A* again belong to *A*, and so does the Kleene star operation applied to any element of *A*. We obtain a Kleene algebra *A* with 0 being the empty set and 1 being the set that only contains the empty string.

Let *M* be a monoid with identity element *e* and let *A* be the set of all subsets of *M*. For two such subsets *S* and *T*, let *S* + *T* be the union of *S* and *T* and set *ST* = {*st* : *s* in *S* and *t* in *T*}. *S** is defined as the submonoid of *M* generated by *S*, which can be described as {*e*} ∪ *S* ∪ *SS* ∪ *SSS* ∪ ... Then *A* forms a Kleene algebra with 0 being the empty set and 1 being {*e*}. An analogous construction can be performed for any small category.

Suppose *M* is a set and *A* is the set of all binary relations on *M*. Taking + to be the union, · to be the composition and * to be the reflexive transitive hull, we obtain a Kleene algebra.

Every boolean algebra with operations v and ^ turns into a Kleene algebra if we use v for +, ^ for · and set *a** = 1 for all *a*.

A quite different Kleene algebra is useful when computing shortest pathss in weighted directed graphs: let *A* be the extended real number line, take *a* + *b* to be the minimum of *a* and *b* and *ab* to be the ordinary sum of *a* and *b* (with the sum of +∞ and -∞ being defined as +∞). *a** is defined to be the real number zero for nonnegative *a* and -∞ for negative *a*. This is a Kleene algebra with zero element +∞ and one element the real number zero.

## Properties

Zero is the smallest element: 0 ≤ *a* for all *a* in *A*.

The sum *a* + *b* is the least upper bound of *a* and *b*: we have *a* ≤ *a* + *b* and *b* ≤ *a* + *b* and if *x* is an element of *A* with *a* ≤ *x* and *b* ≤ *x*, then *a* + *b* ≤ *x*. Similarly, *a*_{1} + ... + *a*_{n} is the least upper bound of the elements *a*_{1}, ..., *a*_{n}.

Multiplication and addition are monotonic: if *a* ≤ *b*, then *a* + *x* ≤ *b* + *x*, *ax* ≤ *bx* and *xa* ≤ *xb* for all *x* in *A*.

Regarding the * operation, we have 0* = 1 and 1* = 1, that * is monotonic (*a* ≤ *b* implies *a** ≤ *b**), and that *a*^{n} ≤ *a** for every natural number *n*. Furthermore, (*a**)(*a**) = *a**, (*a**)* = *a**, and *a* ≤ *b** if and only if *a** ≤ *b**.

If *A* is a Kleene algebra and *n* is a natural number, then one can consider the set M_{n}(*A*) consisting of all *n*-by-*n* matrices with entries in *A*.
Using the ordinary notions of matrix addition and multiplication, one can define a unique *-operation so that M_{n}(*A*) becomes a Kleene algebra.