cyclic: Address reaches a cycle. Definition: cyclic(x,A,F,M) = (\exists v: reach(x,v,A,F,M) & incycle(v,A,F,M)) Wp: wlp(M := M[i <- c], cyclic(x,A,F,M)) = (rewriting) wlp(M := M[i <- c], (\exists v: reach(x,v,A,F,M) & incycle(v,A,F,M))) = (wlp for deterministic, terminating action) (\exists v: wlp(M := M[i <- c], reach(x,v,A,F,M)) & wlp(M := M[i <- c], incycle(v,A,F,M))) = (wlp for reach, incycle) (\exists v: (reach(x,v,Ai,F,M) | ~A(i) & reach(x,i,Ai,F,M) & reach(c,v,Ai,F,M)) & ( incycle(v,Ai,F,M) | reach(v,i,Ai,F,M) & reach(c,v,Ai,F,M) & ~A(i))) = (expanding out and distributing \exists over |) (\exists v: reach(x,v,Ai,F,M) & incycle(v,Ai,F,M)) | (\exists v: reach(x,v,Ai,F,M) & ~A(i) & reach(v,i,Ai,F,M) & reach(c,v,Ai,F,M)) | (\exists v: ~A(i) & reach(x,i,Ai,F,M) & reach(c,v,Ai,F,M) & incycle(v,Ai,F,M)) | (\exists v: ~A(i) & reach(x,i,Ai,F,M) & reach(c,v,Ai,F,M) & reach(v,i,Ai,F,M)) = (rewriting; Lemma 0 (below)) cyclic(x,Ai,F,M) | (\exists v: reach(x,v,Ai,F,M) & ~A(i) & reach(v,i,Ai,F,M) & reach(c,v,Ai,F,M)) | ~A(i) & reach(x,i,Ai,F,M) & (\exists v: reach(c,v,Ai,F,M) & incycle(v,Ai,F,M)) | (\exists v: ~A(i) & reach(x,i,Ai,F,M) & reach(c,v,Ai,F,M) & reach(v,i,Ai,F,M)) = (dropping stronger term (2)=>(4) and simplifying) cyclic(x,Ai,F,M) | ~A(i) & reach(x,i,Ai,F,M) & cyclic(c,Ai,F,M) | ~A(i) & reach(x,i,Ai,F,M) & (\exists v: reach(c,v,Ai,F,M) & reach(v,i,Ai,F,M)) = (simplifying) cyclic(x,Ai,F,M) | ~A(i) & reach(x,i,Ai,F,M) & cyclic(c,Ai,F,M) | ~A(i) & reach(x,i,Ai,F,M) & reach(c,i,Ai,F,M) Lemma 0: F*(w,k,Ai) = F*(w,k,A) if F(i)={undefined} Proof: It is easy to show that [F*(w,k,Ai) => F*(w,k,A)]. In the other direction, we use property (1) of fixpoints. For this proof, we'll consider F* to denote the fixpoint in the actual F* definition; the addr(y) term can be handled seperately. We show that F*(w,k,Ai) satisfies the equation for F*(w,k,A), i.e., [addr(x) & (x=k | ~A(x) & F*(F(x),k,Ai)) => F*(x,k,Ai)], which has two subgoals. (i) [addr(x) & x=k => F*(x,k,Ai)], which is true by fixpoint equation for F*, and (ii) [addr(x) & ~A(x) & F*(F(x),k,Ai) => F*(x,k,Ai)] = (splitting into cases) [addr(x) & ~A(x) & x\neq i & F*(F(x),k,Ai) => F*(x,k,Ai)] and [addr(x) & ~A(x) & x=i & F*(F(x),k,Ai) => F*(x,k,Ai)] = (first term true by fixpoint expansion of F*(Ai,x); [addr(x) & ~A(x) & x=i & F*(F(x),k,Ai) => F*(x,k,Ai)] = (using x=i) [addr(x) & ~A(x) & x=i & F*(F(i),k,Ai) => F*(x,k,Ai)] = (using F(i)={undefined}, the F* term on the left is false) true []