Kleene Algebras with Domain

Victor B. F. Gomes, Walter Guttmann, Peter Höfner, Georg Struth, and Tjark Weber. Archive of Formal Proofs, April 2016. Formal proof development.


Kleene algebras with domain are Kleene algebras endowed with an operation that maps each element of the algebra to its domain of definition (or its complement) in abstract fashion. They form a simple algebraic basis for Hoare logics, dynamic logics or predicate transformer semantics. We formalise a modular hierarchy of algebras with domain and antidomain (domain complement) operations in Isabelle/HOL that ranges from domain and antidomain semigroups to modal Kleene algebras and divergence Kleene algebras. We link these algebras with models of binary relations and program traces. We include some examples from modal logics, termination and program analysis.


The original publication is available at http://afp.sf.net/entries/KAD.shtml.


  author   = {Victor B. F. Gomes and Walter Guttmann and Peter H{\"{o}}fner and Georg Struth and Tjark Weber},
  title    = {{Kleene} Algebras with Domain},
  journal  = {Archive of Formal Proofs},
  month    = apr,
  year     = {2016},
  note     = {\url{http://afp.sf.net/entries/KAD.shtml}, Formal proof development}

Last modified: 2016-07-06