[Imprint][Data Privacy Statement][E-Mail]



View long theorem info. View the proof. Back to main index. View the specification. View theorem base summary, View theorem base listing, the used properties by spec, the dependency list, the symbol table,

Proof step 1 from proof step-D17-D6 (conclusion) (back to tree)

⊦ ( (ls.lst ∈ gs.orl + gs.qrl ∧ ls.nxt = gs.ps[ls.lst].next ∧ ls.nxt = gs.vs[ls.lst].next ∧ ls.nxt ≠ null) ∧ ( listp(gs.orl + gs.qrl, gs.vs, gs.ps, gs.owns) ∧ ¬ dups(gs.orl + gs.qrl) ∧ markedp(gs.orl, gs.ps) ∧ markedp(gs.orl, gs.vs) ∧ unmarkedp(gs.qrl, gs.ps) ∧ gs.orl ≠ [] ∧ gs.phead ∈ gs.orl ∧ rvownerok(gs.vretRefs, gs.vrvHp, gs.rvowns) ∧ allocrv(gs.vretRefs, gs.vrvHp) ∧ nonullRetRefs(gs.orl + gs.qrl, gs.vs, gs.vretRefs, gs.pretRefs) ∧ rvownerok(gs.pretRefs, gs.prvHp, gs.rvowns) ∧ allocrv(gs.pretRefs, gs.prvHp) ∧ dom gs.vrvHp = dom gs.prvHp ∧ ( gs.vs[gs.vhead].next ≠ null ∧ gs.vs[gs.vs[gs.vhead].next].deqID ≠ None → gs.rvowns(gs.vretRefs(gs.vs[gs.vs[gs.vhead].next].deqID.tid)) = Claimed(gs.vs[gs.vs[gs.vhead].next].deqID.tid, gs.vs[gs.vs[gs.vhead].next].val)) ∧ ( gs.orl.last = gs.vhead ∧ (gs.qrl ≠ [] → unmarkedp(gs.qrl.tail, gs.vs)) ∨ gs.orl.butlast ≠ [] ∧ gs.orl.butlast.last = gs.vhead ∧ gs.phead ≠ gs.orl.last ∧ unmarkedp(gs.qrl, gs.vs)) ∧ ( gs.vtail = (gs.orl + gs.qrl).last ∨ gs.qrl ≠ [] ∧ gs.vtail = (gs.orl + gs.qrl.butlast).last ∧ gs.vs[gs.qrl.last].deqID = None ∧ gs.vs[(gs.orl + gs.qrl).last].next = null)) ∧ (¬ ls.success ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid)) ∧ (gs.vretRefs(ls.tid) = ls.rvref ∧ gs.pretRefs(ls.tid) = ls.rvref ∧ ls.rvref ∈ gs.vrvHp ∧ ls.rvref ≠ null) ∧ nextnottid(ls.tid, gs.vhead, gs.vs) ∧ noid(ls.tid, gs.orl + gs.qrl, gs.vhead, gs.vs) ∧ noowns(ls.tid, gs.owns)) ∧ pre(gs, ls, D17, a) ∧ pcstepf(gs, ls, D17, a) = D6 → ( ( lstepf(gs, ls, D17, a).success → lstepf(gs, ls, D17, a).optval = gstepf(gs, ls, D17, a).vrvHp[lstepf(gs, ls, D17, a).rvref] ∧ lstepf(gs, ls, D17, a).optval = gstepf(gs, ls, D17, a).prvHp[lstepf(gs, ls, D17, a).rvref]) ∧ gstepf(gs, ls, D17, a).rvowns(gstepf(gs, ls, D17, a).vretRefs(lstepf(gs, ls, D17, a).tid)) = (lstepf(gs, ls, D17, a).optval = Empty ∨ ¬ lstepf(gs, ls, D17, a).success ⊃ Pending(lstepf(gs, ls, D17, a).tid) ;Claimed(lstepf(gs, ls, D17, a).tid, lstepf(gs, ls, D17, a).optval.val) )) ∧ ( listp (gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl, gstepf(gs, ls, D17, a).vs, gstepf(gs, ls, D17, a).ps, gstepf(gs, ls, D17, a).owns) ∧ ¬ dups(gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl) ∧ markedp(gstepf(gs, ls, D17, a).orl, gstepf(gs, ls, D17, a).ps) ∧ markedp(gstepf(gs, ls, D17, a).orl, gstepf(gs, ls, D17, a).vs) ∧ unmarkedp(gstepf(gs, ls, D17, a).qrl, gstepf(gs, ls, D17, a).ps) ∧ gstepf(gs, ls, D17, a).orl ≠ [] ∧ gstepf(gs, ls, D17, a).phead ∈ gstepf(gs, ls, D17, a).orl ∧ rvownerok(gstepf(gs, ls, D17, a).vretRefs, gstepf(gs, ls, D17, a).vrvHp, gstepf(gs, ls, D17, a).rvowns) ∧ allocrv(gstepf(gs, ls, D17, a).vretRefs, gstepf(gs, ls, D17, a).vrvHp) ∧ nonullRetRefs (gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl, gstepf(gs, ls, D17, a).vs, gstepf(gs, ls, D17, a).vretRefs, gstepf(gs, ls, D17, a).pretRefs) ∧ rvownerok(gstepf(gs, ls, D17, a).pretRefs, gstepf(gs, ls, D17, a).prvHp, gstepf(gs, ls, D17, a).rvowns) ∧ allocrv(gstepf(gs, ls, D17, a).pretRefs, gstepf(gs, ls, D17, a).prvHp) ∧ dom gstepf(gs, ls, D17, a).vrvHp = dom gstepf(gs, ls, D17, a).prvHp ∧ ( gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vhead].next ≠ null ∧ gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vhead].next].deqID ≠ None → gstepf(gs, ls, D17, a).rvowns (gstepf(gs, ls, D17, a).vretRefs(gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vhead].next].deqID.tid)) = Claimed (gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vhead].next].deqID.tid, gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vhead].next].val)) ∧ ( gstepf(gs, ls, D17, a).orl.last = gstepf(gs, ls, D17, a).vhead ∧ (gstepf(gs, ls, D17, a).qrl ≠ [] → unmarkedp(gstepf(gs, ls, D17, a).qrl.tail, gstepf(gs, ls, D17, a).vs)) ∨ gstepf(gs, ls, D17, a).orl.butlast ≠ [] ∧ gstepf(gs, ls, D17, a).orl.butlast.last = gstepf(gs, ls, D17, a).vhead ∧ gstepf(gs, ls, D17, a).phead ≠ gstepf(gs, ls, D17, a).orl.last ∧ unmarkedp(gstepf(gs, ls, D17, a).qrl, gstepf(gs, ls, D17, a).vs)) ∧ ( gstepf(gs, ls, D17, a).vtail = (gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl).last ∨ gstepf(gs, ls, D17, a).qrl ≠ [] ∧ gstepf(gs, ls, D17, a).vtail = (gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl.butlast).last ∧ gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).qrl.last].deqID = None ∧ gstepf(gs, ls, D17, a).vs[(gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl).last].next = null)) ∧ ( gstepf(gs, ls, D17, a).vretRefs(lstepf(gs, ls, D17, a).tid) = lstepf(gs, ls, D17, a).rvref ∧ gstepf(gs, ls, D17, a).pretRefs(lstepf(gs, ls, D17, a).tid) = lstepf(gs, ls, D17, a).rvref ∧ lstepf(gs, ls, D17, a).rvref ∈ gstepf(gs, ls, D17, a).vrvHp ∧ lstepf(gs, ls, D17, a).rvref ≠ null) ∧ nextnottid(lstepf(gs, ls, D17, a).tid, gstepf(gs, ls, D17, a).vhead, gstepf(gs, ls, D17, a).vs) ∧ noid (lstepf(gs, ls, D17, a).tid, gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl, gstepf(gs, ls, D17, a).vhead, gstepf(gs, ls, D17, a).vs) ∧ noowns(lstepf(gs, ls, D17, a).tid, gstepf(gs, ls, D17, a).owns)

System applied rule normalize

And obtained the following new goals

Rule argument

Additional information

Proof step 2 from proof step-D17-D6 (previous step) (back to tree)

