characterization of a Kleene algebra

Let A be an idempotent semiring with a unary operator * on A. The following are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath

  1. 1.

    ac+bc implies a*bc,

  2. 2.

    abb implies a*bb.


(12). Assume abb. So ab+b=b. Then (ab+b)+b=ab+(b+b)=ab+b=b, which implies ab+bb. By 1, this means a*bb as desired. (21). Assume ac+bc. Since 0b, we get ac=ac+0ac+bc. Consequently a*cc. ∎

From the above observation, we see that we get an equivalent definition of a Kleene algebra if the axioms

ac+bc implies a*bc  and  ca+bc implies ba*c

are replaced by

abb implies a*bb  and  bab implies ba*b.

Let A be a Kleene algebra. Some of the interesting properties of * on A are the following:

  1. 1.


  2. 2.

    ana* for all non-negative integers n.

  3. 3.


  4. 4.


  5. 5.


  6. 6.

    ab implies a*b*.

  7. 7.


  8. 8.


  9. 9.


  10. 10.


  11. 11.

    accb implies a*ccb*.

  12. 12.

    cbac implies cb*a*c.

  13. 13.


  14. 14.


  15. 15.

    If c=c2 and 1c, then c*=c.

  16. 16.



  • Properties 9 and 10 imply that the axioms 1+aa*a* and 1+a*aa* of a Kleene algebra can be replaced by these stronger ones.

  • Though in the example of Kleene algebras formed by regular expressionsMathworldPlanetmath,


    and we see that a* is the least upper bound of the ai’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 K *-continuous if a*b whenever aib for any i{0}, and a,bK.


  • 1 D. Kozen, kozen/papers/kacs.psOn Kleene Algebras and Closed Semirings (1990).
Title characterizationMathworldPlanetmath of a Kleene algebra
Canonical name CharacterizationOfAKleeneAlgebra
Date of creation 2013-03-22 17:02:40
Last modified on 2013-03-22 17:02:40
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 12
Author CWoo (3771)
Entry type Definition
Classification msc 20M35
Classification msc 68Q70
Defines *-continuous