Kleene Algebra

A Kleene algebra is a Star Semiring $(A,0,+,1,\cdot,(-)^{*})$ that satisfies the following additional axioms.

• $+$ is Idempotent and Commutative; EG: $(A,+,0)$ is a Join Semilattice.
• if $xa+x=x$, then $xa^{*}+x=x$.
• if $ax+x=x$, then $a^{*}x+x=x$.

The final 4 axioms are more neatly presented as inequalities, with $a\leq b$ defined to be $a+b=b$.

• $1+aa^{*}\leq a^{*}$
• $1+a^{*}a\leq a^{*}$
• $ax\leq x\Rightarrow a^{*}x\leq x$
• $xa\leq x\Rightarrow xa^{*}\leq x$