nLab Kleene star algebra

This page is about the rigs with a Kleene star closure operation. For the de Morgan algebra, see Kleene algebra.

---

Idea

A Kleene algebra is a semiring or rig that generalizes the theory of regular expressions: it consists of a set with union (semiring addition), concatenation (semiring multiplication), and closure operation (Kleene star).

Disambiguation note: This article is titled Kleene star algebra solely for disambiguation purposes as Kleene algebra already refers to the de Morgan algebra, and this rig is the only one with a Kleene star. In the existing literature, these objects are simply called Kleene algebras.

Definition

A Kleene algebra is an additively idempotent semiring $(R, 0, \vee, \epsilon, (-)(-))$ with a function $(-)^*:R \to R$

• for all $x \in R$, $(\epsilon \vee x x^*) \vee x^* = x^*$

• for all $x \in R$, $(\epsilon \vee x^* x) \vee x^* = x^*$

• for all $x \in R$ and $y \in R$, if $x y \vee y = y$, then $x^* y \vee y = y$

• for all $x \in R$ and $y \in R$, if $y x \vee y = y$, then $y x^* \vee y = y$

Examples

• The Kleene algebras of regular expressions are the free Kleene algebras on finite sets.

Related concepts

• semiring, rig

• additively idempotent semiring

• quasiregular semiring

• semilattice

• regular expression

References

• Wikipedia, Kleene algebra

• John Horton Conway, Regular Algebra and Finite Machines. Mineola, N.Y., Dover; Newton Abbot, 2012. ISBN:978-0486485836

• Dexter Kozen (1990). On Kleene algebras and closed semirings. In: Branislav Rovan (editor). Mathematical Foundations of Computer Science 1990. MFCS 1990. Lecture Notes in Computer Science, vol 452. Springer, Berlin, Heidelberg. (doi:10.1007/BFb0029594, pdf)

• Damien Pous, Jurriaan Rot, Jana Wagemaker, On Tools for Completeness of Kleene Algebra with Hypotheses, Logical Methods in Computer Science, Volume 20, Issue 2 (May 16, 2024). (doi:10.46298/lmcs-20(2:8)2024, arXiv:2210.13020)

• Damien Pous, Jana Wagemaker, Completeness Theorems for Kleene algebra with tests and top, Logical Methods in Computer Science, Volume 20, Issue 3 (September 30, 2024). (doi:10.46298/lmcs-20(3:27)2024, arXiv:2304.07190)

• Jana Wagemaker, Extensions of (Concurrent) Kleene Algebra, Thesis (pdf)