Kleene algebra

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


for all a,b,cA.

For a given alphabet Σ, the set of all languagesPlanetmathPlanetmath over Σ, as well as the set of all regular languages over Σ, are examples of Kleene algebras. Similarly, sets of regular expressionsMathworldPlanetmath (regular sets) over Σ are a form (or close variant) of a Kleene algebra: let A be the set of all regular sets over a set Σ of alphabets. Then A is a Kleene algebra if we identify as 0, the singleton containing the empty string λ as 1, concatenationMathworldPlanetmath operationMathworldPlanetmath as , the union operation as +, and the Kleene star operation as *. For example, let a be a set of regular expression, then


so that


Adding 1 on both sides and we have


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 SemiringMathworldPlanetmath
Related topic RegularExpression
Related topic RegularLanguage
Related topic KleeneAlgebra2