PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
Kleene algebra (Definition)

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{displaymath} \begin{array}{ll} 1+aa^*\leq a^*, & ac+b\leq c\Rightarrow a^... ...1+a^*a\leq a^*, & ca+b\leq c\Rightarrow ba^*\leq c, \end{array}\end{displaymath}

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

$\displaystyle a^*=\lbrace \lambda \rbrace \cup a \cup a^2 \cup \cdots \cup a^n \cup \cdots,$
so that
$\displaystyle aa^*=a \cup a^2 \cup \cdots \cup a^n \cup \cdots.$
Adding $ 1$ on both sides and we have
$\displaystyle 1+aa^*=\lbrace \lambda \rbrace \cup aa^*=\lbrace \lambda \rbrace \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.



"Kleene algebra" is owned by CWoo. [ full author list (2) | owner history (2) ]
(view preamble | get metadata)

View style:

See Also: Kleene star, semiring, regular expression, regular language, Kleene algebra


Attachments:
characterization of a Kleene algebra (Definition) by CWoo
Log in to rate this entry.
(view current ratings)

Cross-references: sides, union, operation, concatenation, empty string, singleton, regular expressions, regular languages, languages, alphabet, Kleene star, operator, unary, idempotent semiring
There are 4 references to this entry.

This is version 6 of Kleene algebra, born on 2002-02-24, modified 2008-05-14.
Object id is 2618, canonical name is KleeneAlgebra.
Accessed 4038 times total.

Classification:
AMS MSC68Q70 (Computer science :: Theory of computing :: Algebraic theory of languages and automata)
 20M35 (Group theory and generalizations :: Semigroups :: Semigroups in automata theory, linguistics, etc.)

Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)