ls.nxt = gs.ps[ls.lst].next, ls.nxt = gs.vs[ls.lst].next, gs.pretRefs(ls.tid) = ls.rvref, gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid), gs.vretRefs(ls.tid) = ls.rvref, dom gs.vrvHp = dom gs.prvHp, pcstepf(gs, ls, D17, a) = D6, ls.nxt ≠ null, gs.orl ≠ [], ls.rvref ≠ null, allocrv(gs.vretRefs, gs.vrvHp), allocrv(gs.pretRefs, gs.prvHp), listp(gs.orl + gs.qrl, gs.vs, gs.ps, gs.owns), markedp(gs.orl, gs.ps), markedp(gs.orl, gs.vs), nextnottid(ls.tid, gs.vhead, gs.vs), noid(ls.tid, gs.orl + gs.qrl, gs.vhead, gs.vs), nonullRetRefs(gs.orl + gs.qrl, gs.vs, gs.vretRefs, gs.pretRefs), noowns(ls.tid, gs.owns), pre(gs, ls, D17, a), rvownerok(gs.vretRefs, gs.vrvHp, gs.rvowns), rvownerok(gs.pretRefs, gs.prvHp, gs.rvowns), unmarkedp(gs.qrl, gs.ps), ls.lst ∈ gs.orl + gs.qrl, gs.phead ∈ gs.orl, ls.rvref ∈ gs.vrvHp, ¬ ls.success, ¬ dups(gs.orl + gs.qrl), gs.vs[gs.vhead].next ≠ null ∧ gs.vs[gs.vs[gs.vhead].next].deqID ≠ None → gs.rvowns(gs.vretRefs(gs.vs[gs.vs[gs.vhead].next].deqID.tid)) = Claimed(gs.vs[gs.vs[gs.vhead].next].deqID.tid, gs.vs[gs.vs[gs.vhead].next].val), gs.orl.last = gs.vhead ∧ (gs.qrl ≠ [] → unmarkedp(gs.qrl.tail, gs.vs)) ∨ gs.orl.butlast ≠ [] ∧ gs.orl.butlast.last = gs.vhead ∧ gs.phead ≠ gs.orl.last ∧ unmarkedp(gs.qrl, gs.vs), gs.vtail = (gs.orl + gs.qrl).last ∨ gs.qrl ≠ [] ∧ gs.vtail = (gs.orl + gs.qrl.butlast).last ∧ gs.vs[gs.qrl.last].deqID = None ∧ gs.vs[(gs.orl + gs.qrl).last].next = null ⊦ ( ( lstepf(gs, ls, D17, a).success → lstepf(gs, ls, D17, a).optval = gstepf(gs, ls, D17, a).vrvHp[lstepf(gs, ls, D17, a).rvref] ∧ lstepf(gs, ls, D17, a).optval = gstepf(gs, ls, D17, a).prvHp[lstepf(gs, ls, D17, a).rvref]) ∧ gstepf(gs, ls, D17, a).rvowns(gstepf(gs, ls, D17, a).vretRefs(lstepf(gs, ls, D17, a).tid)) = (lstepf(gs, ls, D17, a).optval = Empty ∨ ¬ lstepf(gs, ls, D17, a).success ⊃ Pending(lstepf(gs, ls, D17, a).tid) ;Claimed(lstepf(gs, ls, D17, a).tid, lstepf(gs, ls, D17, a).optval.val) )) ∧ ( listp (gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl, gstepf(gs, ls, D17, a).vs, gstepf(gs, ls, D17, a).ps, gstepf(gs, ls, D17, a).owns) ∧ ¬ dups(gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl) ∧ markedp(gstepf(gs, ls, D17, a).orl, gstepf(gs, ls, D17, a).ps) ∧ markedp(gstepf(gs, ls, D17, a).orl, gstepf(gs, ls, D17, a).vs) ∧ unmarkedp(gstepf(gs, ls, D17, a).qrl, gstepf(gs, ls, D17, a).ps) ∧ gstepf(gs, ls, D17, a).orl ≠ [] ∧ gstepf(gs, ls, D17, a).phead ∈ gstepf(gs, ls, D17, a).orl ∧ rvownerok(gstepf(gs, ls, D17, a).vretRefs, gstepf(gs, ls, D17, a).vrvHp, gstepf(gs, ls, D17, a).rvowns) ∧ allocrv(gstepf(gs, ls, D17, a).vretRefs, gstepf(gs, ls, D17, a).vrvHp) ∧ nonullRetRefs (gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl, gstepf(gs, ls, D17, a).vs, gstepf(gs, ls, D17, a).vretRefs, gstepf(gs, ls, D17, a).pretRefs) ∧ rvownerok(gstepf(gs, ls, D17, a).pretRefs, gstepf(gs, ls, D17, a).prvHp, gstepf(gs, ls, D17, a).rvowns) ∧ allocrv(gstepf(gs, ls, D17, a).pretRefs, gstepf(gs, ls, D17, a).prvHp) ∧ dom gstepf(gs, ls, D17, a).vrvHp = dom gstepf(gs, ls, D17, a).prvHp ∧ ( gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vhead].next ≠ null ∧ gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vhead].next].deqID ≠ None → gstepf(gs, ls, D17, a).rvowns (gstepf(gs, ls, D17, a).vretRefs(gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vhead].next].deqID.tid)) = Claimed (gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vhead].next].deqID.tid, gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).vhead].next].val)) ∧ ( gstepf(gs, ls, D17, a).orl.last = gstepf(gs, ls, D17, a).vhead ∧ (gstepf(gs, ls, D17, a).qrl ≠ [] → unmarkedp(gstepf(gs, ls, D17, a).qrl.tail, gstepf(gs, ls, D17, a).vs)) ∨ gstepf(gs, ls, D17, a).orl.butlast ≠ [] ∧ gstepf(gs, ls, D17, a).orl.butlast.last = gstepf(gs, ls, D17, a).vhead ∧ gstepf(gs, ls, D17, a).phead ≠ gstepf(gs, ls, D17, a).orl.last ∧ unmarkedp(gstepf(gs, ls, D17, a).qrl, gstepf(gs, ls, D17, a).vs)) ∧ ( gstepf(gs, ls, D17, a).vtail = (gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl).last ∨ gstepf(gs, ls, D17, a).qrl ≠ [] ∧ gstepf(gs, ls, D17, a).vtail = (gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl.butlast).last ∧ gstepf(gs, ls, D17, a).vs[gstepf(gs, ls, D17, a).qrl.last].deqID = None ∧ gstepf(gs, ls, D17, a).vs[(gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl).last].next = null)) ∧ ( gstepf(gs, ls, D17, a).vretRefs(lstepf(gs, ls, D17, a).tid) = lstepf(gs, ls, D17, a).rvref ∧ gstepf(gs, ls, D17, a).pretRefs(lstepf(gs, ls, D17, a).tid) = lstepf(gs, ls, D17, a).rvref ∧ lstepf(gs, ls, D17, a).rvref ∈ gstepf(gs, ls, D17, a).vrvHp ∧ lstepf(gs, ls, D17, a).rvref ≠ null) ∧ nextnottid(lstepf(gs, ls, D17, a).tid, gstepf(gs, ls, D17, a).vhead, gstepf(gs, ls, D17, a).vs) ∧ noid(lstepf(gs, ls, D17, a).tid, gstepf(gs, ls, D17, a).orl + gstepf(gs, ls, D17, a).qrl, gstepf(gs, ls, D17, a).vhead, gstepf(gs, ls, D17, a).vs) ∧ noowns(lstepf(gs, ls, D17, a).tid, gstepf(gs, ls, D17, a).owns)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] a: ⊦ ¬ dups(x + y) → ¬ dups(x) ∧ ¬ dups(y); (forward) from specification list-dup[reflist] list-elem-in-app11: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ vs; (forward) from specification DMSQ list-elem-in-app12: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ ps; (forward) from specification DMSQ ⊦ gstepf(gs, ls, D17, a) = (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs); (s) ⊦ lstepf(gs, ls, D17, a) = ls; (s) ⊦ y ≠ [] → (x + y).last = y.last; (s) ⊦ pre(gs, ls, D17, a) ↔ a = τ; (s) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) ⊦ pcstepf(gs, ls, D17, a) = D6; (s)

Proof step 3 from proof step-D17-D6 (previous step) (back to tree)

