# Kleene algebra

A Kleene algebra $(A,\cdot,+,^{*},0,1)$ is an idempotent semiring $(A,\cdot,+,0,1)$ with an additional (right-associative) unary operator ${}^{*}$, called the Kleene star, which satisfies

 $\begin{array}[]{rl}1+aa^{*}\leq a^{*},&\qquad ac+b\leq c\Rightarrow a^{*}b\leq c% ,\\ 1+a^{*}a\leq a^{*},&\qquad ca+b\leq c\Rightarrow ba^{*}\leq c,\end{array}$

for all $a,b,c\in A$.

For a given alphabet $\Sigma$, the set of all languages over $\Sigma$, as well as the set of all regular languages over $\Sigma$, are examples of Kleene algebras. Similarly, sets of regular expressions (regular sets) over $\Sigma$ are a form (or close variant) of a Kleene algebra: let $A$ be the set of all regular sets over a set $\Sigma$ of alphabets. Then $A$ is a Kleene algebra if we identify $\varnothing$ as $0$, the singleton containing the empty string $\lambda$ as $1$, concatenation operation as $\cdot$, the union operation as $+$, and the Kleene star operation as ${}^{*}$. For example, let $a$ be a set of regular expression, then

 $a^{*}=\{\lambda\}\cup a\cup a^{2}\cup\cdots\cup a^{n}\cup\cdots,$

so that

 $aa^{*}=a\cup a^{2}\cup\cdots\cup a^{n}\cup\cdots.$

Adding $1$ on both sides and we have

 $1+aa^{*}=\{\lambda\}\cup aa^{*}=\{\lambda\}\cup a\cup a^{2}\cup\cdots\cup a^{n% }\cup\cdots=a^{*}.$

The other conditions are checked similarly.

Remark. There is another notion of a Kleene algebra, which arises from lattices. For more detail, see here (http://planetmath.org/KleeneAlgebra2).

 Title Kleene algebra Canonical name KleeneAlgebra Date of creation 2013-03-22 12:27:51 Last modified on 2013-03-22 12:27:51 Owner CWoo (3771) Last modified by CWoo (3771) Numerical id 10 Author CWoo (3771) Entry type Definition Classification msc 20M35 Classification msc 68Q70 Related topic KleeneStar Related topic Semiring Related topic RegularExpression Related topic RegularLanguage Related topic KleeneAlgebra2