ITL
© 1996-2015







5 Kleene and Omega Algebra

Let K denote P (Σ+ ∪ Σ ω) ,

(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

    --
(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., ∅ )

(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