Logic in Computer Science (LICS 1999)

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

Authors: Dexter 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 Kozen},
    title = 	 {On Hoare Logic and Kleene Algebra with Tests},
    booktitle =  {Proceedings of the Fourteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1999},
    year =	 1999,
    editor =	 {Giuseppe Longo},
    month =	 {July}, 
    pages =      {167--172},
    location =   {Trento, Italy}, 
    publisher =	 {IEEE Computer Society Press}
  }