Kleene algebra
Encyclopedia
In mathematics
, a Kleene algebra (icon ; named after Stephen Cole Kleene
) is either of two different things:
A Kleene algebra is a set A together with two binary operation
s + : 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.
The above axioms define a semiring
. We further require:
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 *:
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".
. 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 language
s over Σ (or the set of all context-free language
s over Σ; or the set of all recursive language
s 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 subset
s 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 relation
s 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
and 
turns into a Kleene algebra if we use 
for +, 
for · and set a* = 1 for all a.
A quite different Kleene algebra is useful when computing shortest path
s 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.
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.
under the name of regular algebras. The axioms of Kleene algebras solve this problem, as was first shown by Dexter Kozen.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a Kleene algebra (icon ; named after Stephen Cole Kleene
Stephen Cole Kleene
Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
) is either of two different things:
- A bounded distributive latticeDistributive latticeIn mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
with an involution satisfying De Morgan's laws (i.e. a De Morgan algebraDe Morgan algebraIn mathematics, a De Morgan algebra is a structure A = such that:* is a bounded distributive lattice, and...
), additionally satisfying the inequality x∧−x ≤ y∨−y. Kleene (and De Morgan) algebras are subclasses of Ockham algebraOckham algebraIn mathematics, an Ockham algebra is a bounded distributive lattice with a dual endomorphism. They were introduced by , and were named after William of Ockham by ....
s. The simplest Kleene algebra of this kind is Kleene's three-valued logic K3. (This is analogous to Boolean logicBoolean logicBoolean algebra is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of multiplication xy, addition x + y, and negation −x replaced by the respective logical operations of...
being the simplest Boolean algebraBoolean algebraIn abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets...
.)
- An algebraic structureAlgebraic structureIn abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
that generalizes the operations known from regular expressionRegular expressionIn computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
s. 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 operation
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
s + : 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.
- AssociativityAssociativityIn mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
of + and ·: a + (b + c) = (a + b) + c and a(bc) = (ab)c for all a, b, c in A. - CommutativityCommutativityIn mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
of +: a + b = b + a for all a, b in A - DistributivityDistributivityIn mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalizes the distributive law from elementary algebra.For example:...
: a(b + c) = (ab) + (ac) and (b + c)a = (ba) + (ca) for all a, b, c in A - Identity elementIdentity elementIn mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
s 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
Semiring
In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse...
. 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
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
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
Programming language theory
Programming language theory is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of programming languages and their individual features. It falls within the discipline of computer science, both depending on and affecting...
, 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 languageFormal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
. Then A forms a Kleene algebra. In fact, this is a free
Free object
In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of universal algebra, in the sense that it relates to all types of algebraic structure . It also has a formulation in terms of category theory, although this is in yet more abstract terms....
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 language
Regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s over Σ (or the set of all context-free language
Context-free language
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
s over Σ; or the set of all recursive language
Recursive language
In mathematics, logic and computer science, a formal language is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language...
s over Σ; or the set of all languages over Σ). Then the union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
(written as +) and the concatenation (written as ·) of two elements of A again belong to A, and so does the Kleene star
Kleene star
In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...
operation applied to any element of A. We obtain a Kleene algebra A with 0 being the empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
and 1 being the set that only contains the empty string.
Let M be a monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
with identity element e and let A be the set of all subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s 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
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
.
Suppose M is a set and A is the set of all binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
s 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
and turns into a Kleene algebra if we use for +, for · and set a* = 1 for all a.A quite different Kleene algebra is useful when computing shortest path
Shortest path problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
s in weighted directed graphs
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
: let A be the extended real number line
Extended real number line
In mathematics, the affinely extended real number system is obtained from the real number system R by adding two elements: +∞ and −∞ . The projective extended real number system adds a single object, ∞ and makes no distinction between "positive" or "negative" infinity...
, 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
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
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 complete set of axioms which would allow derivation of all equations among regular expressions. The problem was first studied by John Horton ConwayJohn Horton Conway
John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...
under the name of regular algebras. The axioms of Kleene algebras solve this problem, as was first shown by Dexter Kozen.
See also
- Action algebraAction algebraIn algebraic logic, an action algebra is an algebraic structure which is both a residuated semilattice and a Kleene algebra. It adds the star or reflexive transitive closure operation of the latter to the former, while adding the left and right residuation or implication operations of the former...
- Algebraic structureAlgebraic structureIn abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
- Kleene starKleene starIn mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...
- Regular expressionRegular expressionIn computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...