---
tag: 2D4E6NY8Q4
kind: definition
name: Kleene algebra
msc: ["16Y60", "68Q70", "68Q45"]
defines: BK4DDS24XC
uses: [NA44T2NZE2, 27ZPTJP9PP, 08EJC6Q25H]
sources:
  - url: https://en.wikipedia.org/wiki/Kleene_algebra
---

## Definition

Let $(K, +, \cdot, 0, 1)$ be an [[idempotent semiring|NA44T2NZE2]], with the order $a \le b \iff a + b = b$.
Let $^*$ be a unary operation on $K$.
The structure $(K, +, \cdot, ^*, 0, 1)$ is a *Kleene algebra* if for all $a, b, x \in K$:

1. $1 + a \cdot a^* \le a^*$;
2. $1 + a^* \cdot a \le a^*$;
3. if $b + a \cdot x \le x$, then $a^* \cdot b \le x$;
4. if $b + x \cdot a \le x$, then $b \cdot a^* \le x$.

## Remarks

Clauses 1 and 3 say that $a^* b$ is the least $x$ with $b + a x \le x$.
Example: let $\Sigma^*$ be the [[free monoid|27ZPTJP9PP]] on an alphabet $\Sigma$, and let $K$ be the set of languages $L \subseteq \Sigma^*$.
With union, concatenation, $0 = \emptyset$, $1 = \set{\varepsilon}$ and $L^* = \bigcup_{n \ge 0} L^n$, this is a Kleene algebra.
Indeed, $L^* B$ is the set of words $w_1 \cdots w_n u$ with $w_i \in L$ and $u \in B$, and each such word lies in any $X$ with $B \cup L X \subseteq X$, by induction on $n$.
Example: the [[binary relations|08EJC6Q25H]] on a set, with union, composition and reflexive transitive closure as $^*$, form a Kleene algebra.
Non-example: the Boolean semiring $\set{0, 1}$ with $a^* = a$ fails clause 1, since for $a = 0$ it says $1 + 0 \le 0$.
With $a^* = 1$ for all $a$, the Boolean semiring is a Kleene algebra.
In every Kleene algebra $a^* = 1 + a a^*$ and $a^* a^* = a^*$.