Lazy Kleene Algebra

摘要

We propose a relaxation of Kleene algebra by giving up strictness and right-distributivity of composition. This allows the sub-sumption of Dijkstra's computation calculus, Cohen's omega algebra and von Wright's demonic refinement algebra. Moreover, by adding domain and codomain operators we can also incorporate modal operators. Finally, it is shown that predicate transformers form lazy Kleene algebras again, the disjunctive and conjunctive ones even lazy Kleene algebras with an omega operation.