characterization of a Kleene algebra

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

1. $ac+b\le c$ implies $a^{*}b\le c$,

2. $ab\le b$ implies $a^{*}b\le b$.

Proof.

$(1\Rightarrow 2)$. Assume $ab\le b$. So $ab+b=b$. Then $(ab+b)+b=ab+(b+b)=ab+b=b$, which implies $ab+b\le b$. By $1$, this means $a^{*}b\le b$ as desired. $(2\Rightarrow 1)$. Assume $ac+b\le c$. Since $0\le b$, we get $ac=ac+0\le ac+b\le c$. Consequently $a^{*}c\le c$. ∎

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

$$ac+b\le c\text{ implies }{a}^{*}b\le c\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}ca+b\le c\text{ implies }b{a}^{*}\le c$$

are replaced by

$$ab\le b\text{ implies }{a}^{*}b\le b\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}ba\le b\text{ implies }b{a}^{*}\le b.$$

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

1. $0^{*}=1$.
   

2. $a^n\le a^{*}$ for all non-negative integers $n$.
   

3. $1^{*}a\le a$.
   

4. $1^{*}=1$.
   

5. $1+a^{*}=a^{*}$.
   

6. $a\le b$ implies $a^{*}\le b^{*}$.
   

7. $a^{*}{a}^{*}=a^{*}$.
   

8. $a^{**}=a^{*}$.
   

9. $1+a{a}^{*}=a^{*}$.
   

10. $1+a^{*}a=a^{*}$.
    

11. $ac\le cb$ implies $a^{*}c\le c{b}^{*}$.
    

12. $cb\le ac$ implies $c{b}^{*}\le a^{*}c$.
    

13. ${(ab)}^{*}a=a{(ba)}^{*}$.
    

14. $1+a{(ba)}^{*}b={(ab)}^{*}$.
    

15. If $c=c^2$ and $1\le c$, then $c^{*}=c$.
    

16. ${(a+b)}^{*}=a^{*}{(b{a}^{*})}^{*}$.
    

Remarks.

• Properties 9 and 10 imply that the axioms $1+a{a}^{*}\le a^{*}$ and $1+a^{*}a\le a^{*}$ of a Kleene algebra can be replaced by these stronger ones.

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

  $$a^{*}=\bigcup \{a^i\mid i=0,1,2,\mathrm{\dots }\},$$

  and we see that $a^{*}$ is the least upper bound of the $a^i$’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$ ${}^{\mathrm{*}}$-continuous if $a^{*}\le b$ whenever $a^i\le b$ for any $i\in \mathbb{N}\cup \{0\}$, and $a,b\in K$.

Title	characterization 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