© 1996-2019

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

 2019-01-03 Contact | Home | ITL home | Course | Proofs | Algebra | FL