ls.nxt = gs.ps[ls.lst].next, ls.nxt = gs.vs[ls.lst].next, gs.pretRefs(ls.tid) = ls.rvref, gs.rvowns(ls.rvref) = Pending(ls.tid), gs.vretRefs(ls.tid) = ls.rvref, dom gs.vrvHp = dom gs.prvHp, ls.nxt ≠ null, gs.orl ≠ [], ls.rvref ≠ null, allocrv(gs.vretRefs, gs.vrvHp), allocrv(gs.pretRefs, gs.prvHp), listp(gs.orl + gs.qrl, gs.vs, gs.ps, gs.owns), markedp(gs.orl, gs.ps), markedp(gs.orl, gs.vs), nextnottid(ls.tid, gs.vhead, gs.vs), noid(ls.tid, gs.orl + gs.qrl, gs.vhead, gs.vs), nonullRetRefs(gs.orl + gs.qrl, gs.vs, gs.vretRefs, gs.pretRefs), noowns(ls.tid, gs.owns), rvownerok(gs.vretRefs, gs.vrvHp, gs.rvowns), rvownerok(gs.pretRefs, gs.prvHp, gs.rvowns), unmarkedp(gs.qrl, gs.ps), gs.phead ∈ gs.ps, gs.phead ∈ gs.vs, gs.phead ∈ gs.orl, ls.rvref ∈ gs.vrvHp, ¬ ls.success, ¬ dups(gs.qrl), ¬ dups(gs.orl), ¬ dups(gs.orl + gs.qrl), gs.vs[gs.vhead].next ≠ null ∧ gs.vs[gs.vs[gs.vhead].next].deqID ≠ None → gs.rvowns(gs.vretRefs(gs.vs[gs.vs[gs.vhead].next].deqID.tid)) = Claimed(gs.vs[gs.vs[gs.vhead].next].deqID.tid, gs.vs[gs.vs[gs.vhead].next].val), gs.vtail = (gs.orl + gs.qrl).last ∨ gs.qrl ≠ [] ∧ gs.vtail = (gs.orl + gs.qrl.butlast).last ∧ gs.vs[gs.qrl.last].deqID = None ∧ gs.vs[gs.qrl.last].next = null, ls.lst ∈ gs.orl ∨ ls.lst ∈ gs.qrl, gs.orl.last = gs.vhead ∧ (gs.qrl ≠ [] → unmarkedp(gs.qrl.tail, gs.vs)) ∨ gs.orl.butlast ≠ [] ∧ gs.orl.butlast.last = gs.vhead ∧ gs.phead ≠ gs.orl.last ∧ unmarkedp(gs.qrl, gs.vs) ⊦ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).rvowns((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs(ls.tid)) = Pending(ls.tid) ∧ listp ((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).ps, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).owns) ∧ ¬ dups((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl) ∧ markedp((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).ps) ∧ markedp((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs) ∧ unmarkedp((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).ps) ∧ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl ≠ [] ∧ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).phead ∈ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl ∧ rvownerok ((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vrvHp, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).rvowns) ∧ allocrv((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vrvHp) ∧ nonullRetRefs ((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).pretRefs) ∧ rvownerok ((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).pretRefs, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).prvHp, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).rvowns) ∧ allocrv((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).pretRefs, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).prvHp) ∧ dom (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vrvHp = dom (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).prvHp ∧ ( (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead].next ≠ null ∧ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs [(gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead].next ] .deqID ≠ None → (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).rvowns ((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs ((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs [(gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead].next ] .deqID .tid)) = Claimed ((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs [(gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead].next ] .deqID .tid, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs [(gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead].next ] .val)) ∧ ( (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl.last = (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead ∧ ( (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl ≠ [] → unmarkedp((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl.tail, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs)) ∨ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl.butlast ≠ [] ∧ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl.butlast.last = (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead ∧ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).phead ≠ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl.last ∧ unmarkedp((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs)) ∧ ( (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vtail = ((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl).last ∨ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl ≠ [] ∧ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vtail = ((gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl.butlast).last ∧ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl.last].deqID = None ∧ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl.last].next = null) ∧ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs(ls.tid) = ls.rvref ∧ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).pretRefs(ls.tid) = ls.rvref ∧ ls.rvref ∈ (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vrvHp ∧ nextnottid(ls.tid, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs) ∧ noid (ls.tid, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs) ∧ noowns(ls.tid, (gs.vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).owns)

Heuristic elimination applied rule apply elim lemma

And obtained the following new goals

Rule argument

spec: DMSQ, name:elim-mkgs, seq:⊦ ( ( ( ( ( ( ( ( ( ( (ps = gs.ps ∧ vs = gs.vs) ∧ phead = gs.phead) ∧ vhead = gs.vhead) ∧ vtail = gs.vtail) ∧ vretRefs = gs.vretRefs) ∧ pretRefs = gs.pretRefs) ∧ vrvHp = gs.vrvHp) ∧ prvHp = gs.prvHp) ∧ qrl = gs.qrl) ∧ orl = gs.orl) ∧ owns = gs.owns) ∧ rvowns = gs.rvowns ↔ gs = mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), subst:[qrl, ps, phead, vrvHp, vretRefs, vhead, vtail, gs, owns, rvowns, orl, prvHp, pretRefs, vs] → [qrl, ps, phead, vrvHp, vretRefs, vhead, vtail, gs, owns, rvowns, orl, prvHp, pretRefs, vs]

Additional information

Used simplifier rules: ⊦ ( ( ( ( ( ( ( ( ( ((ps = gs.ps ∧ vs = gs.vs) ∧ phead = gs.phead) ∧ vhead = gs.vhead) ∧ vtail = gs.vtail) ∧ vretRefs = gs.vretRefs) ∧ pretRefs = gs.pretRefs) ∧ vrvHp = gs.vrvHp) ∧ prvHp = gs.prvHp) ∧ qrl = gs.qrl) ∧ orl = gs.orl) ∧ owns = gs.owns) ∧ rvowns = gs.rvowns ↔ gs = mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns); (elim) Used terms: qrl, ps, phead, vrvHp, vretRefs, vhead, vtail, gs, owns, rvowns, orl, prvHp, pretRefs, vs

Proof step 4 from proof step-D17-D6 (previous step) (back to tree)

ls.nxt = vs[ls.lst].next, ls.nxt = ps[ls.lst].next, dom vrvHp = dom prvHp, gs = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), pretRefs(ls.tid) = ls.rvref, rvowns(ls.rvref) = Pending(ls.tid), vretRefs(ls.tid) = ls.rvref, ls.nxt ≠ null, ls.rvref ≠ null, orl ≠ [], allocrv(pretRefs, prvHp), allocrv(vretRefs, vrvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, vs), markedp(orl, ps), nextnottid(ls.tid, vhead, vs), noid(ls.tid, orl + qrl, vhead, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), noowns(ls.tid, owns), rvownerok(pretRefs, prvHp, rvowns), rvownerok(vretRefs, vrvHp, rvowns), unmarkedp(qrl, ps), ls.rvref ∈ vrvHp, phead ∈ orl, phead ∈ vs, phead ∈ ps, ¬ ls.success, ¬ dups(qrl), ¬ dups(orl), ¬ dups(orl + qrl), vs[vhead].next ≠ null ∧ vs[vs[vhead].next].deqID ≠ None → rvowns(vretRefs(vs[vs[vhead].next].deqID.tid)) = Claimed(vs[vs[vhead].next].deqID.tid, vs[vs[vhead].next].val), orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs), ls.lst ∈ orl ∨ ls.lst ∈ qrl, vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null ⊦ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).rvowns((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs(ls.tid)) = Pending(ls.tid) ∧ listp ((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).ps, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).owns) ∧ ¬ dups((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl) ∧ markedp((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).ps) ∧ markedp((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs) ∧ unmarkedp((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).ps) ∧ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl ≠ [] ∧ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).phead ∈ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl ∧ rvownerok ((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vrvHp, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).rvowns) ∧ allocrv((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vrvHp) ∧ nonullRetRefs ((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).pretRefs) ∧ rvownerok ((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).pretRefs, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).prvHp, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).rvowns) ∧ allocrv((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).pretRefs, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).prvHp) ∧ dom (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vrvHp = dom (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).prvHp ∧ ( (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead].next ≠ null ∧ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead].next] .deqID ≠ None → (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).rvowns ((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs ((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead].next] .deqID .tid)) = Claimed ((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead].next] .deqID .tid, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead].next] .val)) ∧ ( (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl.last = (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead ∧ ( (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl ≠ [] → unmarkedp((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl.tail, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs)) ∨ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl.butlast ≠ [] ∧ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl.butlast.last = (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead ∧ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).phead ≠ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl.last ∧ unmarkedp((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs)) ∧ ( (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vtail = ((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl).last ∨ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl ≠ [] ∧ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vtail = ((vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl.butlast).last ∧ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl.last].deqID = None ∧ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs[(vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl.last].next = null) ∧ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vretRefs(ls.tid) = ls.rvref ∧ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).pretRefs(ls.tid) = ls.rvref ∧ ls.rvref ∈ (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vrvHp ∧ nextnottid(ls.tid, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs) ∧ noid (ls.tid, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).orl + (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).qrl, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vhead, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).vs) ∧ noowns(ls.tid, (vtail = ls.lst ⊃ gs.vtail:= ls.nxt;gs).owns)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] a: ⊦ ¬ dups(x + y) → ¬ dups(x) ∧ ¬ dups(y); (forward) from specification list-dup[reflist] list-elem-in-app11: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ vs; (forward) from specification DMSQ list-elem-in-app12: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ ps; (forward) from specification DMSQ ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .vtail:= phead4 = mkgs (ps, ps0, phead, phead0, phead4, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns); (s)

Proof step 5 from proof step-D17-D6 (previous step) (back to tree)

ls.nxt = ps[ls.lst].next, ls.nxt = vs[ls.lst].next, dom vrvHp = dom prvHp, pretRefs(ls.tid) = ls.rvref, rvowns(ls.rvref) = Pending(ls.tid), vretRefs(ls.tid) = ls.rvref, ls.nxt ≠ null, ls.rvref ≠ null, orl ≠ [], allocrv(vretRefs, vrvHp), allocrv(pretRefs, prvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, ps), markedp(orl, vs), nextnottid(ls.tid, vhead, vs), noid(ls.tid, orl + qrl, vhead, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), noowns(ls.tid, owns), rvownerok(vretRefs, vrvHp, rvowns), rvownerok(pretRefs, prvHp, rvowns), unmarkedp(qrl, ps), phead ∈ orl, ls.rvref ∈ vrvHp, phead ∈ vs, phead ∈ ps, ¬ ls.success, ¬ dups(orl + qrl), ¬ dups(orl), ¬ dups(qrl), vs[vhead].next ≠ null ∧ vs[vs[vhead].next].deqID ≠ None → rvowns(vretRefs(vs[vs[vhead].next].deqID.tid)) = Claimed(vs[vs[vhead].next].deqID.tid, vs[vs[vhead].next].val), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null, ls.lst ∈ orl ∨ ls.lst ∈ qrl, orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs) ⊦ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs (ls.tid)) = Pending(ls.tid) ∧ listp ( (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .ps, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .owns) ∧ ¬ dups ( (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl) ∧ markedp ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .ps) ∧ markedp ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs) ∧ unmarkedp ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .ps) ∧ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl ≠ [] ∧ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .phead ∈ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl ∧ rvownerok ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns) ∧ allocrv ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp) ∧ nonullRetRefs ( (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs) ∧ rvownerok ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .prvHp, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns) ∧ allocrv ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .prvHp) ∧ dom (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp = dom (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .prvHp ∧ ( (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ≠ null ∧ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .deqID ≠ None → (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .deqID .tid)) = Claimed ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .deqID .tid, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .val)) ∧ ( (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .last = (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ∧ ( (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl ≠ [] → unmarkedp ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .tail, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs)) ∨ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .butlast ≠ [] ∧ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .butlast .last = (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ∧ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .phead ≠ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .last ∧ unmarkedp ((vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs)) ∧ ( (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vtail = ( (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl ).last ∨ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl ≠ [] ∧ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vtail = ( (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .butlast ).last ∧ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .last ] .deqID = None ∧ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .last ] .next = null) ∧ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs (ls.tid) = ls.rvref ∧ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs (ls.tid) = ls.rvref ∧ ls.rvref ∈ (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp ∧ nextnottid (ls.tid, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs) ∧ noid (ls.tid, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs) ∧ noowns (ls.tid, (vtail = ls.lst ⊃ mkgs(ps, vs, phead, vhead, ls.nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .owns)

Heuristic elimination applied rule apply elim lemma

And obtained the following new goals

Rule argument

spec: DMSQ, name:elim-mkls, seq:⊦ ( ( ( ( ( ( ( ( ( ( (tid = ls.tid ∧ value = ls.value) ∧ optval = ls.optval) ∧ node = ls.node) ∧ nd = ls.nd) ∧ (success ↔ ls.success)) ∧ lst = ls.lst) ∧ nxt = ls.nxt) ∧ rvref = ls.rvref) ∧ optval0 = ls.optval0) ∧ first = ls.first) ∧ othertid = ls.othertid) ∧ addr = ls.addr ↔ ls = mkls (tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), subst:[value, nxt, optval0, node, nd, ls, addr, tid, lst, first, rvref, othertid, success, optval] → [value, nxt, optval0, node, nd, ls, addr, tid, lst, first, rvref, othertid, success, optval]

Additional information

Used simplifier rules: ⊦ ( ( ( ( ( ( ( ( ( ( (tid = ls.tid ∧ value = ls.value) ∧ optval = ls.optval) ∧ node = ls.node) ∧ nd = ls.nd) ∧ (success ↔ ls.success)) ∧ lst = ls.lst) ∧ nxt = ls.nxt) ∧ rvref = ls.rvref) ∧ optval0 = ls.optval0) ∧ first = ls.first) ∧ othertid = ls.othertid) ∧ addr = ls.addr ↔ ls = mkls (tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr); (elim) Used terms: value, nxt, optval, node, nd, ls, addr, tid, lst, first, rvref, othertid, success, optval

Proof step 6 from proof step-D17-D6 (previous step) (back to tree)

dom vrvHp = dom prvHp, ls = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), nxt = vs[lst].next, nxt = ps[lst].next, pretRefs(tid) = rvref, rvowns(rvref) = Pending(tid), ¬ success, vretRefs(tid) = rvref, nxt ≠ null, orl ≠ [], rvref ≠ null, allocrv(pretRefs, prvHp), allocrv(vretRefs, vrvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, vs), markedp(orl, ps), nextnottid(tid, vhead, vs), noid(tid, orl + qrl, vhead, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), noowns(tid, owns), rvownerok(pretRefs, prvHp, rvowns), rvownerok(vretRefs, vrvHp, rvowns), unmarkedp(qrl, ps), phead ∈ ps, phead ∈ vs, rvref ∈ vrvHp, phead ∈ orl, ¬ dups(orl + qrl), ¬ dups(orl), ¬ dups(qrl), vs[vhead].next ≠ null ∧ vs[vs[vhead].next].deqID ≠ None → rvowns(vretRefs(vs[vs[vhead].next].deqID.tid)) = Claimed(vs[vs[vhead].next].deqID.tid, vs[vs[vhead].next].val), orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs), lst ∈ orl ∨ lst ∈ qrl, vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null ⊦ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs (tid)) = Pending(tid) ∧ listp ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .ps, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .owns) ∧ ¬ dups ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl) ∧ markedp ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .ps) ∧ markedp ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs) ∧ unmarkedp ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .ps) ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl ≠ [] ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .phead ∈ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl ∧ rvownerok ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns) ∧ allocrv ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp) ∧ nonullRetRefs ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs) ∧ rvownerok ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .prvHp, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns) ∧ allocrv ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .prvHp) ∧ dom (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp = dom (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .prvHp ∧ ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ≠ null ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .deqID ≠ None → (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .deqID .tid)) = Claimed ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .deqID .tid, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .val)) ∧ ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .last = (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ∧ ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl ≠ [] → unmarkedp ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .tail, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs)) ∨ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .butlast ≠ [] ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .butlast .last = (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .phead ≠ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .last ∧ unmarkedp ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs)) ∧ ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vtail = ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl ).last ∨ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl ≠ [] ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vtail = ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .butlast ).last ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .last ] .deqID = None ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .last ] .next = null) ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs (tid) = rvref ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs (tid) = rvref ∧ rvref ∈ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp ∧ nextnottid (tid, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs) ∧ noid (tid, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs) ∧ noowns (tid, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, nxt, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .owns)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Proof step 7 from proof step-D17-D6 (previous step) (back to tree)

