Paper: On Hoare Logic and Kleene Algebra with Tests (at LICS 1999)

Authors: Dexter C. Kozen

Abstract

We show that Kleene algebra with tests subsumes propositional Hoare logic. Thus the specialized syntax and deductive apparatus of Hoare logic are inessential and can be replaced by ordinary equational reasoning. It follows from the reduction that propositional Hoare logic is in PSPACE; we show that it is PSPACE-complete.

BibTeX

  @InProceedings{Kozen-OnHoareLogicandKlee,
    author = 	 {Dexter C. Kozen},
    title = 	 {On Hoare Logic and Kleene Algebra with Tests},
    booktitle =  {Proceedings of the Fourteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1999)},
    year =	 {1999},
    month =	 {July}, 
    pages =      {167--172},
    location =   {Trento, Italy}, 
    publisher =	 {IEEE Computer Society Press}
  }