Paper: Transition Invariants (at LICS 2004)
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} }