ITL
© 1996-2018







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-25
Contact | Home | ITL home | Course | Proofs | Algebra | FL