ps[lst].next = vs[lst].next, dom vrvHp = dom prvHp, pretRefs(tid) = vretRefs(tid), rvowns(vretRefs(tid)) = Pending(tid), vs[lst].next ≠ null, orl ≠ [], vretRefs(tid) ≠ null, allocrv(vretRefs, vrvHp), allocrv(pretRefs, prvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, ps), markedp(orl, vs), nextnottid(tid, vhead, vs), noid(tid, orl + qrl, vhead, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), noowns(tid, owns), rvownerok(vretRefs, vrvHp, rvowns), rvownerok(pretRefs, prvHp, rvowns), unmarkedp(qrl, ps), phead ∈ orl, vretRefs(tid) ∈ vrvHp, phead ∈ vs, phead ∈ ps, ¬ dups(orl + qrl), ¬ dups(orl), ¬ dups(qrl), vs[vhead].next ≠ null ∧ vs[vs[vhead].next].deqID ≠ None → rvowns(vretRefs(vs[vs[vhead].next].deqID.tid)) = Claimed(vs[vs[vhead].next].deqID.tid, vs[vs[vhead].next].val), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null, lst ∈ orl ∨ lst ∈ qrl, orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs) ⊦ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs (tid)) = Pending(tid) ∧ listp ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .ps, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .owns) ∧ ¬ dups ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl) ∧ markedp ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .ps) ∧ markedp ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs) ∧ unmarkedp ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .ps) ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl ≠ [] ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .phead ∈ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl ∧ rvownerok ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns) ∧ allocrv ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp) ∧ nonullRetRefs ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs) ∧ rvownerok ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .prvHp, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns) ∧ allocrv ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .prvHp) ∧ dom (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp = dom (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .prvHp ∧ ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ≠ null ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .deqID ≠ None → (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .rvowns ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .deqID .tid)) = Claimed ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .deqID .tid, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ] .next ] .val)) ∧ ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .last = (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ∧ ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl ≠ [] → unmarkedp ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .tail, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs)) ∨ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .butlast ≠ [] ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .butlast .last = (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .phead ≠ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl .last ∧ unmarkedp ((vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs)) ∧ ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vtail = ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl ).last ∨ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl ≠ [] ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vtail = ( (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .butlast ).last ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .last ] .deqID = None ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs [(vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl .last ] .next = null) ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vretRefs (tid) = vretRefs(tid) ∧ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .pretRefs (tid) = vretRefs(tid) ∧ vretRefs(tid) ∈ (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vrvHp ∧ nextnottid (tid, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs) ∧ noid (tid, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .orl + (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .qrl, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vhead, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .vs) ∧ noowns (tid, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) .owns)

Heuristic elimination applied rule apply elim lemma

And obtained the following new goals

Rule argument

spec: DMSQ, name:elim-mkgs, seq:⊦ ( ( ( ( ( ( ( ( ( ( (ps = gs.ps ∧ vs = gs.vs) ∧ phead = gs.phead) ∧ vhead = gs.vhead) ∧ vtail = gs.vtail) ∧ vretRefs = gs.vretRefs) ∧ pretRefs = gs.pretRefs) ∧ vrvHp = gs.vrvHp) ∧ prvHp = gs.prvHp) ∧ qrl = gs.qrl) ∧ orl = gs.orl) ∧ owns = gs.owns) ∧ rvowns = gs.rvowns ↔ gs = mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), subst:[qrl, ps, phead, vrvHp, vretRefs, vhead, vtail, gs, owns, rvowns, orl, prvHp, pretRefs, vs] → [qrl0, ps0, phead0, vrvHp0, vretRefs0, vhead0, vtail0, (vtail = lst ⊃ mkgs (ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ), owns0, rvowns0, orl0, prvHp0, pretRefs0, vs0]

Additional information

Used simplifier rules: ⊦ ( ( ( ( ( ( ( ( ( ((ps = gs.ps ∧ vs = gs.vs) ∧ phead = gs.phead) ∧ vhead = gs.vhead) ∧ vtail = gs.vtail) ∧ vretRefs = gs.vretRefs) ∧ pretRefs = gs.pretRefs) ∧ vrvHp = gs.vrvHp) ∧ prvHp = gs.prvHp) ∧ qrl = gs.qrl) ∧ orl = gs.orl) ∧ owns = gs.owns) ∧ rvowns = gs.rvowns ↔ gs = mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns); (elim) Used terms: qrl0, ps0, phead0, vrvHp0, vretRefs0, vhead0, vtail0, (vtail = lst ⊃ mkgs (ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ), owns0, rvowns0, orl0, prvHp0, pretRefs0, vs0

Proof step 8 from proof step-D17-D6 (previous step) (back to tree)

ps[lst].next = vs[lst].next, (vtail = lst ⊃ mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ;mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) ) = mkgs(ps0, vs0, phead0, vhead0, vtail0, vretRefs0, pretRefs0, vrvHp0, prvHp0, qrl0, orl0, owns0, rvowns0), dom vrvHp = dom prvHp, pretRefs(tid) = vretRefs(tid), rvowns(vretRefs(tid)) = Pending(tid), vs[lst].next ≠ null, orl ≠ [], vretRefs(tid) ≠ null, allocrv(pretRefs, prvHp), allocrv(vretRefs, vrvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, vs), markedp(orl, ps), nextnottid(tid, vhead, vs), noid(tid, orl + qrl, vhead, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), noowns(tid, owns), rvownerok(pretRefs, prvHp, rvowns), rvownerok(vretRefs, vrvHp, rvowns), unmarkedp(qrl, ps), phead ∈ ps, phead ∈ vs, vretRefs(tid) ∈ vrvHp, phead ∈ orl, ¬ dups(orl + qrl), ¬ dups(orl), ¬ dups(qrl), vs[vhead].next ≠ null ∧ vs[vs[vhead].next].deqID ≠ None → rvowns(vretRefs(vs[vs[vhead].next].deqID.tid)) = Claimed(vs[vs[vhead].next].deqID.tid, vs[vs[vhead].next].val), orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs), lst ∈ orl ∨ lst ∈ qrl, vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null ⊦ rvowns0(vretRefs0(tid)) = Pending(tid) ∧ listp(orl0 + qrl0, vs0, ps0, owns0) ∧ ¬ dups(orl0 + qrl0) ∧ markedp(orl0, ps0) ∧ markedp(orl0, vs0) ∧ unmarkedp(qrl0, ps0) ∧ orl0 ≠ [] ∧ phead0 ∈ orl0 ∧ rvownerok(vretRefs0, vrvHp0, rvowns0) ∧ allocrv(vretRefs0, vrvHp0) ∧ nonullRetRefs(orl0 + qrl0, vs0, vretRefs0, pretRefs0) ∧ rvownerok(pretRefs0, prvHp0, rvowns0) ∧ allocrv(pretRefs0, prvHp0) ∧ dom vrvHp0 = dom prvHp0 ∧ ( vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val)) ∧ ( orl0.last = vhead0 ∧ (qrl0 ≠ [] → unmarkedp(qrl0.tail, vs0)) ∨ orl0.butlast ≠ [] ∧ orl0.butlast.last = vhead0 ∧ phead0 ≠ orl0.last ∧ unmarkedp(qrl0, vs0)) ∧ (vtail0 = (orl0 + qrl0).last ∨ qrl0 ≠ [] ∧ vtail0 = (orl0 + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null) ∧ vretRefs0(tid) = vretRefs(tid) ∧ pretRefs0(tid) = vretRefs(tid) ∧ vretRefs(tid) ∈ vrvHp0 ∧ nextnottid(tid, vhead0, vs0) ∧ noid(tid, orl0 + qrl0, vhead0, vs0) ∧ noowns(tid, owns0)

User applied rule case distinction

And obtained the following new goals

Rule argument

pos: left 2

Additional information

Used simplifier rules: ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) = mkgs (ps1, ps2, phead2, phead3, phead4, vretRefs1, vretRefs2, vrvHp1, vrvHp2, qrl1, qrl2, owns0, rvowns0) ↔ ps = ps1 ∧ ps0 = ps2 ∧ phead = phead2 ∧ phead0 = phead3 ∧ phead1 = phead4 ∧ vretRefs = vretRefs1 ∧ vretRefs0 = vretRefs2 ∧ vrvHp = vrvHp1 ∧ vrvHp0 = vrvHp2 ∧ qrl = qrl1 ∧ qrl0 = qrl2 ∧ owns = owns0 ∧ rvowns = rvowns0; (ws)

Proof step 9 from proof step-D17-D6 (previous step) (back to tree)

ps[lst].next = vs[lst].next, dom vrvHp = dom prvHp, mkgs(ps, vs, phead, vhead, vs[lst].next, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns) = mkgs(ps0, vs0, phead0, vhead0, vtail0, vretRefs0, pretRefs0, vrvHp0, prvHp0, qrl0, orl0, owns0, rvowns0), pretRefs(tid) = vretRefs(tid), rvowns(vretRefs(tid)) = Pending(tid), vtail = lst, vs[lst].next ≠ null, orl ≠ [], vretRefs(tid) ≠ null, allocrv(vretRefs, vrvHp), allocrv(pretRefs, prvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, ps), markedp(orl, vs), nextnottid(tid, vhead, vs), noid(tid, orl + qrl, vhead, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), noowns(tid, owns), rvownerok(vretRefs, vrvHp, rvowns), rvownerok(pretRefs, prvHp, rvowns), unmarkedp(qrl, ps), phead ∈ orl, vretRefs(tid) ∈ vrvHp, phead ∈ vs, phead ∈ ps, ¬ dups(orl + qrl), ¬ dups(orl), ¬ dups(qrl), vs[vhead].next ≠ null ∧ vs[vs[vhead].next].deqID ≠ None → rvowns(vretRefs(vs[vs[vhead].next].deqID.tid)) = Claimed(vs[vs[vhead].next].deqID.tid, vs[vs[vhead].next].val), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null, lst ∈ orl ∨ lst ∈ qrl, orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs) ⊦ rvowns0(vretRefs0(tid)) = Pending(tid) ∧ listp(orl0 + qrl0, vs0, ps0, owns0) ∧ ¬ dups(orl0 + qrl0) ∧ markedp(orl0, ps0) ∧ markedp(orl0, vs0) ∧ unmarkedp(qrl0, ps0) ∧ orl0 ≠ [] ∧ phead0 ∈ orl0 ∧ rvownerok(vretRefs0, vrvHp0, rvowns0) ∧ allocrv(vretRefs0, vrvHp0) ∧ nonullRetRefs(orl0 + qrl0, vs0, vretRefs0, pretRefs0) ∧ rvownerok(pretRefs0, prvHp0, rvowns0) ∧ allocrv(pretRefs0, prvHp0) ∧ dom vrvHp0 = dom prvHp0 ∧ ( vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val)) ∧ ( orl0.last = vhead0 ∧ (qrl0 ≠ [] → unmarkedp(qrl0.tail, vs0)) ∨ orl0.butlast ≠ [] ∧ orl0.butlast.last = vhead0 ∧ phead0 ≠ orl0.last ∧ unmarkedp(qrl0, vs0)) ∧ (vtail0 = (orl0 + qrl0).last ∨ qrl0 ≠ [] ∧ vtail0 = (orl0 + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null) ∧ vretRefs0(tid) = vretRefs(tid) ∧ pretRefs0(tid) = vretRefs(tid) ∧ vretRefs(tid) ∈ vrvHp0 ∧ nextnottid(tid, vhead0, vs0) ∧ noid(tid, orl0 + qrl0, vhead0, vs0) ∧ noowns(tid, owns0)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] a: ⊦ ¬ dups(x + y) → ¬ dups(x) ∧ ¬ dups(y); (forward) from specification list-dup[reflist] list-elem-in-app11: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ vs; (forward) from specification DMSQ list-elem-in-app12: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ ps; (forward) from specification DMSQ ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) = mkgs (ps1, ps2, phead2, phead3, phead4, vretRefs1, vretRefs2, vrvHp1, vrvHp2, qrl1, qrl2, owns0, rvowns0) ↔ ps = ps1 ∧ ps0 = ps2 ∧ phead = phead2 ∧ phead0 = phead3 ∧ phead1 = phead4 ∧ vretRefs = vretRefs1 ∧ vretRefs0 = vretRefs2 ∧ vrvHp = vrvHp1 ∧ vrvHp0 = vrvHp2 ∧ qrl = qrl1 ∧ qrl0 = qrl2 ∧ owns = owns0 ∧ rvowns = rvowns0; (ws)

Proof step 10 from proof step-D17-D6 (previous step) (back to tree)

ps0[lst].next = vs0[lst].next, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[lst].next ≠ null, vs0[lst].next ≠ (orl0 + qrl0).last, orl0 ≠ [], vretRefs0(tid) ≠ null, allocrv(vretRefs0, vrvHp0), allocrv(pretRefs0, prvHp0), listp(orl0 + qrl0, vs0, ps0, owns0), markedp(orl0, ps0), markedp(orl0, vs0), nextnottid(tid, vhead0, vs0), noid(tid, orl0 + qrl0, vhead0, vs0), nonullRetRefs(orl0 + qrl0, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(vretRefs0, vrvHp0, rvowns0), rvownerok(pretRefs0, prvHp0, rvowns0), unmarkedp(qrl0, ps0), phead0 ∈ orl0, vretRefs0(tid) ∈ vrvHp0, phead0 ∈ vs0, phead0 ∈ ps0, ¬ dups(orl0 + qrl0), ¬ dups(orl0), ¬ dups(qrl0), vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), lst = (orl0 + qrl0).last ∨ qrl0 ≠ [] ∧ lst = (orl0 + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null, lst ∈ orl0 ∨ lst ∈ qrl0, orl0.last = vhead0 ∧ (qrl0 ≠ [] → unmarkedp(qrl0.tail, vs0)) ∨ orl0.butlast ≠ [] ∧ orl0.butlast.last = vhead0 ∧ phead0 ≠ orl0.last ∧ unmarkedp(qrl0, vs0) ⊦ qrl0 ≠ [] ∧ vs0[lst].next = (orl0 + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null

User applied rule apply lemma

And obtained the following new goals

Rule argument

spec: DMSQ, name:listp-in-postfix, seq:⊦ listp(rl, vs, ps, owns) ∧ r ∈ rl → (∃ rl1, rl2. rl = rl1 + r ' + rl2 ∧ listp(r ' + rl2, vs, ps, owns)), subst:[ps, rl, owns, r, vs] → [ps0, orl0 + qrl0, owns0, lst, vs0]

Additional information

Used terms: ps0, orl0 + qrl0, owns0, lst, vs0

Proof step 11 from proof step-D17-D6 (previous step) (back to tree)

⊦ listp(rl, vs, ps, owns) ∧ r ∈ rl → (∃ rl1, rl2. rl = rl1 + r ' + rl2 ∧ listp(r ' + rl2, vs, ps, owns))

