Kleene algebra

In mathematics, a Kleene algebra (/ˈkleɪni/ KLAY-nee; named after Stephen Cole Kleene) is an idempotent (and thus partially ordered) semiring endowed with a closure operator.^[1] It generalizes the operations known from regular expressions.

Definition

Various inequivalent definitions of Kleene algebras and related structures have been given in the literature.^[2] 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.
Annihilation by 0: 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 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 ^[3]

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".

Examples

Notational correspondence between
Kleene algebras and	+	·	^*	0	1
Regular expressions	\|	not written	^*	∅	ε

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.

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 $V \cdot W = span {v \cdot w | v \in V, w \in W}$ , the linear span of the product of vectors from V and W respectively. Define $1 = span {I}$ , 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.^[4]

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, a₁ + ... + a_n is the least upper bound of the elements a₁, ..., a_n.

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 star operation, we have

0^* = 1 and 1^* = 1,
a ≤ b implies a^* ≤ b^* (monotonicity),
aⁿ ≤ a^* for every natural number n, where aⁿ 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)^*.^[5]

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.

History

Kleene introduced regular expressions and gave some of their algebraic laws.^[6]^[7] Although he didn't define Kleene algebras, he asked for a decision procedure for equivalence of regular expressions.^[8] Redko proved that no finite set of equational axioms can characterize the algebra of regular languages.^[9] Salomaa gave complete axiomatizations of this algebra, however depending on problematic inference rules.^[10] The problem of providing a complete set of axioms, which would allow derivation of all equations among regular expressions, was intensively studied by John Horton Conway under the name of regular algebras,^[11] however, the bulk of his treatment was infinitary. In 1981, Kozen gave a complete infinitary equational deductive system for the algebra of regular languages.^[12] 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.^[13]

Generalization (or relation to other structures)

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.^[14]^[15] In a Kleene algebra, a* is the least solution to the fixpoint equations: X = aX + 1 and X = Xa + 1.^[15]

Closed semirings and Kleene algebras appear in algebraic path problems, a generalization of the shortest path problem.^[15]

References

^ Marc Pouly; Jürg Kohlas (2011). Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. p. 246. ISBN 978-1-118-01086-0.
^ For a survey, see: Kozen, Dexter (1990). "On Kleene algebras and closed semirings" (PDF). In Rovan, Branislav (ed.). Mathematical foundations of computer science, Proc. 15th Symp., MFCS '90, Banská Bystrica/Czech. 1990. Lecture Notes Computer Science. Vol. 452. Springer-Verlag. pp. 26–47. Zbl 0732.03047.
^ Kozen (1990), sect.2.1, p.3
^ Gross, Jonathan L.; Yellen, Jay (2003), Handbook of Graph Theory, Discrete Mathematics and Its Applications, CRC Press, p. 65, ISBN 9780203490204.
^ Kozen (1990), sect.2.1.2, p.5
^ S.C. Kleene (Dec 1951). Representation of Events in Nerve Nets and Finite Automata (PDF) (Technical report). U.S. Air Force / RAND Corporation. p. 98. RM-704. Here: sect.7.2, p.52
^ Kleene, Stephen C. (1956). "Representation of Events in Nerve Nets and Finite Automata" (PDF). Automata Studies, Annals of Mathematical Studies. 34. Princeton Univ. Press. Here: sect.7.2, p.26-27
^ Kleene (1956), p.35
^ V.N. Redko (1964). "On defining relations for the algebra of regular events" (PDF). Ukrainskii Matematicheskii Zhurnal [uk]. 16 (1): 120–126. (In Russian)
^ Arto Salomaa (Jan 1966). "Two complete axiom systems for the algebra of regular events" (PDF). Journal of the ACM. 13 (1): 158–169. doi:10.1145/321312.321326. S2CID 8445404.
^ Conway, J.H. (1971). Regular algebra and finite machines. London: Chapman and Hall. ISBN 0-412-10620-5. Zbl 0231.94041. Chap.IV.
^ Dexter Kozen (1981). "On induction vs. ^*-continuity" (PDF). In Dexter Kozen (ed.). Proc. Workshop Logics of Programs. Lect. Notes in Comput. Sci. Vol. 131. Springer. pp. 167–176.
^ Dexter Kozen (May 1994). "A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events" (PDF). Information and Computation. 110 (2): 366–390. doi:10.1006/inco.1994.1037. — An earlier version appeared as: Dexter Kozen (May 1990). A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events (Technical report). Cornell. p. 27. TR90-1123.
^ Jonathan S. Golan (30 June 2003). Semirings and Affine Equations over Them. Springer Science & Business Media. pp. 157–159. ISBN 978-1-4020-1358-4.
^ ^a ^b ^c Marc Pouly; Jürg Kohlas (2011). Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. pp. 232 and 248. ISBN 978-1-118-01086-0.