characterization of a Kleene algebra
Let be an idempotent semiring with a unary operator on . The following are equivalent
- 1.
implies ,
- 2.
implies .
Proof.
. Assume . So . Then , which implies . By , this means as desired. . Assume . Since , we get . Consequently .∎
From the above observation, we see that we get an equivalent definition of a Kleene algebra if the axioms
are replaced by
Let be a Kleene algebra. Some of the interesting properties of on are the following:
- 1.
.
- 2.
for all non-negative integers .
- 3.
.
- 4.
.
- 5.
.
- 6.
implies .
- 7.
.
- 8.
.
- 9.
.
- 10.
.
- 11.
implies .
- 12.
implies .
- 13.
.
- 14.
.
- 15.
If and , then .
- 16.
.
Remarks.
- •
Properties 9 and 10 imply that the axioms and of a Kleene algebra can be replaced by these stronger ones.
- •
Though in the example of Kleene algebras formed by regular expressions
,
and we see that is the least upper bound of the ’s, this is not a property of a general Kleene algebra. A counterexample of this can be found in Kozen’s article, see below. He calls a Kleene algebra -continuous if whenever for any , and .
References
- 1 D. Kozen, http://www.cs.cornell.edu/ kozen/papers/kacs.psOn Kleene Algebras and Closed Semirings (1990).