Kleene algebra

In mathematics and theoretical computer science, a Kleene algebra ( ; named after Stephen Cole Kleene) is a semiring that generalizes the theory of regular expressions: it consists of a set supporting union (addition), concatenation…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 7 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics and theoretical computer science, a Kleene algebra ( ; named after Stephen Cole Kleene) is a semiring that generalizes the theory of regular expressions: it consists of a set supporting union (addition), concatenation (multiplication), and Kleene star operations subject to certain algebraic laws. The addition is required to be idempotent ( x + x = x for all x ), and induces a partial order defined by x \le y if x + y = y . The Kleene star operation, denoted x^* , must satisfy the laws of a closure operator.

Kleene algebras have their origins in the theory of regular expressions and regular languages introduced by Kleene in 1951 and studied by others including V.N. Redko and John Horton Conway, who introduced the term in 1971. The concept was later popularized by Dexter Kozen in the 1980s, who fully characterized their algebraic properties and, in 1994, gave a finite axiomatization.

Kleene algebras have a number of extensions that have been studied, including Kleene algebras with tests (KAT) introduced by Kozen in 1997. Kleene algebras and Kleene algebras with tests have applications in formal verification of computer programs.

They have also been applied to specify and verify computer networks. : (a+b)+c = a+(b+c) and (ab)c=a(bc) 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 \cdot : for all a\in A we have a+0=0+a=a and a1=1a=a . Annihilation by 0 : a0=0a=0 for all a\in A . The above axioms define a semiring. We further require Idempotence of + : 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 any definition, a ≤ b ≤ a implies a = b). With this order we can formulate the last four 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". 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.

The linear subspaces of a unital algebra over a field form a Kleene algebra. Given linear subspaces V and W, define V + W to be the sum of the two subspaces, and 0 to be the trivial subspace {0}. Define , the linear span of the product of vectors from V and W respectively.

Define , the span of the unit of the algebra. The closure of V is the direct sum of all powers of V. V^{*} = \bigoplus_{i = 0}^{\infty} V^{i} 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 closure, we obtain a Kleene algebra.

Every Boolean algebra with operations \lor and \land turns into a Kleene algebra if we use \lor for +, \land for · and set a * = 1 for all a. A quite different Kleene algebra can be used to implement the Floyd–Warshall algorithm, computing the shortest path's length for every two vertices of a weighted directed graph, by Kleene's algorithm, computing a regular expression for every two states of a deterministic finite automaton. Using 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.

A weighted directed graph can then be considered as a deterministic finite automaton, with each transition labelled by its weight. For any two graph nodes (automaton states), the regular expressions computed from Kleene's algorithm evaluates, in this particular Kleene algebra, to the shortest path length between the nodes.

0 * = 1 and 1 * = 1, a ≤ b implies a * ≤ b * (monotonicity), a n ≤ a * for every natural number n, where a n is defined as n-fold multiplication of a, (a * )(a * ) = a * , (a * ) * = a * , 1 + a(a * ) = a * = 1 + (a * )a, ax = xb implies (a * )x = x(b * ), ((ab) * )a = a((ba) * ), (a+b) * = a * (b(a * )) * , and pq = 1 = qp implies q(a * )p = (qap) * . 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.

In 1994, he gave the above finite axiom system, which uses unconditional and conditional equalities (considering a ≤ b as an abbreviation for a + b = b), and is equationally complete for the algebra of regular languages, that is, two regular expressions a and b denote the same language only if a = b follows from the above axioms. Kleene algebras are a particular case of closed semirings, also called quasi-regular semirings or Lehmann semirings, which are semirings in which every element has at least one quasi-inverse satisfying the equation: a* = aa* + 1 = a*a + 1.

This quasi-inverse is not necessarily unique. In a Kleene algebra, a* is the least solution to the fixpoint equations: X = aX + 1 and X = Xa + 1. Closed semirings and Kleene algebras appear in algebraic path problems, a generalization of the shortest path problem.

See also

Action algebra Algebraic structure Kleene star Regular expression Star semiring Valuation algebra

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371080838 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

10 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.