A spec-lemma

Proof step 12 from proof step-D17-D6 (previous step) (back to tree)

ps0[lst].next = vs0[lst].next, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[lst].next ≠ null, vs0[lst].next ≠ (orl0 + qrl0).last, orl0 ≠ [], vretRefs0(tid) ≠ null, allocrv(pretRefs0, prvHp0), allocrv(vretRefs0, vrvHp0), listp(orl0 + qrl0, vs0, ps0, owns0), markedp(orl0, vs0), markedp(orl0, ps0), nextnottid(tid, vhead0, vs0), noid(tid, orl0 + qrl0, vhead0, vs0), nonullRetRefs(orl0 + qrl0, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(pretRefs0, prvHp0, rvowns0), rvownerok(vretRefs0, vrvHp0, rvowns0), unmarkedp(qrl0, ps0), phead0 ∈ ps0, phead0 ∈ vs0, vretRefs0(tid) ∈ vrvHp0, phead0 ∈ orl0, ¬ dups(orl0 + qrl0), ¬ dups(orl0), ¬ dups(qrl0), vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), listp(orl0 + qrl0, vs0, ps0, owns0) ∧ lst ∈ orl0 + qrl0 → (∃ rl1, rl2. orl0 + qrl0 = rl1 + lst ' + rl2 ∧ listp(lst ' + rl2, vs0, ps0, owns0)), orl0.last = vhead0 ∧ (qrl0 ≠ [] → unmarkedp(qrl0.tail, vs0)) ∨ orl0.butlast ≠ [] ∧ orl0.butlast.last = vhead0 ∧ phead0 ≠ orl0.last ∧ unmarkedp(qrl0, vs0), lst ∈ orl0 ∨ lst ∈ qrl0, lst = (orl0 + qrl0).last ∨ qrl0 ≠ [] ∧ lst = (orl0 + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null ⊦ qrl0 ≠ [] ∧ vs0[lst].next = (orl0 + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s)

Proof step 13 from proof step-D17-D6 (previous step) (back to tree)

orl0 + qrl0 = rl1 + lst ' + rl2, ps0[lst].next = vs0[lst].next, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[lst].next ≠ null, vs0[lst].next ≠ (orl0 + qrl0).last, orl0 ≠ [], vretRefs0(tid) ≠ null, allocrv(vretRefs0, vrvHp0), allocrv(pretRefs0, prvHp0), listp(orl0 + qrl0, vs0, ps0, owns0), listp(lst ' + rl2, vs0, ps0, owns0), markedp(orl0, ps0), markedp(orl0, vs0), nextnottid(tid, vhead0, vs0), noid(tid, orl0 + qrl0, vhead0, vs0), nonullRetRefs(orl0 + qrl0, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(vretRefs0, vrvHp0, rvowns0), rvownerok(pretRefs0, prvHp0, rvowns0), unmarkedp(qrl0, ps0), phead0 ∈ orl0, vretRefs0(tid) ∈ vrvHp0, phead0 ∈ vs0, phead0 ∈ ps0, ¬ dups(orl0 + qrl0), ¬ dups(orl0), ¬ dups(qrl0), vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), lst = (orl0 + qrl0).last ∨ qrl0 ≠ [] ∧ lst = (orl0 + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null, lst ∈ orl0 ∨ lst ∈ qrl0, orl0.last = vhead0 ∧ (qrl0 ≠ [] → unmarkedp(qrl0.tail, vs0)) ∨ orl0.butlast ≠ [] ∧ orl0.butlast.last = vhead0 ∧ phead0 ≠ orl0.last ∧ unmarkedp(qrl0, vs0) ⊦ qrl0 ≠ [] ∧ vs0[lst].next = (orl0 + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null

User applied rule apply elim lemma

And obtained the following new goals

Rule argument

spec: list-last[reflist], name:last-elim, seq:x ≠ [] ⊦ a = x.last ∧ y = x.butlast ↔ x = y + a ', subst:[x, a, y] → [orl0, phead, rl]

Additional information

Used simplifier rules: x ≠ [] ⊦ a = x.last ∧ y = x.butlast ↔ x = y + a '; (elim) Used terms: orl0, phead, y

Proof step 14 from proof step-D17-D6 (previous step) (back to tree)

orl0 + qrl0 = rl1 + lst ' + rl2, ps0[lst].next = vs0[lst].next, dom vrvHp0 = dom prvHp0, orl0 = rl + phead ', pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[lst].next ≠ null, vs0[lst].next ≠ (orl0 + qrl0).last, orl0 ≠ [], vretRefs0(tid) ≠ null, allocrv(pretRefs0, prvHp0), allocrv(vretRefs0, vrvHp0), listp(lst ' + rl2, vs0, ps0, owns0), listp(orl0 + qrl0, vs0, ps0, owns0), markedp(orl0, vs0), markedp(orl0, ps0), nextnottid(tid, vhead0, vs0), noid(tid, orl0 + qrl0, vhead0, vs0), nonullRetRefs(orl0 + qrl0, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(pretRefs0, prvHp0, rvowns0), rvownerok(vretRefs0, vrvHp0, rvowns0), unmarkedp(qrl0, ps0), phead0 ∈ ps0, phead0 ∈ vs0, vretRefs0(tid) ∈ vrvHp0, phead0 ∈ orl0, ¬ dups(orl0 + qrl0), ¬ dups(orl0), ¬ dups(qrl0), vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), phead = vhead0 ∧ (qrl0 ≠ [] → unmarkedp(qrl0.tail, vs0)) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl0, vs0), lst ∈ orl0 ∨ lst ∈ qrl0, lst = (orl0 + qrl0).last ∨ qrl0 ≠ [] ∧ lst = (orl0 + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null ⊦ qrl0 ≠ [] ∧ vs0[lst].next = (orl0 + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] a: ⊦ ¬ dups(x + y) → ¬ dups(x) ∧ ¬ dups(y); (forward) from specification list-dup[reflist] ⊦ (x + a ' + y).last = (a ' + y).last; (s) ⊦ a ∈ b ' ↔ a = b; (s) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) ⊦ ¬ b ∈ x → (dups(x + b ') ↔ dups(x)); (s) ⊦ dups(x + a ' + y) ↔ a ∈ x ∨ a ∈ y ∨ dups(x + y); (ws) ⊦ markedp(r ', vs) ↔ some?(vs[r].deqID); (s) ⊦ markedp(rl + rl0, vs) ↔ markedp(rl, vs) ∧ markedp(rl0, vs); (s) ⊦ x + a ' ≠ []; (s)

Proof step 15 from proof step-D17-D6 (previous step) (back to tree)

(rl + phead ') + qrl0 = rl1 + lst ' + rl2, ps0[lst].next = vs0[lst].next, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[lst].next ≠ null, vs0[lst].next ≠ (phead ' + qrl0).last, vretRefs0(tid) ≠ null, allocrv(vretRefs0, vrvHp0), allocrv(pretRefs0, prvHp0), listp(rl1 + lst ' + rl2, vs0, ps0, owns0), listp(lst ' + rl2, vs0, ps0, owns0), markedp(rl, ps0), markedp(rl, vs0), nextnottid(tid, vhead0, vs0), noid(tid, rl1 + lst ' + rl2, vhead0, vs0), nonullRetRefs(rl1 + lst ' + rl2, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(vretRefs0, vrvHp0, rvowns0), rvownerok(pretRefs0, prvHp0, rvowns0), some?(ps0[phead].deqID), some?(vs0[phead].deqID), unmarkedp(qrl0, ps0), vretRefs0(tid) ∈ vrvHp0, phead0 ∈ vs0, phead0 ∈ ps0, ¬ dups(rl + qrl0), ¬ dups(rl), ¬ dups(qrl0), ¬ phead ∈ rl, ¬ phead ∈ qrl0, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), phead = vhead0 ∧ (qrl0 ≠ [] → unmarkedp(qrl0.tail, vs0)) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl0, vs0), phead0 ∈ rl ∨ phead0 = phead, lst = (phead ' + qrl0).last ∨ qrl0 ≠ [] ∧ lst = (phead ' + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null, lst ∈ rl ∨ lst = phead ∨ lst ∈ qrl0 ⊦ qrl0 ≠ [] ∧ vs0[lst].next = (phead ' + qrl0.butlast).last ∧ vs0[qrl0.last].deqID = None ∧ vs0[qrl0.last].next = null

User applied rule apply elim lemma

And obtained the following new goals

Rule argument

spec: list-last[reflist], name:last-elim, seq:x ≠ [] ⊦ a = x.last ∧ y = x.butlast ↔ x = y + a ', subst:[x, a, y] → [qrl0, vhead, qrl]

Additional information

Used simplifier rules: ⊦ ¬ dups([]); (s) ⊦ ¬ a ∈ []; (s) ⊦ unmarkedp([], vs); (s) ⊦ a '.last = a; (s) in-15: ⊦ x + a ' = y → a ∈ y; (forward) from specification list[reflist] ⊦ ¬ a ∈ x → (x + a ' = y + a ' + z ↔ y = x ∧ z = []); (ws) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) ⊦ a ∈ b ' + x ↔ a = b ∨ a ∈ x; (s) ⊦ x + [] = x; (s) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] ⊦ listp(r ', vs, ps, owns) ↔ owns(r) = None ∧ r ∈ vs ∧ r ∈ ps ∧ r ≠ null ∧ ¬ weak?(vs[r].deqID) ∧ (ps[r].deqID = vs[r].deqID ∨ ps[r].deqID = None) ∧ ps[r].val = vs[r].val ∧ ps[r].next = null ∧ ( vs[r].next ≠ null → vs[r].next ∈ vs ∧ vs[r].next ∈ ps ∧ ps[vs[r].next] = vs[vs[r].next] ∧ ps[vs[r].next].deqID = None ∧ ps[vs[r].next].next = null ∧ weak?(owns(vs[r].next))); (s) ⊦ some?(opttid) → opttid ≠ None; (as) x ≠ [] ⊦ a = x.last ∧ y = x.butlast ↔ x = y + a '; (elim) Used terms: qrl0, vhead, y

Proof step 16 from proof step-D17-D6 (previous step) (back to tree)

(rl + phead ') + qrl0 = rl1 + lst ' + rl2, ps0[lst].next = vs0[lst].next, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), qrl0 = qrl + vhead ', rvowns0(vretRefs0(tid)) = Pending(tid), vs0[lst].next ≠ null, vs0[lst].next ≠ (phead ' + qrl0).last, qrl0 ≠ [], vretRefs0(tid) ≠ null, allocrv(pretRefs0, prvHp0), allocrv(vretRefs0, vrvHp0), listp(lst ' + rl2, vs0, ps0, owns0), listp(rl1 + lst ' + rl2, vs0, ps0, owns0), markedp(rl, vs0), markedp(rl, ps0), nextnottid(tid, vhead0, vs0), noid(tid, rl1 + lst ' + rl2, vhead0, vs0), nonullRetRefs(rl1 + lst ' + rl2, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(pretRefs0, prvHp0, rvowns0), rvownerok(vretRefs0, vrvHp0, rvowns0), some?(vs0[phead].deqID), some?(ps0[phead].deqID), unmarkedp(qrl0, ps0), phead0 ∈ ps0, phead0 ∈ vs0, vretRefs0(tid) ∈ vrvHp0, ¬ dups(rl + qrl0), ¬ dups(rl), ¬ dups(qrl0), ¬ phead ∈ rl, ¬ phead ∈ qrl0, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), lst ∈ rl ∨ lst = phead ∨ lst ∈ qrl0, lst = (phead ' + qrl0).last ∨ qrl0 ≠ [] ∧ lst = (phead ' + qrl).last ∧ vs0[vhead].deqID = None ∧ vs0[vhead].next = null, phead0 ∈ rl ∨ phead0 = phead, phead = vhead0 ∧ (qrl0 ≠ [] → unmarkedp(qrl0.tail, vs0)) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl0, vs0) ⊦ qrl0 ≠ [] ∧ vs0[lst].next = (phead ' + qrl).last ∧ vs0[vhead].deqID = None ∧ vs0[vhead].next = null

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] ⊦ a ∈ b ' + x ↔ a = b ∨ a ∈ x; (s) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) a: ⊦ ¬ dups(x + y) → ¬ dups(x) ∧ ¬ dups(y); (forward) from specification list-dup[reflist] in-15: ⊦ x + a ' = y → a ∈ y; (forward) from specification list[reflist] ⊦ x + a ' ≠ []; (s) ⊦ a ∈ b ' ↔ a = b; (s) ⊦ (a ' + x + b ').last = b; (s) ⊦ unmarkedp(r ', vs) ↔ vs[r].deqID = None; (s) ⊦ unmarkedp(rl + rl0, vs) ↔ unmarkedp(rl, vs) ∧ unmarkedp(rl0, vs); (s) ⊦ ¬ b ∈ x → (dups(x + b ') ↔ dups(x)); (s) ⊦ dups(x + a ') ↔ a ∈ x ∨ dups(x); (ws) ⊦ (x + a ').last = a; (s) ⊦ x ≠ [] → (a ' + x).last = x.last; (s)

Proof step 17 from proof step-D17-D6 (previous step) (back to tree)

(rl + phead ') + qrl + vhead ' = rl1 + lst ' + rl2, ps0[vhead].deqID = None, ps0[lst].next = vs0[lst].next, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[lst].next ≠ vhead, vs0[lst].next ≠ null, phead ≠ vhead, vretRefs0(tid) ≠ null, allocrv(pretRefs0, prvHp0), allocrv(vretRefs0, vrvHp0), listp(lst ' + rl2, vs0, ps0, owns0), listp(rl1 + lst ' + rl2, vs0, ps0, owns0), markedp(rl, vs0), markedp(rl, ps0), nextnottid(tid, vhead0, vs0), noid(tid, rl1 + lst ' + rl2, vhead0, vs0), nonullRetRefs(rl1 + lst ' + rl2, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(pretRefs0, prvHp0, rvowns0), rvownerok(vretRefs0, vrvHp0, rvowns0), some?(vs0[phead].deqID), some?(ps0[phead].deqID), unmarkedp(qrl, ps0), phead0 ∈ ps0, phead0 ∈ vs0, vretRefs0(tid) ∈ vrvHp0, ¬ dups(qrl), ¬ dups(rl), ¬ dups(rl + qrl), ¬ phead ∈ qrl, ¬ phead ∈ rl, ¬ vhead ∈ qrl, ¬ vhead ∈ rl, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), lst ∈ rl ∨ lst = phead ∨ lst ∈ qrl ∨ lst = vhead, lst = vhead ∨ lst = (phead ' + qrl).last ∧ vs0[vhead].deqID = None ∧ vs0[vhead].next = null, phead = vhead0 ∧ unmarkedp((qrl + vhead ').tail, vs0) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl, vs0) ∧ vs0[vhead].deqID = None, phead0 ∈ rl ∨ phead0 = phead, vhead ∈ rl1 ∨ vhead = lst ∨ vhead ∈ rl2 ⊦ vs0[lst].next = (phead ' + qrl).last ∧ vs0[vhead].deqID = None ∧ vs0[vhead].next = null

Heuristic elimination applied rule apply elim lemma

And obtained the following new goals

Rule argument

spec: list-data[reflist], name:elim-list-c, seq:x ≠ [] ⊦ a = x.head ∧ y = x.tail ↔ x = a + y, subst:[x, a, y] → [qrl + vhead ', lst0, qrl0]

Additional information

Used simplifier rules: ⊦ x + y = [] ↔ x = [] ∧ y = []; (as) ⊦ a ' ≠ []; (s) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] x ≠ [] ⊦ a = x.head ∧ y = x.tail ↔ x = a + y; (elim) Used terms: qrl + vhead ', lst0, y

Proof step 18 from proof step-D17-D6 (previous step) (back to tree)

(rl + phead ') + qrl + vhead ' = rl1 + lst ' + rl2, qrl + vhead ' = lst0 + qrl0, ps0[vhead].deqID = None, ps0[lst].next = vs0[lst].next, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), qrl + vhead ' ≠ [], vs0[lst].next ≠ vhead, vs0[lst].next ≠ null, phead ≠ vhead, vretRefs0(tid) ≠ null, allocrv(vretRefs0, vrvHp0), allocrv(pretRefs0, prvHp0), listp(rl1 + lst ' + rl2, vs0, ps0, owns0), listp(lst ' + rl2, vs0, ps0, owns0), markedp(rl, ps0), markedp(rl, vs0), nextnottid(tid, vhead0, vs0), noid(tid, rl1 + lst ' + rl2, vhead0, vs0), nonullRetRefs(rl1 + lst ' + rl2, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(vretRefs0, vrvHp0, rvowns0), rvownerok(pretRefs0, prvHp0, rvowns0), some?(ps0[phead].deqID), some?(vs0[phead].deqID), unmarkedp(qrl, ps0), vretRefs0(tid) ∈ vrvHp0, phead0 ∈ vs0, phead0 ∈ ps0, ¬ dups(qrl), ¬ dups(rl), ¬ dups(rl + qrl), ¬ phead ∈ qrl, ¬ phead ∈ rl, ¬ vhead ∈ qrl, ¬ vhead ∈ rl, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), vhead ∈ rl1 ∨ vhead = lst ∨ vhead ∈ rl2, phead0 ∈ rl ∨ phead0 = phead, phead = vhead0 ∧ unmarkedp(qrl0, vs0) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl, vs0) ∧ vs0[vhead].deqID = None, lst = vhead ∨ lst = (phead ' + qrl).last ∧ vs0[vhead].deqID = None ∧ vs0[vhead].next = null, lst ∈ rl ∨ lst = phead ∨ lst ∈ qrl ∨ lst = vhead ⊦ vs0[lst].next = (phead ' + qrl).last ∧ vs0[vhead].deqID = None ∧ vs0[vhead].next = null

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] ⊦ a ∈ b ' ↔ a = b; (s) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) ⊦ a ∈ b ' + x ↔ a = b ∨ a ∈ x; (s) in-14: ⊦ a ' + x = y → a ∈ y; (forward) from specification list[reflist] in-15: ⊦ x + a ' = y → a ∈ y; (forward) from specification list[reflist] ⊦ x + a ' ≠ []; (s) ⊦ a + x = a ' + x; (s)

Proof step 19 from proof step-D17-D6 (previous step) (back to tree)

qrl + vhead ' = lst0 ' + qrl0, (rl + phead ') + lst0 ' + qrl0 = rl1 + lst ' + rl2, ps0[vhead].deqID = None, ps0[lst].next = vs0[lst].next, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[lst].next ≠ null, vs0[lst].next ≠ vhead, phead ≠ vhead, vretRefs0(tid) ≠ null, allocrv(vretRefs0, vrvHp0), allocrv(pretRefs0, prvHp0), listp(rl1 + lst ' + rl2, vs0, ps0, owns0), listp(lst ' + rl2, vs0, ps0, owns0), markedp(rl, ps0), markedp(rl, vs0), nextnottid(tid, vhead0, vs0), noid(tid, rl1 + lst ' + rl2, vhead0, vs0), nonullRetRefs(rl1 + lst ' + rl2, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(vretRefs0, vrvHp0, rvowns0), rvownerok(pretRefs0, prvHp0, rvowns0), some?(ps0[phead].deqID), some?(vs0[phead].deqID), unmarkedp(qrl, ps0), vretRefs0(tid) ∈ vrvHp0, phead0 ∈ vs0, phead0 ∈ ps0, ¬ dups(rl + qrl), ¬ dups(rl), ¬ dups(qrl), ¬ vhead ∈ rl, ¬ vhead ∈ qrl, ¬ phead ∈ rl, ¬ phead ∈ qrl, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), vhead ∈ rl1 ∨ vhead = lst ∨ vhead ∈ rl2, phead0 ∈ rl ∨ phead0 = phead, phead = vhead0 ∧ unmarkedp(qrl0, vs0) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl, vs0) ∧ vs0[vhead].deqID = None, lst = vhead ∨ lst = (phead ' + qrl).last ∧ vs0[vhead].deqID = None ∧ vs0[vhead].next = null, lst ∈ rl ∨ lst = phead ∨ lst ∈ qrl ∨ lst = vhead, vhead = lst0 ∨ vhead ∈ qrl0, lst0 ∈ qrl ∨ lst0 = vhead ⊦ vs0[lst].next = (phead ' + qrl).last ∧ vs0[vhead].deqID = None ∧ vs0[vhead].next = null

User applied rule case distinction

And obtained the following new goals

Rule argument

pos: left 41

Additional information

Proof step 20 from proof step-D17-D6 (previous step) (back to tree)

(rl + phead ') + lst0 ' + qrl0 = rl1 + lst ' + rl2, qrl + vhead ' = lst0 ' + qrl0, ps0[vhead].deqID = None, ps0[lst].next = vs0[lst].next, dom vrvHp0 = dom prvHp0, lst = vhead, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[lst].next ≠ null, vs0[lst].next ≠ vhead, phead ≠ vhead, vretRefs0(tid) ≠ null, allocrv(pretRefs0, prvHp0), allocrv(vretRefs0, vrvHp0), listp(lst ' + rl2, vs0, ps0, owns0), listp(rl1 + lst ' + rl2, vs0, ps0, owns0), markedp(rl, vs0), markedp(rl, ps0), nextnottid(tid, vhead0, vs0), noid(tid, rl1 + lst ' + rl2, vhead0, vs0), nonullRetRefs(rl1 + lst ' + rl2, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(pretRefs0, prvHp0, rvowns0), rvownerok(vretRefs0, vrvHp0, rvowns0), some?(vs0[phead].deqID), some?(ps0[phead].deqID), unmarkedp(qrl, ps0), phead0 ∈ ps0, phead0 ∈ vs0, vretRefs0(tid) ∈ vrvHp0, ¬ dups(rl + qrl), ¬ dups(rl), ¬ dups(qrl), ¬ vhead ∈ rl, ¬ vhead ∈ qrl, ¬ phead ∈ rl, ¬ phead ∈ qrl, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), lst0 ∈ qrl ∨ lst0 = vhead, vhead = lst0 ∨ vhead ∈ qrl0, lst ∈ rl ∨ lst = phead ∨ lst ∈ qrl ∨ lst = vhead, phead = vhead0 ∧ unmarkedp(qrl0, vs0) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl, vs0) ∧ vs0[vhead].deqID = None, phead0 ∈ rl ∨ phead0 = phead, vhead ∈ rl1 ∨ vhead = lst ∨ vhead ∈ rl2 ⊦ vs0[lst].next = (phead ' + qrl).last ∧ vs0[vhead].deqID = None ∧ vs0[vhead].next = null

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Proof step 21 from proof step-D17-D6 (previous step) (back to tree)

qrl + vhead ' = lst0 ' + qrl0, (rl + phead ') + lst0 ' + qrl0 = rl1 + vhead ' + rl2, ps0[vhead].deqID = None, ps0[vhead].next = vs0[vhead].next, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[vhead].next ≠ null, vs0[vhead].next ≠ vhead, phead ≠ vhead, vretRefs0(tid) ≠ null, allocrv(vretRefs0, vrvHp0), allocrv(pretRefs0, prvHp0), listp(rl1 + vhead ' + rl2, vs0, ps0, owns0), listp(vhead ' + rl2, vs0, ps0, owns0), markedp(rl, ps0), markedp(rl, vs0), nextnottid(tid, vhead0, vs0), noid(tid, rl1 + vhead ' + rl2, vhead0, vs0), nonullRetRefs(rl1 + vhead ' + rl2, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(vretRefs0, vrvHp0, rvowns0), rvownerok(pretRefs0, prvHp0, rvowns0), some?(ps0[phead].deqID), some?(vs0[phead].deqID), unmarkedp(qrl, ps0), vretRefs0(tid) ∈ vrvHp0, phead0 ∈ vs0, phead0 ∈ ps0, ¬ dups(rl + qrl), ¬ dups(rl), ¬ dups(qrl), ¬ vhead ∈ rl, ¬ vhead ∈ qrl, ¬ phead ∈ rl, ¬ phead ∈ qrl, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), phead0 ∈ rl ∨ phead0 = phead, phead = vhead0 ∧ unmarkedp(qrl0, vs0) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl, vs0) ∧ vs0[vhead].deqID = None, vhead = lst0 ∨ vhead ∈ qrl0, lst0 ∈ qrl ∨ lst0 = vhead ⊦

User applied rule constructor cut

And closed the goal!

Rule argument

var: rl2

Additional information

Used simplifier rules: reflist freely generated by [], +;; ⊦ a + x = a ' + x; (s) ⊦ listp(r ' + r0 ' + rl, vs, ps, owns) ↔ owns(r) = None ∧ r ∈ vs ∧ r ∈ ps ∧ r ≠ null ∧ ¬ weak?(vs[r].deqID) ∧ (ps[r].deqID = vs[r].deqID ∨ ps[r].deqID = None) ∧ ps[r].val = vs[r].val ∧ ps[r].next = vs[r].next ∧ ps[r].next = r0 ∧ listp(r0 ' + rl, vs, ps, owns); (s) listp-twoin: ⊦ listp(rl + r ' + r0 ' + rl0, vs, ps, owns) → ps[r].next = r0; (forward) from specification DMSQ in-14: ⊦ a ' + x = y → a ∈ y; (forward) from specification list[reflist] in-16: ⊦ x + a ' = y + b ' + z ∧ a ≠ b → a ∈ z; (forward) from specification list[reflist] inex: ⊦ x + a ' = y + b ' + z ∧ a ≠ b → (∃ z0. z = z0 + a '); (forward) from specification list[reflist] in-15: ⊦ x + a ' = y → a ∈ y; (forward) from specification list[reflist] ⊦ a ∈ b ' + x ↔ a = b ∨ a ∈ x; (s) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) ⊦ a ∈ b ' ↔ a = b; (s) ⊦ a ∈ y → a ∈ x + y; (s) list-elem-in-app22: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ qrl → node ∈ ps; (forward) from specification DMSQ list-elem-in-app21: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ qrl → node ∈ vs; (forward) from specification DMSQ ⊦ # y = # y0 → (x + y = z + y0 ↔ x = z ∧ y = y0); (ws) ⊦ ¬ a ∈ y ∧ ¬ a ∈ z ∧ a ≠ c → y + c ' + z ≠ y1 + a ' + x; (s) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] ⊦ x + [] = x; (s) ⊦ listp(r ', vs, ps, owns) ↔ owns(r) = None ∧ r ∈ vs ∧ r ∈ ps ∧ r ≠ null ∧ ¬ weak?(vs[r].deqID) ∧ (ps[r].deqID = vs[r].deqID ∨ ps[r].deqID = None) ∧ ps[r].val = vs[r].val ∧ ps[r].next = null ∧ ( vs[r].next ≠ null → vs[r].next ∈ vs ∧ vs[r].next ∈ ps ∧ ps[vs[r].next] = vs[vs[r].next] ∧ ps[vs[r].next].deqID = None ∧ ps[vs[r].next].next = null ∧ weak?(owns(vs[r].next))); (s)

