# 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}{cc}\hfill 1+a{a}^{*}\le {a}^{*},& ac+b\le c\Rightarrow {a}^{*}b\le c,\hfill \\ \hfill 1+{a}^{*}a\le {a}^{*},& ca+b\le c\Rightarrow b{a}^{*}\le c,\hfill \end{array}$$ |

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

For a given alphabet $\mathrm{\Sigma}$, the set of all languages^{} over $\mathrm{\Sigma}$, as well as the set of all regular languages over $\mathrm{\Sigma}$, are examples of Kleene algebras. Similarly, sets of regular expressions^{} (regular sets) over $\mathrm{\Sigma}$ are a form (or close variant) of a Kleene algebra: let $A$ be the set of all regular sets over a set $\mathrm{\Sigma}$ of alphabets. Then $A$ is a Kleene algebra if we identify $\mathrm{\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 \mathrm{\cdots}\cup {a}^{n}\cup \mathrm{\cdots},$$ |

so that

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

Adding $1$ on both sides and we have

$$1+a{a}^{*}=\{\lambda \}\cup a{a}^{*}=\{\lambda \}\cup a\cup {a}^{2}\cup \mathrm{\cdots}\cup {a}^{n}\cup \mathrm{\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 |