Kleene algebra

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 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 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^*$.