Proof step 22 from proof step-D17-D6 (previous step) (back to tree)

(rl + phead ') + lst0 ' + qrl0 = rl1 + lst ' + rl2, qrl + vhead ' = lst0 ' + qrl0, ps0[vhead].deqID = None, vs0[vhead].deqID = None, ps0[lst].next = vs0[lst].next, vs0[vhead].next = null, dom vrvHp0 = dom prvHp0, lst = (phead ' + qrl).last, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[lst].next ≠ null, vs0[lst].next ≠ vhead, phead ≠ vhead, vretRefs0(tid) ≠ null, allocrv(pretRefs0, prvHp0), allocrv(vretRefs0, vrvHp0), listp(lst ' + rl2, vs0, ps0, owns0), listp(rl1 + lst ' + rl2, vs0, ps0, owns0), markedp(rl, vs0), markedp(rl, ps0), nextnottid(tid, vhead0, vs0), noid(tid, rl1 + lst ' + rl2, vhead0, vs0), nonullRetRefs(rl1 + lst ' + rl2, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(pretRefs0, prvHp0, rvowns0), rvownerok(vretRefs0, vrvHp0, rvowns0), some?(vs0[phead].deqID), some?(ps0[phead].deqID), unmarkedp(qrl, ps0), phead0 ∈ ps0, phead0 ∈ vs0, vretRefs0(tid) ∈ vrvHp0, ¬ dups(rl + qrl), ¬ dups(rl), ¬ dups(qrl), ¬ vhead ∈ rl, ¬ vhead ∈ qrl, ¬ phead ∈ rl, ¬ phead ∈ qrl, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), lst0 ∈ qrl ∨ lst0 = vhead, vhead = lst0 ∨ vhead ∈ qrl0, lst ∈ rl ∨ lst = phead ∨ lst ∈ qrl ∨ lst = vhead, phead = vhead0 ∧ unmarkedp(qrl0, vs0) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl, vs0) ∧ vs0[vhead].deqID = None, phead0 ∈ rl ∨ phead0 = phead, vhead ∈ rl1 ∨ vhead = lst ∨ vhead ∈ rl2 ⊦ vs0[lst].next = (phead ' + qrl).last ∧ vs0[vhead].deqID = None ∧ vs0[vhead].next = null

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] ⊦ a ∈ b ' + x ↔ a = b ∨ a ∈ x; (s) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) ⊦ a ∈ b ' ↔ a = b; (s) in-15: ⊦ x + a ' = y → a ∈ y; (forward) from specification list[reflist] in-14: ⊦ a ' + x = y → a ∈ y; (forward) from specification list[reflist] listp-twoin: ⊦ listp(rl + r ' + r0 ' + rl0, vs, ps, owns) → ps[r].next = r0; (forward) from specification DMSQ

