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 De Morgan's laws, and the inequality x∧−x ≤ y∨−y. Thus every Boolean algebra is a Kleene algebra, but most Kleene algebras are not Boolean algebras. Just as Boolean algebras are related to the classical propositional logic, Kleene algebras relate to Kleene's three-valued logic.
- An algebraic structure that generalizes the operations known from regular expressions. The remainder of this article deals with this notion of Kleene algebra.
| Contents |
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 × 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 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
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 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 paths 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, a1 + ... + an is the least upper bound of the elements a1, ..., an.
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 an ≤ 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 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.
References
- Dexter Kozen: On Kleene algebras and closed semirings. In Rovan, editor, Proc. Math. Found. Comput. Sci., volume 452 of Lecture Notes in Computer Science, pages 26-47. Springer, 1990. Online at http://www.cs.cornell.edu/kozen/papers/kacs.ps