5 Kleene and Omega Algebra

Kleene and Omega Algebra [Slide 20]

Let K denote 𝒫(Σ⁺ ∪ Σ^ω),

(K,∪,∅,⋅,Σ) is an idempotent left semiring iff (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 iff a ∪b = b

Kleene and Omega Algebra [Slide 21]

(K,∼ ) is a Boolean idempotent left semiring iff

• (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 iff

• (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 iff

• (K,^∗) is a Boolean strong left (lazy) Kleene algebra
• a^ω = a ⋅a^ω
• c ⊆b ∪a ⋅c implies c ⊆a^ω ∪a^∗⋅b