Proof step 23 from proof step-D17-D6 (previous step) (back to tree)

qrl + vhead ' = ps0[phead].next ' + qrl0, (rl + phead ') + qrl + vhead ' = rl1 + (phead ' + qrl).last ' + rl2, vs0[vhead].deqID = None, ps0[vhead].deqID = None, vs0[vhead].next = null, ps0[(phead ' + qrl).last].next = vs0[(phead ' + qrl).last].next, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[(phead ' + qrl).last].next ≠ null, vs0[(phead ' + qrl).last].next ≠ vhead, vs0[(phead ' + qrl).last].next ≠ (phead ' + qrl).last, phead ≠ vhead, vretRefs0(tid) ≠ null, allocrv(vretRefs0, vrvHp0), allocrv(pretRefs0, prvHp0), listp((rl + phead ') + qrl + vhead ', vs0, ps0, owns0), listp((phead ' + qrl).last ' + rl2, vs0, ps0, owns0), markedp(rl, ps0), markedp(rl, vs0), nextnottid(tid, vhead0, vs0), noid(tid, (rl + phead ') + qrl + vhead ', vhead0, vs0), nonullRetRefs((rl + phead ') + qrl + vhead ', vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(vretRefs0, vrvHp0, rvowns0), rvownerok(pretRefs0, prvHp0, rvowns0), some?(ps0[phead].deqID), some?(vs0[phead].deqID), unmarkedp(qrl, ps0), vretRefs0(tid) ∈ vrvHp0, phead0 ∈ vs0, phead0 ∈ ps0, ¬ dups(rl + qrl), ¬ dups(rl), ¬ dups(qrl), ¬ vhead ∈ rl, ¬ vhead ∈ qrl, ¬ phead ∈ rl, ¬ phead ∈ qrl, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), phead0 ∈ rl ∨ phead0 = phead, vhead = ps0[phead].next ∨ vhead ∈ qrl0, phead = vhead0 ∧ unmarkedp(qrl0, vs0) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl, vs0), (phead ' + qrl).last ∈ rl ∨ (phead ' + qrl).last = phead ∨ (phead ' + qrl).last ∈ qrl, ps0[phead].next ∈ qrl ∨ ps0[phead].next = vhead, vhead ∈ rl1 ∨ vhead ∈ rl2 ⊦

Heuristic use patterns applied rule apply elim lemma

And obtained the following new goals

Rule argument

spec: list-last[reflist], name:last-elim, seq:x ≠ [] ⊦ a = x.last ∧ y = x.butlast ↔ x = y + a ', subst:[x, a, y] → [phead ' + qrl, phead1, rl0]

Additional information

Used simplifier rules: ⊦ x + y = [] ↔ x = [] ∧ y = []; (as) ⊦ a ' ≠ []; (s) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] x ≠ [] ⊦ a = x.last ∧ y = x.butlast ↔ x = y + a '; (elim) Used terms: phead ' + qrl, phead1, y

Proof step 24 from proof step-D17-D6 (previous step) (back to tree)

(rl + phead ') + qrl + vhead ' = rl1 + phead1 ' + rl2, qrl + vhead ' = ps0[phead].next ' + qrl0, phead ' + qrl = rl0 + phead1 ', ps0[vhead].deqID = None, vs0[vhead].deqID = None, ps0[phead1].next = vs0[phead1].next, vs0[vhead].next = null, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), phead ' + qrl ≠ [], vs0[phead1].next ≠ null, vs0[phead1].next ≠ vhead, vs0[phead1].next ≠ phead1, phead ≠ vhead, vretRefs0(tid) ≠ null, allocrv(pretRefs0, prvHp0), allocrv(vretRefs0, vrvHp0), listp(phead1 ' + rl2, vs0, ps0, owns0), listp((rl + phead ') + qrl + vhead ', vs0, ps0, owns0), markedp(rl, vs0), markedp(rl, ps0), nextnottid(tid, vhead0, vs0), noid(tid, (rl + phead ') + qrl + vhead ', vhead0, vs0), nonullRetRefs((rl + phead ') + qrl + vhead ', vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(pretRefs0, prvHp0, rvowns0), rvownerok(vretRefs0, vrvHp0, rvowns0), some?(vs0[phead].deqID), some?(ps0[phead].deqID), unmarkedp(qrl, ps0), phead0 ∈ ps0, phead0 ∈ vs0, vretRefs0(tid) ∈ vrvHp0, ¬ dups(rl + qrl), ¬ dups(rl), ¬ dups(qrl), ¬ vhead ∈ rl, ¬ vhead ∈ qrl, ¬ phead ∈ rl, ¬ phead ∈ qrl, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), vhead ∈ rl1 ∨ vhead ∈ rl2, ps0[phead].next ∈ qrl ∨ ps0[phead].next = vhead, phead1 ∈ rl ∨ phead1 = phead ∨ phead1 ∈ qrl, phead = vhead0 ∧ unmarkedp(qrl0, vs0) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl, vs0), vhead = ps0[phead].next ∨ vhead ∈ qrl0, phead0 ∈ rl ∨ phead0 = phead ⊦

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] ⊦ a ∈ b ' + x ↔ a = b ∨ a ∈ x; (s) ⊦ a ∈ b ' ↔ a = b; (s) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) in-15: ⊦ x + a ' = y → a ∈ y; (forward) from specification list[reflist] in-14: ⊦ a ' + x = y → a ∈ y; (forward) from specification list[reflist] ⊦ a ' + x ≠ []; (s)

Proof step 25 from proof step-D17-D6 (previous step) (back to tree)

(rl + phead ') + qrl + vhead ' = rl1 + phead1 ' + rl2, qrl + vhead ' = ps0[phead].next ' + qrl0, phead ' + qrl = rl0 + phead1 ', ps0[vhead].deqID = None, vs0[vhead].deqID = None, ps0[phead1].next = vs0[phead1].next, vs0[vhead].next = null, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[phead1].next ≠ phead1, vs0[phead1].next ≠ vhead, vs0[phead1].next ≠ null, phead ≠ vhead, vretRefs0(tid) ≠ null, allocrv(pretRefs0, prvHp0), allocrv(vretRefs0, vrvHp0), listp(phead1 ' + rl2, vs0, ps0, owns0), listp(rl1 + phead1 ' + rl2, vs0, ps0, owns0), markedp(rl, vs0), markedp(rl, ps0), nextnottid(tid, vhead0, vs0), noid(tid, rl1 + phead1 ' + rl2, vhead0, vs0), nonullRetRefs(rl1 + phead1 ' + rl2, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(pretRefs0, prvHp0, rvowns0), rvownerok(vretRefs0, vrvHp0, rvowns0), some?(vs0[phead].deqID), some?(ps0[phead].deqID), unmarkedp(qrl, ps0), phead0 ∈ ps0, phead0 ∈ vs0, vretRefs0(tid) ∈ vrvHp0, ¬ dups(qrl), ¬ dups(rl), ¬ dups(rl + qrl), ¬ phead ∈ qrl, ¬ phead ∈ rl, ¬ vhead ∈ qrl, ¬ vhead ∈ rl, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), ps0[phead].next ∈ qrl ∨ ps0[phead].next = vhead, phead1 ∈ rl ∨ phead1 = phead ∨ phead1 ∈ qrl, phead = vhead0 ∧ unmarkedp(qrl0, vs0) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl, vs0), vhead = ps0[phead].next ∨ vhead ∈ qrl0, phead0 ∈ rl ∨ phead0 = phead, vhead ∈ rl1 ∨ vhead ∈ rl2, phead ∈ rl0 ∨ phead = phead1, phead1 = phead ∨ phead1 ∈ qrl ⊦

User applied rule constructor cut

And obtained the following new goals

Rule argument

var: rl2

Additional information

Used simplifier rules: reflist freely generated by [], +;; ⊦ x + [] = x; (s) ⊦ x + a ' = y + b ' ↔ x = y ∧ a = b; (ws) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist]

Proof step 26 from proof step-D17-D6 (previous step) (back to tree)

phead ' + qrl = rl0 + phead1 ', qrl + vhead ' = ps0[phead].next ' + qrl0, (rl + phead ') + qrl + vhead ' = rl1 + phead1 ' + rl2, vs0[vhead].deqID = None, ps0[vhead].deqID = None, vs0[vhead].next = null, ps0[phead1].next = vs0[phead1].next, dom vrvHp0 = dom prvHp0, pretRefs0(tid) = vretRefs0(tid), rl2 = phead2 + rl3, rvowns0(vretRefs0(tid)) = Pending(tid), vs0[phead1].next ≠ phead1, vs0[phead1].next ≠ vhead, vs0[phead1].next ≠ null, phead ≠ vhead, vretRefs0(tid) ≠ null, allocrv(vretRefs0, vrvHp0), allocrv(pretRefs0, prvHp0), listp(rl1 + phead1 ' + rl2, vs0, ps0, owns0), listp(phead1 ' + rl2, vs0, ps0, owns0), markedp(rl, ps0), markedp(rl, vs0), nextnottid(tid, vhead0, vs0), noid(tid, rl1 + phead1 ' + rl2, vhead0, vs0), nonullRetRefs(rl1 + phead1 ' + rl2, vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(vretRefs0, vrvHp0, rvowns0), rvownerok(pretRefs0, prvHp0, rvowns0), some?(ps0[phead].deqID), some?(vs0[phead].deqID), unmarkedp(qrl, ps0), vretRefs0(tid) ∈ vrvHp0, phead0 ∈ vs0, phead0 ∈ ps0, ¬ dups(qrl), ¬ dups(rl), ¬ dups(rl + qrl), ¬ phead ∈ qrl, ¬ phead ∈ rl, ¬ vhead ∈ qrl, ¬ vhead ∈ rl, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), phead1 = phead ∨ phead1 ∈ qrl, phead ∈ rl0 ∨ phead = phead1, vhead ∈ rl1 ∨ vhead ∈ rl2, phead0 ∈ rl ∨ phead0 = phead, vhead = ps0[phead].next ∨ vhead ∈ qrl0, phead = vhead0 ∧ unmarkedp(qrl0, vs0) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl, vs0), phead1 ∈ rl ∨ phead1 = phead ∨ phead1 ∈ qrl, ps0[phead].next ∈ qrl ∨ ps0[phead].next = vhead ⊦

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] ⊦ a ∈ b ' ↔ a = b; (s) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) ⊦ # y = # y0 → (x + y = z + y0 ↔ x = z ∧ y = y0); (ws) ⊦ a ∈ y → a ∈ x + y; (s) in-15: ⊦ x + a ' = y → a ∈ y; (forward) from specification list[reflist] inex: ⊦ x + a ' = y + b ' + z ∧ a ≠ b → (∃ z0. z = z0 + a '); (forward) from specification list[reflist] in-16: ⊦ x + a ' = y + b ' + z ∧ a ≠ b → a ∈ z; (forward) from specification list[reflist] list-elem-in-app21: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ qrl → node ∈ vs; (forward) from specification DMSQ list-elem-in-app22: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ qrl → node ∈ ps; (forward) from specification DMSQ ni: ⊦ x + a ' = y + z ∧ ¬ a ∈ z → z = []; (forward) from specification list[reflist] ⊦ a ≠ b → (a ∈ b ' + x ↔ a ∈ x); (s) ⊦ a ∈ b ' + x ↔ a = b ∨ a ∈ x; (s) ⊦ a + x = a ' + x; (s) ⊦ listp(r ' + r0 ' + rl, vs, ps, owns) ↔ owns(r) = None ∧ r ∈ vs ∧ r ∈ ps ∧ r ≠ null ∧ ¬ weak?(vs[r].deqID) ∧ (ps[r].deqID = vs[r].deqID ∨ ps[r].deqID = None) ∧ ps[r].val = vs[r].val ∧ ps[r].next = vs[r].next ∧ ps[r].next = r0 ∧ listp(r0 ' + rl, vs, ps, owns); (s)

Proof step 27 from proof step-D17-D6 (previous step) (back to tree)

phead ' + qrl = rl0 + phead1 ', qrl + vhead ' = ps0[phead].next ' + qrl0, rl + rl0 = rl1 + phead1 ' + vs0[phead1].next ' + rl2, vs0[vhead].deqID = None, ps0[vhead].deqID = None, vs0[vhead].next = null, ps0[phead1].next = vs0[phead1].next, ps0[phead1].val = vs0[phead1].val, dom vrvHp0 = dom prvHp0, owns0(phead1) = None, pretRefs0(tid) = vretRefs0(tid), rvowns0(vretRefs0(tid)) = Pending(tid), vs0[phead1].next ≠ null, vs0[phead1].next ≠ vhead, vs0[phead1].next ≠ phead1, phead ≠ vhead, phead1 ≠ null, vretRefs0(tid) ≠ null, allocrv(vretRefs0, vrvHp0), allocrv(pretRefs0, prvHp0), listp((rl + phead ') + qrl + vhead ', vs0, ps0, owns0), listp(vs0[phead1].next ' + (rl2 + phead1 ') + vhead ', vs0, ps0, owns0), markedp(rl, ps0), markedp(rl, vs0), nextnottid(tid, vhead0, vs0), noid(tid, (rl + phead ') + qrl + vhead ', vhead0, vs0), nonullRetRefs((rl + phead ') + qrl + vhead ', vs0, vretRefs0, pretRefs0), noowns(tid, owns0), rvownerok(vretRefs0, vrvHp0, rvowns0), rvownerok(pretRefs0, prvHp0, rvowns0), some?(ps0[phead].deqID), some?(vs0[phead].deqID), unmarkedp(qrl, ps0), phead1 ∈ ps0, phead1 ∈ vs0, vretRefs0(tid) ∈ vrvHp0, phead0 ∈ vs0, phead0 ∈ ps0, vhead ∈ vs0, vhead ∈ ps0, ¬ dups(rl + qrl), ¬ dups(rl), ¬ dups(qrl), ¬ weak?(vs0[phead1].deqID), ¬ vhead ∈ rl, ¬ vhead ∈ qrl, ¬ phead ∈ rl, ¬ phead ∈ qrl, vs0[vhead0].next ≠ null ∧ vs0[vs0[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs0[vs0[vhead0].next].deqID.tid)) = Claimed(vs0[vs0[vhead0].next].deqID.tid, vs0[vs0[vhead0].next].val), ps0[phead1].deqID = vs0[phead1].deqID ∨ ps0[phead1].deqID = None, phead1 = phead ∨ phead1 ∈ qrl, phead ∈ rl0 ∨ phead = phead1, phead0 ∈ rl ∨ phead0 = phead, vhead = ps0[phead].next ∨ vhead ∈ qrl0, phead = vhead0 ∧ unmarkedp(qrl0, vs0) ∨ rl ≠ [] ∧ rl.last = vhead0 ∧ phead0 ≠ phead ∧ unmarkedp(qrl, vs0), phead1 ∈ rl ∨ phead1 = phead ∨ phead1 ∈ qrl, ps0[phead].next ∈ qrl ∨ ps0[phead].next = vhead ⊦

User applied rule apply lemma

And obtained the following new goals

Rule argument

spec: DMSQ, name:listp-postfix, seq: ⊦ listp(rl + rl0, vs, ps, owns) → (listp(rl0, vs, ps, owns) ↔ rl0 ≠ []), subst:[ps, rl, owns, rl0, vs] → [ps0, vs0[phead1].next ' + rl2, owns0, phead1 ' + vhead ', vs0]

Additional information

Used simplifier rules: ⊦ a ' + x ≠ []; (s) ⊦ listp(r ' + r0 ', vs, ps, owns) ↔ owns(r) = None ∧ r ∈ vs ∧ r ∈ ps ∧ r ≠ null ∧ ¬ weak?(vs[r].deqID) ∧ (ps[r].deqID = vs[r].deqID ∨ ps[r].deqID = None) ∧ ps[r].val = vs[r].val ∧ ps[r].next = vs[r].next ∧ ps[r].next = r0 ∧ r0 ≠ null ∧ owns(r0) = None ∧ r0 ∈ vs ∧ r0 ∈ ps ∧ ¬ weak?(vs[r0].deqID) ∧ (ps[r0].deqID = vs[r0].deqID ∨ ps[r0].deqID = None) ∧ ps[r0].val = vs[r0].val ∧ ps[r0].next = null ∧ ( vs[r0].next ≠ null → vs[r0].next ∈ vs ∧ vs[r0].next ∈ ps ∧ ps[vs[r0].next] = vs[vs[r0].next] ∧ ps[vs[r0].next].deqID = None ∧ ps[vs[r0].next].next = null ∧ weak?(owns(vs[r0].next))); (s) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] Used terms: ps0, vs0[phead1].next ' + rl2, owns0, phead1 ' + vhead ', vs0

Proof step 28 from proof step-D17-D6 (previous step) (back to tree)

⊦ listp(rl + rl0, vs, ps, owns) → (listp(rl0, vs, ps, owns) ↔ rl0 ≠ [])

A spec-lemma

Proof Tree for step-D17-D6 (View conclusion)

The following image shows the proof tree of sequent calculus. The proved goal is at the bottom. You can click on the nodes to view additional rules. See here for details on colors in a proof tree.

the proof tree