Paper: Matching explicit and modal reasoning about programs: a proof theoretic delineation of dynamic logic (at LICS 2006)

Authors: Daniel Leivant

Abstract

We establish a match between two broad approaches to reasoning about programs: modal (dynamic logic) proofs on the one hand, and explicit higher-order reference to program semantics, on the other. We show that Pratt-Segerberg’s firstorder dynamic logic DL proves precisely program properties that are provable in second-order logic with set-existence restricted to a natural class of formulas, well-known to be related to computation theory

BibTeX

  @InProceedings{Leivant-Matchingexplicitand,
    author = 	 {Daniel Leivant},
    title = 	 {Matching explicit and modal reasoning about programs: a proof theoretic delineation of dynamic logic},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {157--166},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }