5    Kleene and Omega Algebra
   
   
Kleene and Omega Algebra [Slide 20]
Let K denote š«(Ī£+ ⪠ΣĻ),
   (K,āŖ,ā
,ā
,Ī£) is an idempotent left semiring iļ¬  (for a,b,c ā K) 
       
- 
(K,āŖ,ā
) is a commutative monoid , i.e.,
 a āŖb  = b āŖa
 a āŖā
 = a
 a āŖ (b āŖc)  = (a āŖb) āŖc
 
-        
(K,ā
,Ī£) is a monoid, i.e.,
 a ā
Ī£  = a
 Ī£ ā
a  = a
 a ā
 (b ā
c)  = (a ā
b) ā
c
 
- (a āŖb) ā
c  = a ā
c āŖb ā
c
- ā
ā
a  = ā
- a āŖa  = a
                                                                  
            
                                                                                        
- b  āc implies a ā
b  āa ā
c where a  āb iļ¬ a āŖb  = b
            
               
Kleene and Omega Algebra [Slide 21]
(K,ā¼ ) is a Boolean idempotent left semiring iļ¬ 
                   
- (K,āŖ,ā
,ā
,Ī£) is an idempotent left semiring
- a  = ā¼(ā¼a āŖā¼b) āŖā¼(ā¼a āŖb) (Huntington equation)
As usual we have the following 
                   
- a ā©b  = ā¼(ā¼a āŖā¼b)
- T = a āŖā¼a (greatest element w.r.t.  ā, i.e. Ī£+ ⪠ΣĻ)
- ā
 = a ā©ā¼a (smallest element w.r.t.  ā, i.e., ā
)
            
               
Kleene and Omega Algebra [Slide 22]
(K,ā) is a Boolean strong left (lazy) Kleene algebra iļ¬ 
                                                                  
            
                                                                                                        
                   
- (K,ā¼ ) is a Boolean idempotent left semiring
- Ī£ āŖa ā
aāāaā
- b āŖa ā
c  āc implies aāā
b  āc
- b āŖc ā
a  āc implies b ā
aāāc
(K,Ļ) is a Boolean left (lazy) omega algebra iļ¬ 
                   
- (K,ā) is a Boolean strong left (lazy) Kleene algebra
- aĻ  = a ā
aĻ
- c  āb āŖa ā
c implies c  āaĻ āŖaāā
b