Kleene Algebra - Definition

Definition

Various inequivalent definitions of Kleene algebras and related structures have been given in the literature. See 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 × 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: a1 = 1a = a.
• a0 = 0a = 0 for all a in A.

The above axioms define a semiring. We further require:

• + is idempotent: a + a = a for all a in A.

It is now possible to define a partial order ≤ on A by setting a ≤ b if and only if a + b = b (or equivalently: a ≤ b if and only if 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

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 a ≤ b implies ax ≤ bx. The idea behind the star operator is a* = 1 + a + aa + aaa + ... From the standpoint of programming language theory, one may also interpret + as "choice", · as "sequencing" and * as "iteration".