PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
create new user
forget your password?
Main Menu
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$.

Regular expressions are a form (or close variant) of a Kleene algebra.

"Kleene algebra" is owned by Logan.
(view preamble)

View style:

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

Cross-references: regular expressions, satisfies, Kleene star, operator, unary, idempotent semiring
There are 2 references to this entry.

This is version 2 of Kleene algebra, born on 2002-02-24, modified 2002-05-03.
Object id is 2618, canonical name is KleeneAlgebra.
Accessed 2627 times total.

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
Style: Expand: Order:
forum policy

No messages.

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