loading...
Transition Invariants
Turku, Finland July 13-July 17
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2004.131959819th Annual IEEE Symposium on Logic i ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Andreas Podelski, Max-Planck-Institut f?r Informatik, Saarbr?cken, Germany
Andrey Rybalchenko, Max-Planck-Institut f?r Informatik, Saarbr?cken, Germany
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.
Citation:
Andreas Podelski, Andrey Rybalchenko, "Transition Invariants," lics, pp.32-41, 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.