|
|
|
|
Kleene algebra
|
(Definition)
|
|
|
A Kleene algebra
 is an idempotent semiring
 with an additional (right-associative) unary operator  , called the Kleene star, which satisfies
for all
 .
For a given alphabet  , the set of all languages over  , as well as the set of all regular languages over  , are examples of Kleene algebras. Similarly, sets of regular expressions (regular sets) over  are a form (or close variant) of a Kleene algebra: let  be the set of all regular sets over a set  of alphabets. Then  is a Kleene algebra if we identify
 as 0, the singleton containing the empty string  as  , concatenation operation as  , the union operation as  , and the Kleene star operation as  . For example, let  be a set of regular expression, then
so that
Adding  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.
|
"Kleene algebra" is owned by CWoo. [ full author list (2) | owner history (2) ]
|
|
(view preamble | get metadata)
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 MSC: | 68Q70 (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
|
|
|
|
|
|
|
|
|
|
|
