Main Page | See live article | Alphabetical index

# Kleene algebra

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.

## Definition

Various inequivalent definitions of Kleene algebras and related structures have been given in the literature. See [1] for a survey. 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 × AA and · : A × AA and one function * : AA, 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: a1 = 1a = a.
• a0 = 0a = 0 for all a in A.
The above axioms define a semiring. We further require:
It is now possible to define a partial order ≤ on A by setting ab iff a + b = b (or equivalently: ab 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*)aa* for all a in A.
• if a and x are in A such that axx, then a*xx
• if a and x are in A such that xax, then x(a*) ≤ x

Intuitively, one should think of 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 ab implies axbx. 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} ∪ SSSSSS ∪ ... 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 aa + b and ba + b and if x is an element of A with ax and bx, then a + bx. Similarly, a1 + ... + an is the least upper bound of the elements a1, ..., an.

Multiplication and addition are monotonic: if ab, then a + xb + x, axbx and xaxb for all x in A.

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

If A is a Kleene algebra and n is a natural number, then one can consider the set Mn(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 Mn(A) becomes a Kleene algebra.

## History

Kleene algebras were not defined by Kleene; he introduced regular expressions and asked for a set of axioms which would allow to derive all equations among regular expressions. The axioms of Kleene algebras solve this problem, as was first shown by Dexter Kozen.