Transition Invariants

718 views · Published 6 September 2016 · 44:31 · Indexed 10 November 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

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.

More from this channel