### 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

 2018-02-26 Contact | Home | ITL home | Course | Proofs | Algebra | FL