# characterization of a Kleene algebra

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

1. 1.

$ac+b\leq c$ implies $a^{*}b\leq c$,

2. 2.

$ab\leq b$ implies $a^{*}b\leq b$.

###### Proof.

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

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

 $ac+b\leq c\mbox{ implies }a^{*}b\leq c\qquad\mbox{and}\qquad ca+b\leq c\mbox{ % implies }ba^{*}\leq c$

are replaced by

 $ab\leq b\mbox{ implies }a^{*}b\leq b\qquad\mbox{and}\qquad ba\leq b\mbox{ % implies }ba^{*}\leq b.$

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

1. 1.

$0^{*}=1$.

2. 2.

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

3. 3.

$1^{*}a\leq a$.

4. 4.

$1^{*}=1$.

5. 5.

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

6. 6.

$a\leq b$ implies $a^{*}\leq b^{*}$.

7. 7.

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

8. 8.

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

9. 9.

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

10. 10.

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

11. 11.

$ac\leq cb$ implies $a^{*}c\leq cb^{*}$.

12. 12.

$cb\leq ac$ implies $cb^{*}\leq a^{*}c$.

13. 13.

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

14. 14.

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

15. 15.

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

16. 16.

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

Remarks.

• Properties 9 and 10 imply that the axioms $1+aa^{*}\leq a^{*}$ and $1+a^{*}a\leq 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,\ldots\},$

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$ ${}^{*}$-continuous if $a^{*}\leq b$ whenever $a^{i}\leq b$ for any $i\in\mathbb{N}\cup\{0\}$, and $a,b\in K$.

## References

• 1 D. Kozen, http://www.cs.cornell.edu/ kozen/papers/kacs.psOn Kleene Algebras and Closed Semirings (1990).
Title characterization of a Kleene algebra CharacterizationOfAKleeneAlgebra 2013-03-22 17:02:40 2013-03-22 17:02:40 CWoo (3771) CWoo (3771) 12 CWoo (3771) Definition msc 20M35 msc 68Q70 ${}^{*}$-continuous