## You are here

HomeKleene algebra

## Primary tabs

# 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^{*},&ac+b\leq c\Rightarrow a^{*}b\leq c,\\ 1+a^{*}a\leq a^{*},&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.

## Mathematics Subject Classification

20M35*no label found*68Q70

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections