Sixteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2001)

Paper: Intuitionistic Linear Logic and Partial Correctness (at LICS 2001)

Authors: Dexter Kozen Jerzy Tiuryn


We formulate a Gentzen-style sequent calculus for partial correctness that subsumes propositional Hoare Logic. The system is a noncommutative intuitionistic Linear Logic. We prove soundness and completeness over relational and trace models. As a corollary we obtain a complete sequent calculus for inclusion and equivalence of regular expressions.


    author = 	 {Dexter Kozen and Jerzy Tiuryn},
    title = 	 {Intuitionistic Linear Logic and Partial Correctness},
    booktitle =  {Proceedings of the Sixteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2001},
    year =	 2001,
    editor =	 {Joseph Halpern},
    month =	 {June}, 
    pages =      {259--268},
    location =   {Boston, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}