nLab Kleene algebra

This page is about de Morgan algebras satisfying an extra condition. For Kleene algebras in relation to regular expressions, see Kleene star algebra.

---

Definition

A Kleene algebra is a de Morgan algebra $D$ satisfying $x \wedge \neg x \le y \vee \neg y$ for all $x,y\in D$. Since the order is definable in terms of the lattice operators, this can be stated as the equation

$$x \wedge \neg x \wedge (y \vee \neg y) = x \wedge \neg x.$$

Examples

• Any Boolean algebra is a Kleene algebra, with $\neg$ the logical negation.
• The unit interval $[0,1]$ is a Kleene algebra, with $\neg x = (1-x)$.
• More generally, any bounded interval $[a, b]$ in a lattice-ordered abelian group is a Kleene algebra, with $\neg x = a + b - x$.

Related concepts

• Kleene algebras are used in one form of cubical type theory

• Boolean algebra

• de Morgan algebra

• l-group

 References

• Wikipedia, Kleene algebra (with involution)

• William H Cornish, Peter R Fowler, Coproducts of de morgan algebras, Bulletin of the Australian Mathematical Society, 16(01):1–13, 1977. (pdf)

• William H Cornish, Peter R Fowler, Coproducts of kleene algebras, Journal of the Australian Mathematical Society (Series A), 27(02):209–220, 1979 (pdf)

• Ulrik Buchholtz, Edward Morehouse, (2017). Varieties of Cubical Sets. In: Peter Höfner, Damien Pous, Georg Struth (eds) Relational and Algebraic Methods in Computer Science. RAMICS 2017. Lecture Notes in Computer Science, vol 10226. Springer, Cham. (doi:10.1007/978-3-319-57418-9_5, arXiv:1701.08189)

• What’s the deal with De Morgan algebras and Kleene algebras?, MathOverflow (web)