Transition Invariants
718 views · Published 6 September 2016 · 44:31 · Indexed 10 November 2026
Channel: Microsoft Research · 2016 · Science & Technology
Proof rules for the temporal verification of concurrent programs 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 transition invariant is disjunctively well-founded if it is a finite union of well-founded relations. We characterize the validity of a liveness property by the existence of a disjunctively well-founded transition invariant.