Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Nineteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2004)

Paper: Transition Invariants (at LICS 2004)

Authors: Andreas Podelski Andrey Rybalchenko

Abstract

Proof rules for program verification rely on auxiliary assertions. We propose a (sound and relatively complete) proof rule whose auxiliary assertions are transition invariants. A transition invariant of a program is a binary relation over program states that contains the transitive closure of the transition relation of the program. A relation is disjunctively well-founded if it is a finite union of well-founded relations. We characterize the validity of termination or another liveness property by the existence of a disjunctively well-founded transition invariant. The main contribution of our proof rule lies in its potential for automation via abstract interpretation.

BibTeX

  @InProceedings{PodelskiRybalchenko-TransitionInvariant,
    author = 	 {Andreas Podelski and Andrey Rybalchenko},
    title = 	 {Transition Invariants},
    booktitle =  {Proceedings of the Nineteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2004)},
    year =	 {2004},
    month =	 {July}, 
    pages =      {32--41},
    location =   {Turku, Finland}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski