[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 DMSQInv-atDoEnq (conclusion) (back to tree)

DMSQInv(gs, lsf, pcf), gs.vs[(gs.orl + gs.qrl).last].next ≠ null ⊦ ( pcf(gs.owns(gs.vs[(gs.orl + gs.qrl).last].next).tid) = E10 ∧ lsf(gs.owns(gs.vs[(gs.orl + gs.qrl).last].next).tid).success ∨ pcf(gs.owns(gs.vs[(gs.orl + gs.qrl).last].next).tid) = E11) ∧ lsf(gs.owns(gs.vs[(gs.orl + gs.qrl).last].next).tid).node = gs.vs[(gs.orl + gs.qrl).last].next ∧ lsf(gs.owns(gs.vs[(gs.orl + gs.qrl).last].next).tid).lst = gs.vtail ∧ gs.vtail = (gs.orl + gs.qrl).last

System applied rule normalize

And obtained the following new goals

Rule argument

Additional information

Proof step 2 from proof DMSQInv-atDoEnq (previous step) (back to tree)

gs.vs[(gs.orl + gs.qrl).last].next ≠ null, DMSQInv(gs, lsf, pcf) ⊦ ( pcf(gs.owns(gs.vs[(gs.orl + gs.qrl).last].next).tid) = E10 ∧ lsf(gs.owns(gs.vs[(gs.orl + gs.qrl).last].next).tid).success ∨ pcf(gs.owns(gs.vs[(gs.orl + gs.qrl).last].next).tid) = E11) ∧ lsf(gs.owns(gs.vs[(gs.orl + gs.qrl).last].next).tid).node = gs.vs[(gs.orl + gs.qrl).last].next ∧ lsf(gs.owns(gs.vs[(gs.orl + gs.qrl).last].next).tid).lst = gs.vtail ∧ gs.vtail = (gs.orl + gs.qrl).last

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 3 from proof DMSQInv-atDoEnq (previous step) (back to tree)

gs = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), vs[(orl + qrl).last].next ≠ null, DMSQInv(gs, lsf, pcf) ⊦ ( pcf(owns(vs[(orl + qrl).last].next).tid) = E10 ∧ lsf(owns(vs[(orl + qrl).last].next).tid).success ∨ pcf(owns(vs[(orl + qrl).last].next).tid) = E11) ∧ lsf(owns(vs[(orl + qrl).last].next).tid).node = vs[(orl + qrl).last].next ∧ lsf(owns(vs[(orl + qrl).last].next).tid).lst = vtail ∧ vtail = (orl + qrl).last

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Proof step 4 from proof DMSQInv-atDoEnq (previous step) (back to tree)

vs[(orl + qrl).last].next ≠ null, DMSQInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf, pcf) ⊦ ( pcf(owns(vs[(orl + qrl).last].next).tid) = E10 ∧ lsf(owns(vs[(orl + qrl).last].next).tid).success ∨ pcf(owns(vs[(orl + qrl).last].next).tid) = E11) ∧ lsf(owns(vs[(orl + qrl).last].next).tid).node = vs[(orl + qrl).last].next ∧ lsf(owns(vs[(orl + qrl).last].next).tid).lst = (orl + qrl).last ∧ vtail = (orl + qrl).last

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, lsf(owns(vs[(orl + qrl).last].next).tid), 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, lsf(owns(vs[(orl + qrl).last].next).tid), addr, tid, lst, first, rvref, othertid, success, optval

Proof step 5 from proof DMSQInv-atDoEnq (previous step) (back to tree)

lsf(owns(vs[(orl + qrl).last].next).tid) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), vs[(orl + qrl).last].next ≠ null, DMSQInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf, pcf) ⊦ (pcf(owns(vs[(orl + qrl).last].next).tid) = E10 ∧ success ∨ pcf(owns(vs[(orl + qrl).last].next).tid) = E11) ∧ node = vs[(orl + qrl).last].next ∧ lst = (orl + qrl).last ∧ vtail = (orl + qrl).last

User applied rule apply rewrite lemma

And obtained the following new goals

Rule argument

spec: DMSQ, name:DMSQInv, seq:⊦ DMSQInv(gs, lsf, pcf) ↔ DMSQGInv(gs) ∧ (∀ tid. lsf(tid).tid = tid ∧ DMSQLInv(gs, lsf(tid), pcf(tid))), subst:[gs, lsf, pcf] → [mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf, pcf], <all paths>

Additional information

Used terms: mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf, pcf

Proof step 6 from proof DMSQInv-atDoEnq (previous step) (back to tree)

⊦ DMSQInv(gs, lsf, pcf) ↔ DMSQGInv(gs) ∧ (∀ tid. lsf(tid).tid = tid ∧ DMSQLInv(gs, lsf(tid), pcf(tid)))

A spec-lemma

Proof step 7 from proof DMSQInv-atDoEnq (previous step) (back to tree)

lsf(owns(vs[(orl + qrl).last].next).tid) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), vs[(orl + qrl).last].next ≠ null, DMSQGInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns)), ∀ tid. lsf(tid).tid = tid ∧ DMSQLInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf(tid), pcf(tid)) ⊦ (pcf(owns(vs[(orl + qrl).last].next).tid) = E10 ∧ success ∨ pcf(owns(vs[(orl + qrl).last].next).tid) = E11) ∧ node = vs[(orl + qrl).last].next ∧ lst = (orl + qrl).last ∧ vtail = (orl + qrl).last

User applied rule apply rewrite lemma

And obtained the following new goals

Rule argument

spec: DMSQ, name:DMSQGInv, seq:⊦ DMSQGInv(gs) ↔ 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), subst:[gs] → [mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns)], <all paths>

Additional information

Used terms: mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns)

Proof step 8 from proof DMSQInv-atDoEnq (previous step) (back to tree)

⊦ DMSQGInv(gs) ↔ 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)

A spec-lemma

Proof step 9 from proof DMSQInv-atDoEnq (previous step) (back to tree)

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

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] listp-nextoflast: ⊦ listp(rl, vs, ps, owns) ∧ vs[rl.last].next ≠ null → vs[rl.last].next ∈ vs ∧ vs[rl.last].next ∈ ps ∧ ps[vs[rl.last].next] = vs[vs[rl.last].next] ∧ ps[vs[rl.last].next].deqID = None ∧ ps[vs[rl.last].next].next = null ∧ weak?(owns(vs[rl.last].next)); (forward) from specification DMSQ 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) .vhead = phead0; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .vs = ps0; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .rvowns = rvowns; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .vretRefs = vretRefs; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .qrl = qrl; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .orl = qrl0; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .phead = phead; (s) ⊦ y ≠ [] → (x + y).last = y.last; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .vtail = phead1; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .vrvHp = vrvHp; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .prvHp = vrvHp0; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .pretRefs = vretRefs0; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .owns = owns; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .ps = ps; (s)

Proof step 10 from proof DMSQInv-atDoEnq (previous step) (back to tree)

vs[vs[(orl + qrl).last].next].deqID = None, vs[vs[(orl + qrl).last].next].next = null, ps[vs[(orl + qrl).last].next] = vs[vs[(orl + qrl).last].next], dom vrvHp = dom prvHp, lsf(owns(vs[(orl + qrl).last].next).tid) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), vs[(orl + qrl).last].next ≠ null, orl ≠ [], allocrv(vretRefs, vrvHp), allocrv(pretRefs, prvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, ps), markedp(orl, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), rvownerok(vretRefs, vrvHp, rvowns), rvownerok(pretRefs, prvHp, rvowns), unmarkedp(qrl, ps), weak?(owns(vs[(orl + qrl).last].next)), phead ∈ ps, phead ∈ vs, vs[(orl + qrl).last].next ∈ vs, vs[(orl + qrl).last].next ∈ ps, phead ∈ orl, ¬ 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), ∀ tid. lsf(tid).tid = tid ∧ DMSQLInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf(tid), pcf(tid)), orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null ⊦ (pcf(owns(vs[(orl + qrl).last].next).tid) = E10 ∧ success ∨ pcf(owns(vs[(orl + qrl).last].next).tid) = E11) ∧ node = vs[(orl + qrl).last].next ∧ lst = (orl + qrl).last ∧ vtail = (orl + qrl).last

Heuristic elimination applied rule apply elim lemma

And obtained the following new goals

Rule argument

spec: opttid, name:elim-Weak, seq: ⊦ weak?(opttid) → (tid = opttid.tid ↔ opttid = Weak(tid)), subst:[opttid, tid] → [owns(vs[(orl + qrl).last].next), tid0]

Additional information

Used simplifier rules: ⊦ weak?(opttid) → (tid = opttid.tid ↔ opttid = Weak(tid)); (elim) Used terms: owns(vs[(orl + qrl).last].next), tid0

Proof step 11 from proof DMSQInv-atDoEnq (previous step) (back to tree)

vs[vs[(orl + qrl).last].next].deqID = None, vs[vs[(orl + qrl).last].next].next = null, ps[vs[(orl + qrl).last].next] = vs[vs[(orl + qrl).last].next], dom vrvHp = dom prvHp, lsf(tid0) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), owns(vs[(orl + qrl).last].next) = Weak(tid0), vs[(orl + qrl).last].next ≠ null, orl ≠ [], allocrv(pretRefs, prvHp), allocrv(vretRefs, vrvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, vs), markedp(orl, ps), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), rvownerok(pretRefs, prvHp, rvowns), rvownerok(vretRefs, vrvHp, rvowns), unmarkedp(qrl, ps), weak?(owns(vs[(orl + qrl).last].next)), phead ∈ orl, vs[(orl + qrl).last].next ∈ ps, vs[(orl + qrl).last].next ∈ vs, phead ∈ vs, phead ∈ ps, ¬ 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), ∀ tid. lsf(tid).tid = tid ∧ DMSQLInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf(tid), pcf(tid)), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null, orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs) ⊦ (pcf(tid0) = E10 ∧ success ∨ pcf(tid0) = E11) ∧ node = vs[(orl + qrl).last].next ∧ lst = (orl + qrl).last ∧ vtail = (orl + qrl).last

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: ⊦ weak?(Weak(tid)); (s)

Proof step 12 from proof DMSQInv-atDoEnq (previous step) (back to tree)

vs[vs[(orl + qrl).last].next].deqID = None, vs[vs[(orl + qrl).last].next].next = null, ps[vs[(orl + qrl).last].next] = vs[vs[(orl + qrl).last].next], dom vrvHp = dom prvHp, lsf(tid0) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), owns(vs[(orl + qrl).last].next) = Weak(tid0), vs[(orl + qrl).last].next ≠ null, orl ≠ [], allocrv(pretRefs, prvHp), allocrv(vretRefs, vrvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, vs), markedp(orl, ps), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), rvownerok(pretRefs, prvHp, rvowns), rvownerok(vretRefs, vrvHp, rvowns), unmarkedp(qrl, ps), phead ∈ orl, vs[(orl + qrl).last].next ∈ ps, vs[(orl + qrl).last].next ∈ vs, 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), ∀ tid. lsf(tid).tid = tid ∧ DMSQLInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf(tid), pcf(tid)), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null, orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs) ⊦ (pcf(tid0) = E10 ∧ success ∨ pcf(tid0) = E11) ∧ node = vs[(orl + qrl).last].next ∧ lst = (orl + qrl).last ∧ vtail = (orl + qrl).last

User applied rule all left

And obtained the following new goals

Rule argument

pos: left 27 terms: tid0 abort: F discard: F computed: F

Additional information

Used terms: tid0

Proof step 13 from proof DMSQInv-atDoEnq (previous step) (back to tree)

vs[vs[(orl + qrl).last].next].deqID = None, vs[vs[(orl + qrl).last].next].next = null, lsf(tid0).tid = tid0, ps[vs[(orl + qrl).last].next] = vs[vs[(orl + qrl).last].next], dom vrvHp = dom prvHp, lsf(tid0) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), owns(vs[(orl + qrl).last].next) = Weak(tid0), vs[(orl + qrl).last].next ≠ null, orl ≠ [], DMSQLInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf(tid0), pcf(tid0)), allocrv(vretRefs, vrvHp), allocrv(pretRefs, prvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, ps), markedp(orl, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), rvownerok(vretRefs, vrvHp, rvowns), rvownerok(pretRefs, prvHp, rvowns), unmarkedp(qrl, ps), phead ∈ ps, phead ∈ vs, vs[(orl + qrl).last].next ∈ vs, vs[(orl + qrl).last].next ∈ ps, 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), ∀ tid. lsf(tid).tid = tid ∧ DMSQLInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf(tid), pcf(tid)), orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null ⊦ (pcf(tid0) = E10 ∧ success ∨ pcf(tid0) = E11) ∧ node = vs[(orl + qrl).last].next ∧ lst = (orl + qrl).last ∧ vtail = (orl + qrl).last

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: ⊦ mkls (tid, value, optval, node, nd, success, node0, node1, rvref, optval0, node2, tid0, rvref0) .tid = tid; (s)

Proof step 14 from proof DMSQInv-atDoEnq (previous step) (back to tree)

vs[vs[(orl + qrl).last].next].deqID = None, vs[vs[(orl + qrl).last].next].next = null, ps[vs[(orl + qrl).last].next] = vs[vs[(orl + qrl).last].next], dom vrvHp = dom prvHp, lsf(tid) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), owns(vs[(orl + qrl).last].next) = Weak(tid), vs[(orl + qrl).last].next ≠ null, orl ≠ [], DMSQLInv (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), pcf(tid)), allocrv(vretRefs, vrvHp), allocrv(pretRefs, prvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, ps), markedp(orl, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), rvownerok(vretRefs, vrvHp, rvowns), rvownerok(pretRefs, prvHp, rvowns), unmarkedp(qrl, ps), phead ∈ ps, phead ∈ vs, vs[(orl + qrl).last].next ∈ vs, vs[(orl + qrl).last].next ∈ ps, phead ∈ orl, ¬ 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), ∀ tid. lsf(tid).tid = tid ∧ DMSQLInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf(tid), pcf(tid)), orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null ⊦ (pcf(tid) = E10 ∧ success ∨ pcf(tid) = E11) ∧ node = vs[(orl + qrl).last].next ∧ lst = (orl + qrl).last ∧ vtail = (orl + qrl).last

User applied rule apply rewrite lemma

And obtained the following new goals

Rule argument

spec: DMSQ, name:DMSQLInv, seq:⊦ DMSQLInv(gs, ls, pc) ↔ ( pc = D3 → gs.rvowns(ls.rvref) = Pending(ls.tid) ∧ ls.rvref ∈ gs.vrvHp ∧ ls.rvref ∈ gs.prvHp ∧ ls.rvref ≠ null) ∧ ( pc = D4 → gs.vretRefs(ls.tid) = ls.rvref ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid) ∧ ls.rvref ∈ gs.vrvHp ∧ ls.rvref ∈ gs.prvHp ∧ ls.rvref ≠ null) ∧ (pc = D5 → gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid)) ∧ ( pc = D6 → ( ls.success → ls.optval = gs.vrvHp[ls.rvref] ∧ ls.optval = gs.prvHp[ls.rvref]) ∧ gs.rvowns(gs.vretRefs(ls.tid)) = (ls.optval = Empty ∨ ¬ ls.success ⊃ Pending(ls.tid) ;Claimed(ls.tid, ls.optval.val) )) ∧ (pc = D8 → gs.vtail ∈ gs.orl + gs.qrl from ls.first) ∧ (pc = D9 → gs.vtail ∈ gs.orl + gs.qrl from ls.lst) ∧ ( pc = D10 → gs.vtail ∈ gs.orl + gs.qrl from ls.lst ∧ (ls.nxt ≠ null → ls.nxt = gs.vs[ls.first].next) ∧ ( ls.first ≠ ls.lst → ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next)) ∧ ( pc = D11 → gs.vtail ∈ gs.orl + gs.qrl from ls.lst ∧ ls.lst ∈ gs.orl + gs.qrl ∧ (ls.nxt ≠ null → ls.nxt = gs.vs[ls.first].next) ∧ ( ls.first ≠ ls.lst → ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next)) ∧ ( pc = D12 → ls.lst ∈ gs.orl + gs.qrl ∧ (ls.nxt ≠ null → ls.nxt = gs.vs[ls.lst].next)) ∧ (pc = D13 → ls.lst ∈ gs.orl + gs.qrl ∧ ls.nxt = null) ∧ ( pc = D14 → ls.lst ∈ gs.orl + gs.qrl ∧ gs.vrvHp[ls.rvref] = Empty ∧ ls.nxt = null) ∧ ( pc = D15 → ls.lst ∈ gs.orl + gs.qrl ∧ gs.vrvHp[ls.rvref] = Empty ∧ gs.prvHp[ls.rvref] = Empty) ∧ ( pc = D16 → ls.lst ∈ gs.orl + gs.qrl ∧ ls.nxt = gs.vs[ls.lst].next ∧ ls.nxt ≠ null) ∧ ( pc = D17 → ls.lst ∈ gs.orl + gs.qrl ∧ ls.nxt = gs.ps[ls.lst].next ∧ ls.nxt = gs.vs[ls.lst].next ∧ ls.nxt ≠ null) ∧ (pc = D18 → ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next) ∧ ( pc = D19 → ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ ls.optval = Val(gs.vs[ls.nxt].val)) ∧ ( pc = D20 → ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ ls.optval = Val(gs.vs[ls.nxt].val) ∧ ( gs.qrl ≠ [] ∧ gs.vs[gs.qrl.head].deqID = Some(ls.tid) → gs.vhead = ls.first ∧ ls.success) ∧ (ls.success ⊃ gs.vs[ls.nxt].deqID = Some(ls.tid) ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Claimed(ls.tid, ls.optval.val) ∧ (gs.ps[ls.nxt].deqID = None → gs.vhead = ls.first) ∧ noid(ls.tid, gs.orl + gs.qrl, ls.nxt, gs.vs) ; gs.vs[ls.nxt].deqID ≠ None ∧ noid(ls.tid, gs.orl + gs.qrl, ls.first, gs.vs) ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid) )) ∧ ( pc = D21 → ls.nxt ≠ null ∧ ls.first ∈ gs.orl ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.vs[ls.nxt].deqID = Some(ls.tid) ∧ (gs.ps[ls.nxt].deqID = None → gs.vhead = ls.first) ∧ noid(ls.tid, gs.orl + gs.qrl, ls.nxt, gs.vs) ∧ ( gs.qrl ≠ [] ∧ gs.vs[gs.qrl.head].deqID = Some(ls.tid) → gs.vhead = ls.first)) ∧ ( pc = D22 → gs.ps[ls.nxt].deqID ≠ None ∧ ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next) ∧ ( pc = D23 → gs.ps[ls.nxt].deqID ≠ None ∧ ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ ls.optval = gs.vrvHp[ls.rvref]) ∧ ( pc = D24 → gs.ps[ls.nxt].deqID ≠ None ∧ ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ ls.optval = gs.vrvHp[ls.rvref] ∧ ls.optval = gs.prvHp[ls.rvref]) ∧ ( pc = D25 → ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.vs[ls.nxt].deqID ≠ None ∧ ls.optval = Val(gs.vs[ls.nxt].val) ∧ ( gs.vhead = ls.first → gs.rvowns(gs.vretRefs((gs.ps ⊕ gs.vs)[ls.nxt].deqID.tid)) = Claimed((gs.ps ⊕ gs.vs)[ls.nxt].deqID.tid, ls.optval.val))) ∧ ( pc = D26 → ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.vs[ls.nxt].deqID ≠ None ∧ gs.vs[ls.nxt].deqID = Some(ls.othertid) ∧ ls.optval = Val(gs.vs[ls.nxt].val) ∧ ( gs.vhead = ls.first → gs.rvowns(gs.vretRefs(ls.othertid)) = Claimed(ls.othertid, ls.optval.val))) ∧ ( pc = D27 → ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.vs[ls.nxt].deqID = Some(ls.othertid) ∧ ( gs.vhead = ls.first → gs.rvowns(ls.addr) = Claimed(ls.othertid, ls.optval.val))) ∧ ( pc = D28 → ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.vs[ls.nxt].deqID = Some(ls.othertid) ∧ gs.rvowns(ls.addr) = Claimed(ls.othertid, ls.optval.val)) ∧ ( pc = D29 → ls.first ∈ gs.orl ∧ gs.ps[ls.nxt].deqID ≠ None ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.rvowns(ls.addr) = Claimed(ls.othertid, ls.optval.val)) ∧ ( pc = D30 → ls.first ∈ gs.orl ∧ gs.ps[ls.nxt].deqID ≠ None ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.rvowns(ls.addr) = Claimed(ls.othertid, ls.optval.val)) ∧ ( pc = D31 → ls.first ∈ gs.orl ∧ gs.ps[ls.nxt].deqID ≠ None ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next) ∧ ( pc = D34 → ls.optval = gs.vrvHp[gs.vretRefs(ls.tid)] ∧ ls.optval = gs.prvHp[gs.pretRefs(ls.tid)] ∧ gs.vretRefs(ls.tid) = gs.pretRefs(ls.tid) ∧ gs.vretRefs(ls.tid) ∈ gs.vrvHp ∧ gs.vretRefs(ls.tid) ≠ null ∧ gs.rvowns(gs.vretRefs(ls.tid)) = (ls.optval = Empty ⊃ Pending(ls.tid) ;Claimed(ls.tid, ls.optval.val) )) ∧ (pc = E2 → gs.owns(ls.node) = Some(ls.tid)) ∧ (pc = E3 → gs.owns(ls.node) = Some(ls.tid)) ∧ (pc = E5 → gs.owns(ls.node) = Some(ls.tid)) ∧ ( pc = E6 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.lst ∈ gs.orl + gs.qrl ∧ (gs.ps[ls.lst].next = null → ls.lst = gs.vtail)) ∧ ( pc = E7 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.lst ∈ gs.orl + gs.qrl ∧ (ls.nxt ≠ null → ls.nxt = gs.vs[ls.lst].next) ∧ (gs.vs[ls.lst].next = null → gs.vtail = ls.lst)) ∧ ( pc = E8 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.lst ∈ gs.orl + gs.qrl ∧ (ls.nxt ≠ null → ls.nxt = gs.vs[ls.lst].next) ∧ (gs.vs[ls.lst].next = null → gs.vtail = ls.lst)) ∧ ( pc = E9 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.nxt = null ∧ ls.lst ∈ gs.orl + gs.qrl ∧ (gs.vs[ls.lst].next = null → gs.vtail = ls.lst)) ∧ ( pc = E10 → ls.success → gs.vs[ls.lst].next = ls.node ∧ ls.node ≠ null ∧ gs.vs[ls.node].val = ls.value ∧ ( ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null ∧ gs.owns(ls.node) = Weak(ls.tid) ∨ ls.lst ∈ gs.orl + gs.qrl ∧ gs.ps[ls.lst].next = ls.node)) ∧ ( pc = E11 → ls.success ∧ gs.vs[ls.lst].next = ls.node ∧ ls.node ≠ null ∧ gs.vs[ls.node].val = ls.value ∧ ( ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null ∧ gs.owns(ls.node) = Weak(ls.tid) ∨ ls.lst ∈ gs.orl + gs.qrl ∧ gs.ps[ls.lst].next = ls.node)) ∧ ( pc = E12 → ls.success ∧ ls.lst ∈ gs.orl + gs.qrl ∧ ls.node ∈ gs.orl + gs.qrl ∧ gs.vs[ls.lst].next = ls.node ∧ gs.ps[ls.lst].next = ls.node ∧ ls.node ∈ gs.ps ∧ ls.node ∈ gs.vs ∧ ls.node ≠ null) ∧ (pc = E13 → gs.owns(ls.node) = Some(ls.tid)) ∧ ( pc = E14 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.lst ∈ gs.orl + gs.qrl ∧ ls.nxt = gs.vs[ls.lst].next ∧ ls.nxt ≠ null) ∧ ( pc = E15 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.lst ∈ gs.orl + gs.qrl ∧ ls.nxt = gs.vs[ls.lst].next ∧ ls.nxt = gs.ps[ls.lst].next ∧ ls.nxt ≠ null) ∧ (pc = E16 → gs.owns(ls.node) = Some(ls.tid)) ∧ ( pc = E2 ∨ pc = E3 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 → ls.node ∈ gs.ps ∧ ls.node ∈ gs.vs ∧ ls.node ≠ null ∧ ¬ ls.node ∈ gs.orl ∧ ¬ ls.node ∈ gs.qrl) ∧ ( pc = E4 ∨ pc = E10 → ¬ ls.success → ¬ ls.node ∈ gs.orl ∧ ¬ ls.node ∈ gs.qrl ∧ ls.node ≠ null ∧ ls.node ∈ gs.ps ∧ ls.node ∈ gs.vs ∧ gs.owns(ls.node) = Some(ls.tid) ∧ gs.vs[ls.node] = mk(ls.value, None, null) ∧ gs.ps[ls.node] = gs.vs[ls.node]) ∧ ( pc = E3 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 → gs.vs[ls.node] = mk(ls.value, None, null)) ∧ ( pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 → gs.ps[ls.node] = gs.vs[ls.node]) ∧ ( pc = D7 ∨ pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D16 ∨ pc = D17 ∨ pc = D18 ∨ pc = D19 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32 ∨ pc = D33 → ¬ ls.success ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid)) ∧ ( pc = D13 ∨ pc = D14 ∨ pc = D15 → ¬ ls.success ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid)) ∧ ( pc = E2 ∨ pc = E3 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 → ¬ ls.success) ∧ ( pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D15 ∨ pc = D18 ∨ pc = D19 ∨ pc = D20 → ls.first ∈ gs.orl ∧ gs.vhead ∈ gs.orl from ls.first) ∧ ( pc = D18 ∨ pc = D19 ∨ pc = D20 ∨ pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 → ls.first ≠ ls.lst ∧ gs.vtail ∈ gs.orl + gs.qrl from ls.lst) ∧ ( pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D18 ∨ pc = D19 ∨ pc = D20 ∨ pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 → ls.lst ∈ gs.orl + gs.qrl from ls.first) ∧ ( pc = D5 ∨ pc = D6 ∨ pc = D7 ∨ pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D15 ∨ pc = D16 ∨ pc = D17 ∨ pc = D18 ∨ pc = D19 ∨ pc = D20 ∨ pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32 ∨ pc = D33 → gs.vretRefs(ls.tid) = ls.rvref ∧ gs.pretRefs(ls.tid) = ls.rvref ∧ ls.rvref ∈ gs.vrvHp ∧ ls.rvref ≠ null) ∧ ( pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 → ls.success ∧ gs.vretRefs(ls.tid) ∈ gs.vrvHp ∧ gs.vretRefs(ls.tid) ≠ null ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Claimed(ls.tid, ls.optval.val) ∧ ls.optval = Val(gs.vs[ls.nxt].val)) ∧ ( pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 → ls.addr ∈ gs.vrvHp ∧ ls.addr ≠ null ∧ ls.optval = Val(gs.vs[ls.nxt].val)) ∧ ( pc = idle ∨ pc = ready ∨ pc = E1 ∨ pc = E2 ∨ pc = E3 ∨ pc = E4 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E10 ∨ pc = E11 ∨ pc = E12 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 ∨ pc = E17 ∨ pc = D1 ∨ pc = D2 ∨ pc = D3 ∨ pc = D4 ∨ pc = D5 ∨ pc = D6 ∨ pc = D7 ∨ pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D15 ∨ pc = D16 ∨ pc = D17 ∨ pc = D18 ∨ pc = D19 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32 ∨ pc = D33 ∨ pc = D34 → nextnottid(ls.tid, gs.vhead, gs.vs)) ∧ ( pc = D20 ∨ pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 → gs.vhead ≠ ls.first → nextnottid(ls.tid, gs.vhead, gs.vs)) ∧ ( pc = crashed ∨ pc = idle ∨ pc = ready ∨ pc = E1 ∨ pc = E2 ∨ pc = E3 ∨ pc = E4 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E10 ∨ pc = E11 ∨ pc = E12 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 ∨ pc = E17 ∨ pc = D1 ∨ pc = D2 ∨ pc = D3 ∨ pc = D4 ∨ pc = D5 ∨ pc = D6 ∨ pc = D7 ∨ pc = D16 ∨ pc = D17 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32 ∨ pc = D33 ∨ pc = D34 → noid(ls.tid, gs.orl + gs.qrl, gs.vhead, gs.vs)) ∧ ( pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D15 ∨ pc = D18 ∨ pc = D19 → noid(ls.tid, gs.orl + gs.qrl, ls.first, gs.vs)) ∧ ( pc = D22 ∨ pc = D23 ∨ pc = D24 → noid(ls.tid, gs.orl + gs.qrl, ls.nxt, gs.vs)) ∧ ( pc = crashed ∨ pc = idle ∨ pc = ready ∨ pc = D1 ∨ pc = D2 ∨ pc = D3 ∨ pc = D4 ∨ pc = D5 ∨ pc = D6 ∨ pc = D7 ∨ pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D15 ∨ pc = D16 ∨ pc = D17 ∨ pc = D18 ∨ pc = D19 ∨ pc = D20 ∨ pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32 ∨ pc = D33 ∨ pc = D34 ∨ pc = E1 ∨ pc = E12 ∨ pc = E17 → noowns(ls.tid, gs.owns)) ∧ ( pc = E2 ∨ pc = E3 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 → oneowns(ls.tid, ls.node, gs.owns, gs.vs, gs.ps)) ∧ ( pc = E10 → (ls.success ⊃ (gs.ps[ls.lst].next ≠ gs.vs[ls.lst].next ⊃ oneweakowns(ls.tid, ls.node, gs.owns, gs.vs, gs.ps) ;noowns(ls.tid, gs.owns) ) ;oneowns(ls.tid, ls.node, gs.owns, gs.vs, gs.ps) )) ∧ ( pc = E11 → (gs.ps[ls.lst].next ≠ gs.vs[ls.lst].next ⊃ oneweakowns(ls.tid, ls.node, gs.owns, gs.vs, gs.ps) ;noowns(ls.tid, gs.owns) )) ∧ ( pc = E4 → (ls.success ⊃ noowns(ls.tid, gs.owns) ;oneowns(ls.tid, ls.node, gs.owns, gs.vs, gs.ps) )), subst:[gs, ls, pc] → [mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), mkls (tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), pcf(tid)], <all paths>

Additional information

Used terms: mkgs (ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), mkls (tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), pcf(tid)

Proof step 15 from proof DMSQInv-atDoEnq (previous step) (back to tree)

⊦ DMSQLInv(gs, ls, pc) ↔ (pc = D3 → gs.rvowns(ls.rvref) = Pending(ls.tid) ∧ ls.rvref ∈ gs.vrvHp ∧ ls.rvref ∈ gs.prvHp ∧ ls.rvref ≠ null) ∧ ( pc = D4 → gs.vretRefs(ls.tid) = ls.rvref ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid) ∧ ls.rvref ∈ gs.vrvHp ∧ ls.rvref ∈ gs.prvHp ∧ ls.rvref ≠ null) ∧ (pc = D5 → gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid)) ∧ ( pc = D6 → (ls.success → ls.optval = gs.vrvHp[ls.rvref] ∧ ls.optval = gs.prvHp[ls.rvref]) ∧ gs.rvowns(gs.vretRefs(ls.tid)) = (ls.optval = Empty ∨ ¬ ls.success ⊃ Pending(ls.tid);Claimed(ls.tid, ls.optval.val))) ∧ (pc = D8 → gs.vtail ∈ gs.orl + gs.qrl from ls.first) ∧ (pc = D9 → gs.vtail ∈ gs.orl + gs.qrl from ls.lst) ∧ ( pc = D10 → gs.vtail ∈ gs.orl + gs.qrl from ls.lst ∧ (ls.nxt ≠ null → ls.nxt = gs.vs[ls.first].next) ∧ (ls.first ≠ ls.lst → ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next)) ∧ ( pc = D11 → gs.vtail ∈ gs.orl + gs.qrl from ls.lst ∧ ls.lst ∈ gs.orl + gs.qrl ∧ (ls.nxt ≠ null → ls.nxt = gs.vs[ls.first].next) ∧ (ls.first ≠ ls.lst → ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next)) ∧ (pc = D12 → ls.lst ∈ gs.orl + gs.qrl ∧ (ls.nxt ≠ null → ls.nxt = gs.vs[ls.lst].next)) ∧ (pc = D13 → ls.lst ∈ gs.orl + gs.qrl ∧ ls.nxt = null) ∧ (pc = D14 → ls.lst ∈ gs.orl + gs.qrl ∧ gs.vrvHp[ls.rvref] = Empty ∧ ls.nxt = null) ∧ (pc = D15 → ls.lst ∈ gs.orl + gs.qrl ∧ gs.vrvHp[ls.rvref] = Empty ∧ gs.prvHp[ls.rvref] = Empty) ∧ (pc = D16 → ls.lst ∈ gs.orl + gs.qrl ∧ ls.nxt = gs.vs[ls.lst].next ∧ ls.nxt ≠ null) ∧ (pc = D17 → ls.lst ∈ gs.orl + gs.qrl ∧ ls.nxt = gs.ps[ls.lst].next ∧ ls.nxt = gs.vs[ls.lst].next ∧ ls.nxt ≠ null) ∧ (pc = D18 → ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next) ∧ (pc = D19 → ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ ls.optval = Val(gs.vs[ls.nxt].val)) ∧ ( pc = D20 → ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ ls.optval = Val(gs.vs[ls.nxt].val) ∧ (gs.qrl ≠ [] ∧ gs.vs[gs.qrl.head].deqID = Some(ls.tid) → gs.vhead = ls.first ∧ ls.success) ∧ (ls.success ⊃ gs.vs[ls.nxt].deqID = Some(ls.tid) ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Claimed(ls.tid, ls.optval.val) ∧ (gs.ps[ls.nxt].deqID = None → gs.vhead = ls.first) ∧ noid(ls.tid, gs.orl + gs.qrl, ls.nxt, gs.vs) ;gs.vs[ls.nxt].deqID ≠ None ∧ noid(ls.tid, gs.orl + gs.qrl, ls.first, gs.vs) ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid) )) ∧ ( pc = D21 → ls.nxt ≠ null ∧ ls.first ∈ gs.orl ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.vs[ls.nxt].deqID = Some(ls.tid) ∧ (gs.ps[ls.nxt].deqID = None → gs.vhead = ls.first) ∧ noid(ls.tid, gs.orl + gs.qrl, ls.nxt, gs.vs) ∧ (gs.qrl ≠ [] ∧ gs.vs[gs.qrl.head].deqID = Some(ls.tid) → gs.vhead = ls.first)) ∧ (pc = D22 → gs.ps[ls.nxt].deqID ≠ None ∧ ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next) ∧ (pc = D23 → gs.ps[ls.nxt].deqID ≠ None ∧ ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ ls.optval = gs.vrvHp[ls.rvref]) ∧ ( pc = D24 → gs.ps[ls.nxt].deqID ≠ None ∧ ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ ls.optval = gs.vrvHp[ls.rvref] ∧ ls.optval = gs.prvHp[ls.rvref]) ∧ ( pc = D25 → ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.vs[ls.nxt].deqID ≠ None ∧ ls.optval = Val(gs.vs[ls.nxt].val) ∧ ( gs.vhead = ls.first → gs.rvowns(gs.vretRefs((gs.ps ⊕ gs.vs)[ls.nxt].deqID.tid)) = Claimed((gs.ps ⊕ gs.vs)[ls.nxt].deqID.tid, ls.optval.val))) ∧ ( pc = D26 → ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.vs[ls.nxt].deqID ≠ None ∧ gs.vs[ls.nxt].deqID = Some(ls.othertid) ∧ ls.optval = Val(gs.vs[ls.nxt].val) ∧ (gs.vhead = ls.first → gs.rvowns(gs.vretRefs(ls.othertid)) = Claimed(ls.othertid, ls.optval.val))) ∧ ( pc = D27 → ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.vs[ls.nxt].deqID = Some(ls.othertid) ∧ (gs.vhead = ls.first → gs.rvowns(ls.addr) = Claimed(ls.othertid, ls.optval.val))) ∧ ( pc = D28 → ls.first ∈ gs.orl ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.vs[ls.nxt].deqID = Some(ls.othertid) ∧ gs.rvowns(ls.addr) = Claimed(ls.othertid, ls.optval.val)) ∧ ( pc = D29 → ls.first ∈ gs.orl ∧ gs.ps[ls.nxt].deqID ≠ None ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.rvowns(ls.addr) = Claimed(ls.othertid, ls.optval.val)) ∧ ( pc = D30 → ls.first ∈ gs.orl ∧ gs.ps[ls.nxt].deqID ≠ None ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next ∧ gs.rvowns(ls.addr) = Claimed(ls.othertid, ls.optval.val)) ∧ (pc = D31 → ls.first ∈ gs.orl ∧ gs.ps[ls.nxt].deqID ≠ None ∧ ls.nxt ≠ null ∧ ls.nxt = gs.ps[ls.first].next) ∧ ( pc = D34 → ls.optval = gs.vrvHp[gs.vretRefs(ls.tid)] ∧ ls.optval = gs.prvHp[gs.pretRefs(ls.tid)] ∧ gs.vretRefs(ls.tid) = gs.pretRefs(ls.tid) ∧ gs.vretRefs(ls.tid) ∈ gs.vrvHp ∧ gs.vretRefs(ls.tid) ≠ null ∧ gs.rvowns(gs.vretRefs(ls.tid)) = (ls.optval = Empty ⊃ Pending(ls.tid);Claimed(ls.tid, ls.optval.val))) ∧ (pc = E2 → gs.owns(ls.node) = Some(ls.tid)) ∧ (pc = E3 → gs.owns(ls.node) = Some(ls.tid)) ∧ (pc = E5 → gs.owns(ls.node) = Some(ls.tid)) ∧ (pc = E6 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.lst ∈ gs.orl + gs.qrl ∧ (gs.ps[ls.lst].next = null → ls.lst = gs.vtail)) ∧ ( pc = E7 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.lst ∈ gs.orl + gs.qrl ∧ (ls.nxt ≠ null → ls.nxt = gs.vs[ls.lst].next) ∧ (gs.vs[ls.lst].next = null → gs.vtail = ls.lst)) ∧ ( pc = E8 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.lst ∈ gs.orl + gs.qrl ∧ (ls.nxt ≠ null → ls.nxt = gs.vs[ls.lst].next) ∧ (gs.vs[ls.lst].next = null → gs.vtail = ls.lst)) ∧ (pc = E9 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.nxt = null ∧ ls.lst ∈ gs.orl + gs.qrl ∧ (gs.vs[ls.lst].next = null → gs.vtail = ls.lst)) ∧ ( pc = E10 → ls.success → gs.vs[ls.lst].next = ls.node ∧ ls.node ≠ null ∧ gs.vs[ls.node].val = ls.value ∧ (ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null ∧ gs.owns(ls.node) = Weak(ls.tid) ∨ ls.lst ∈ gs.orl + gs.qrl ∧ gs.ps[ls.lst].next = ls.node)) ∧ ( pc = E11 → ls.success ∧ gs.vs[ls.lst].next = ls.node ∧ ls.node ≠ null ∧ gs.vs[ls.node].val = ls.value ∧ (ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null ∧ gs.owns(ls.node) = Weak(ls.tid) ∨ ls.lst ∈ gs.orl + gs.qrl ∧ gs.ps[ls.lst].next = ls.node)) ∧ ( pc = E12 → ls.success ∧ ls.lst ∈ gs.orl + gs.qrl ∧ ls.node ∈ gs.orl + gs.qrl ∧ gs.vs[ls.lst].next = ls.node ∧ gs.ps[ls.lst].next = ls.node ∧ ls.node ∈ gs.ps ∧ ls.node ∈ gs.vs ∧ ls.node ≠ null) ∧ (pc = E13 → gs.owns(ls.node) = Some(ls.tid)) ∧ (pc = E14 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.lst ∈ gs.orl + gs.qrl ∧ ls.nxt = gs.vs[ls.lst].next ∧ ls.nxt ≠ null) ∧ ( pc = E15 → gs.owns(ls.node) = Some(ls.tid) ∧ ls.lst ∈ gs.orl + gs.qrl ∧ ls.nxt = gs.vs[ls.lst].next ∧ ls.nxt = gs.ps[ls.lst].next ∧ ls.nxt ≠ null) ∧ (pc = E16 → gs.owns(ls.node) = Some(ls.tid)) ∧ ( pc = E2 ∨ pc = E3 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 → ls.node ∈ gs.ps ∧ ls.node ∈ gs.vs ∧ ls.node ≠ null ∧ ¬ ls.node ∈ gs.orl ∧ ¬ ls.node ∈ gs.qrl) ∧ ( pc = E4 ∨ pc = E10 → ¬ ls.success → ¬ ls.node ∈ gs.orl ∧ ¬ ls.node ∈ gs.qrl ∧ ls.node ≠ null ∧ ls.node ∈ gs.ps ∧ ls.node ∈ gs.vs ∧ gs.owns(ls.node) = Some(ls.tid) ∧ gs.vs[ls.node] = mk(ls.value, None, null) ∧ gs.ps[ls.node] = gs.vs[ls.node]) ∧ ( pc = E3 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 → gs.vs[ls.node] = mk(ls.value, None, null)) ∧ (pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 → gs.ps[ls.node] = gs.vs[ls.node]) ∧ ( pc = D7 ∨ pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D16 ∨ pc = D17 ∨ pc = D18 ∨ pc = D19 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32 ∨ pc = D33 → ¬ ls.success ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid)) ∧ (pc = D13 ∨ pc = D14 ∨ pc = D15 → ¬ ls.success ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Pending(ls.tid)) ∧ (pc = E2 ∨ pc = E3 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 → ¬ ls.success) ∧ ( pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D15 ∨ pc = D18 ∨ pc = D19 ∨ pc = D20 → ls.first ∈ gs.orl ∧ gs.vhead ∈ gs.orl from ls.first) ∧ ( pc = D18 ∨ pc = D19 ∨ pc = D20 ∨ pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 → ls.first ≠ ls.lst ∧ gs.vtail ∈ gs.orl + gs.qrl from ls.lst) ∧ ( pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D18 ∨ pc = D19 ∨ pc = D20 ∨ pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 → ls.lst ∈ gs.orl + gs.qrl from ls.first) ∧ ( pc = D5 ∨ pc = D6 ∨ pc = D7 ∨ pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D15 ∨ pc = D16 ∨ pc = D17 ∨ pc = D18 ∨ pc = D19 ∨ pc = D20 ∨ pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32 ∨ pc = D33 → gs.vretRefs(ls.tid) = ls.rvref ∧ gs.pretRefs(ls.tid) = ls.rvref ∧ ls.rvref ∈ gs.vrvHp ∧ ls.rvref ≠ null) ∧ ( pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 → ls.success ∧ gs.vretRefs(ls.tid) ∈ gs.vrvHp ∧ gs.vretRefs(ls.tid) ≠ null ∧ gs.rvowns(gs.vretRefs(ls.tid)) = Claimed(ls.tid, ls.optval.val) ∧ ls.optval = Val(gs.vs[ls.nxt].val)) ∧ (pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 → ls.addr ∈ gs.vrvHp ∧ ls.addr ≠ null ∧ ls.optval = Val(gs.vs[ls.nxt].val)) ∧ ( pc = idle ∨ pc = ready ∨ pc = E1 ∨ pc = E2 ∨ pc = E3 ∨ pc = E4 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E10 ∨ pc = E11 ∨ pc = E12 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 ∨ pc = E17 ∨ pc = D1 ∨ pc = D2 ∨ pc = D3 ∨ pc = D4 ∨ pc = D5 ∨ pc = D6 ∨ pc = D7 ∨ pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D15 ∨ pc = D16 ∨ pc = D17 ∨ pc = D18 ∨ pc = D19 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32 ∨ pc = D33 ∨ pc = D34 → nextnottid(ls.tid, gs.vhead, gs.vs)) ∧ (pc = D20 ∨ pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 → gs.vhead ≠ ls.first → nextnottid(ls.tid, gs.vhead, gs.vs)) ∧ ( pc = crashed ∨ pc = idle ∨ pc = ready ∨ pc = E1 ∨ pc = E2 ∨ pc = E3 ∨ pc = E4 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E10 ∨ pc = E11 ∨ pc = E12 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 ∨ pc = E17 ∨ pc = D1 ∨ pc = D2 ∨ pc = D3 ∨ pc = D4 ∨ pc = D5 ∨ pc = D6 ∨ pc = D7 ∨ pc = D16 ∨ pc = D17 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32 ∨ pc = D33 ∨ pc = D34 → noid(ls.tid, gs.orl + gs.qrl, gs.vhead, gs.vs)) ∧ ( pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D15 ∨ pc = D18 ∨ pc = D19 → noid(ls.tid, gs.orl + gs.qrl, ls.first, gs.vs)) ∧ (pc = D22 ∨ pc = D23 ∨ pc = D24 → noid(ls.tid, gs.orl + gs.qrl, ls.nxt, gs.vs)) ∧ ( pc = crashed ∨ pc = idle ∨ pc = ready ∨ pc = D1 ∨ pc = D2 ∨ pc = D3 ∨ pc = D4 ∨ pc = D5 ∨ pc = D6 ∨ pc = D7 ∨ pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D15 ∨ pc = D16 ∨ pc = D17 ∨ pc = D18 ∨ pc = D19 ∨ pc = D20 ∨ pc = D21 ∨ pc = D22 ∨ pc = D23 ∨ pc = D24 ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32 ∨ pc = D33 ∨ pc = D34 ∨ pc = E1 ∨ pc = E12 ∨ pc = E17 → noowns(ls.tid, gs.owns)) ∧ ( pc = E2 ∨ pc = E3 ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9 ∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16 → oneowns(ls.tid, ls.node, gs.owns, gs.vs, gs.ps)) ∧ ( pc = E10 → (ls.success ⊃ (gs.ps[ls.lst].next ≠ gs.vs[ls.lst].next ⊃ oneweakowns(ls.tid, ls.node, gs.owns, gs.vs, gs.ps);noowns(ls.tid, gs.owns)) ;oneowns(ls.tid, ls.node, gs.owns, gs.vs, gs.ps) )) ∧ (pc = E11 → (gs.ps[ls.lst].next ≠ gs.vs[ls.lst].next ⊃ oneweakowns(ls.tid, ls.node, gs.owns, gs.vs, gs.ps);noowns(ls.tid, gs.owns))) ∧ (pc = E4 → (ls.success ⊃ noowns(ls.tid, gs.owns);oneowns(ls.tid, ls.node, gs.owns, gs.vs, gs.ps)))

A spec-lemma

Proof step 16 from proof DMSQInv-atDoEnq (previous step) (back to tree)

vs[vs[(orl + qrl).last].next].deqID = None, vs[vs[(orl + qrl).last].next].next = null, ps[vs[(orl + qrl).last].next] = vs[vs[(orl + qrl).last].next], dom vrvHp = dom prvHp, lsf(tid) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), owns(vs[(orl + qrl).last].next) = Weak(tid), vs[(orl + qrl).last].next ≠ null, orl ≠ [], allocrv(pretRefs, prvHp), allocrv(vretRefs, vrvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, vs), markedp(orl, ps), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), rvownerok(pretRefs, prvHp, rvowns), rvownerok(vretRefs, vrvHp, rvowns), unmarkedp(qrl, ps), phead ∈ orl, vs[(orl + qrl).last].next ∈ ps, vs[(orl + qrl).last].next ∈ vs, phead ∈ vs, phead ∈ ps, ¬ 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), pcf(tid) = D3 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref) = Pending(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).prvHp ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ≠ null, pcf(tid) = D4 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid)) = Pending(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).prvHp ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ≠ null, pcf(tid) = D5 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid)) = Pending(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid), pcf(tid) = D6 → ( mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ] ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).prvHp [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ]) ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid)) = ( mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = Empty ∨ ¬ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success ⊃ Pending(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ;Claimed (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval.val) ), pcf(tid) = D8 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vtail ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl from mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first, pcf(tid) = D9 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vtail ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl from mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst, pcf(tid) = D10 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vtail ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl from mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∧ ( mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next) ∧ ( mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ≠ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next), pcf(tid) = D11 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vtail ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl from mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ ( mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next) ∧ ( mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ≠ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next), pcf(tid) = D12 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ ( mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next), pcf(tid) = D13 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = null, pcf(tid) = D14 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ] = Empty ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = null, pcf(tid) = D15 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ] = Empty ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).prvHp [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ] = Empty, pcf(tid) = D16 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null, pcf(tid) = D17 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null, pcf(tid) = D18 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next, pcf(tid) = D19 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = Val (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .val), pcf(tid) = D20 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = Val (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .val) ∧ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ≠ [] ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl.head ] .deqID = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success) ∧ (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success ⊃ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid)) = Claimed (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval.val) ∧ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID = None → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first) ∧ noid (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs) ; mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID ≠ None ∧ noid (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs) ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid)) = Pending(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ), pcf(tid) = D21 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID = None → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first) ∧ noid (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs) ∧ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ≠ [] ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl.head ] .deqID = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first), pcf(tid) = D22 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID ≠ None ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next, pcf(tid) = D23 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID ≠ None ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ], pcf(tid) = D24 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID ≠ None ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ] ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).prvHp [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ], pcf(tid) = D25 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID ≠ None ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = Val (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .val) ∧ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps ⊕ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs )[mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID .tid)) = Claimed (( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps ⊕ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs )[mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID .tid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval.val)), pcf(tid) = D26 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID ≠ None ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).othertid) ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = Val (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .val) ∧ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).othertid)) = Claimed (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).othertid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval.val)), pcf(tid) = D27 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).othertid) ∧ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).addr) = Claimed (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).othertid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval.val)), pcf(tid) = D28 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).othertid) ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).addr) = Claimed (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).othertid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval.val), pcf(tid) = D29 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID ≠ None ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).addr) = Claimed (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).othertid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval.val), pcf(tid) = D30 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID ≠ None ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).addr) = Claimed (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).othertid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval.val), pcf(tid) = D31 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .deqID ≠ None ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ] .next, pcf(tid) = D34 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp [mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ] ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).prvHp [mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).pretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ] ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).pretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ≠ null ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid)) = (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = Empty ⊃ Pending(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ;Claimed (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval.val) ), pcf(tid) = E2 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid), pcf(tid) = E3 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid), pcf(tid) = E5 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid), pcf(tid) = E6 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = null → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vtail), pcf(tid) = E7 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ ( mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next) ∧ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = null → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vtail = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst), pcf(tid) = E8 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ ( mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next) ∧ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = null → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vtail = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst), pcf(tid) = E9 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = null → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vtail = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst), pcf(tid) = E10 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ≠ null ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ] .val = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).value ∧ ( mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vtail ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = null ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Weak(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∨ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node), pcf(tid) = E11 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ≠ null ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ] .val = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).value ∧ ( mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vtail ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = null ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Weak(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∨ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node), pcf(tid) = E12 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ≠ null, pcf(tid) = E13 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid), pcf(tid) = E14 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null, pcf(tid) = E15 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ≠ null, pcf(tid) = E16 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid), pcf(tid) = E2 ∨ pcf(tid) = E3 ∨ pcf(tid) = E5 ∨ pcf(tid) = E6 ∨ pcf(tid) = E7 ∨ pcf(tid) = E8 ∨ pcf(tid) = E9 ∨ pcf(tid) = E13 ∨ pcf(tid) = E14 ∨ pcf(tid) = E15 ∨ pcf(tid) = E16 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ≠ null ∧ ¬ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ ¬ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl, pcf(tid) = E4 ∨ pcf(tid) = E10 → ¬ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success → ¬ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ ¬ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node) = Some(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ] = mk(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).value, None, null) ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ] = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ], pcf(tid) = E3 ∨ pcf(tid) = E5 ∨ pcf(tid) = E6 ∨ pcf(tid) = E7 ∨ pcf(tid) = E8 ∨ pcf(tid) = E9 ∨ pcf(tid) = E13 ∨ pcf(tid) = E14 ∨ pcf(tid) = E15 ∨ pcf(tid) = E16 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ] = mk(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).value, None, null), pcf(tid) = E5 ∨ pcf(tid) = E6 ∨ pcf(tid) = E7 ∨ pcf(tid) = E8 ∨ pcf(tid) = E9 ∨ pcf(tid) = E13 ∨ pcf(tid) = E14 ∨ pcf(tid) = E15 ∨ pcf(tid) = E16 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ] = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node ], pcf(tid) = D7 ∨ pcf(tid) = D8 ∨ pcf(tid) = D9 ∨ pcf(tid) = D10 ∨ pcf(tid) = D11 ∨ pcf(tid) = D12 ∨ pcf(tid) = D16 ∨ pcf(tid) = D17 ∨ pcf(tid) = D18 ∨ pcf(tid) = D19 ∨ pcf(tid) = D25 ∨ pcf(tid) = D26 ∨ pcf(tid) = D27 ∨ pcf(tid) = D28 ∨ pcf(tid) = D29 ∨ pcf(tid) = D30 ∨ pcf(tid) = D31 ∨ pcf(tid) = D32 ∨ pcf(tid) = D33 → ¬ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid)) = Pending(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid), pcf(tid) = D13 ∨ pcf(tid) = D14 ∨ pcf(tid) = D15 → ¬ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid)) = Pending(mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid), pcf(tid) = E2 ∨ pcf(tid) = E3 ∨ pcf(tid) = E5 ∨ pcf(tid) = E6 ∨ pcf(tid) = E7 ∨ pcf(tid) = E8 ∨ pcf(tid) = E9 ∨ pcf(tid) = E13 ∨ pcf(tid) = E14 ∨ pcf(tid) = E15 ∨ pcf(tid) = E16 → ¬ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success, pcf(tid) = D8 ∨ pcf(tid) = D9 ∨ pcf(tid) = D10 ∨ pcf(tid) = D11 ∨ pcf(tid) = D12 ∨ pcf(tid) = D13 ∨ pcf(tid) = D14 ∨ pcf(tid) = D15 ∨ pcf(tid) = D18 ∨ pcf(tid) = D19 ∨ pcf(tid) = D20 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl from mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first, pcf(tid) = D18 ∨ pcf(tid) = D19 ∨ pcf(tid) = D20 ∨ pcf(tid) = D21 ∨ pcf(tid) = D22 ∨ pcf(tid) = D23 ∨ pcf(tid) = D24 ∨ pcf(tid) = D25 ∨ pcf(tid) = D26 ∨ pcf(tid) = D27 ∨ pcf(tid) = D28 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first ≠ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vtail ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl from mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst, pcf(tid) = D9 ∨ pcf(tid) = D10 ∨ pcf(tid) = D11 ∨ pcf(tid) = D18 ∨ pcf(tid) = D19 ∨ pcf(tid) = D20 ∨ pcf(tid) = D21 ∨ pcf(tid) = D22 ∨ pcf(tid) = D23 ∨ pcf(tid) = D24 ∨ pcf(tid) = D25 ∨ pcf(tid) = D26 ∨ pcf(tid) = D27 ∨ pcf(tid) = D28 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl from mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first, pcf(tid) = D5 ∨ pcf(tid) = D6 ∨ pcf(tid) = D7 ∨ pcf(tid) = D8 ∨ pcf(tid) = D9 ∨ pcf(tid) = D10 ∨ pcf(tid) = D11 ∨ pcf(tid) = D12 ∨ pcf(tid) = D13 ∨ pcf(tid) = D14 ∨ pcf(tid) = D15 ∨ pcf(tid) = D16 ∨ pcf(tid) = D17 ∨ pcf(tid) = D18 ∨ pcf(tid) = D19 ∨ pcf(tid) = D20 ∨ pcf(tid) = D21 ∨ pcf(tid) = D22 ∨ pcf(tid) = D23 ∨ pcf(tid) = D24 ∨ pcf(tid) = D25 ∨ pcf(tid) = D26 ∨ pcf(tid) = D27 ∨ pcf(tid) = D28 ∨ pcf(tid) = D29 ∨ pcf(tid) = D30 ∨ pcf(tid) = D31 ∨ pcf(tid) = D32 ∨ pcf(tid) = D33 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).pretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).rvref ≠ null, pcf(tid) = D21 ∨ pcf(tid) = D22 ∨ pcf(tid) = D23 ∨ pcf(tid) = D24 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid) ≠ null ∧ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).rvowns (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vretRefs (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid)) = Claimed (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval.val) ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = Val (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .val), pcf(tid) = D27 ∨ pcf(tid) = D28 ∨ pcf(tid) = D29 ∨ pcf(tid) = D30 → mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).addr ∈ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vrvHp ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).addr ≠ null ∧ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).optval = Val (mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt ] .val), pcf(tid) = idle ∨ pcf(tid) = ready ∨ pcf(tid) = E1 ∨ pcf(tid) = E2 ∨ pcf(tid) = E3 ∨ pcf(tid) = E4 ∨ pcf(tid) = E5 ∨ pcf(tid) = E6 ∨ pcf(tid) = E7 ∨ pcf(tid) = E8 ∨ pcf(tid) = E9 ∨ pcf(tid) = E10 ∨ pcf(tid) = E11 ∨ pcf(tid) = E12 ∨ pcf(tid) = E13 ∨ pcf(tid) = E14 ∨ pcf(tid) = E15 ∨ pcf(tid) = E16 ∨ pcf(tid) = E17 ∨ pcf(tid) = D1 ∨ pcf(tid) = D2 ∨ pcf(tid) = D3 ∨ pcf(tid) = D4 ∨ pcf(tid) = D5 ∨ pcf(tid) = D6 ∨ pcf(tid) = D7 ∨ pcf(tid) = D8 ∨ pcf(tid) = D9 ∨ pcf(tid) = D10 ∨ pcf(tid) = D11 ∨ pcf(tid) = D12 ∨ pcf(tid) = D13 ∨ pcf(tid) = D14 ∨ pcf(tid) = D15 ∨ pcf(tid) = D16 ∨ pcf(tid) = D17 ∨ pcf(tid) = D18 ∨ pcf(tid) = D19 ∨ pcf(tid) = D25 ∨ pcf(tid) = D26 ∨ pcf(tid) = D27 ∨ pcf(tid) = D28 ∨ pcf(tid) = D29 ∨ pcf(tid) = D30 ∨ pcf(tid) = D31 ∨ pcf(tid) = D32 ∨ pcf(tid) = D33 ∨ pcf(tid) = D34 → nextnottid (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs), pcf(tid) = D20 ∨ pcf(tid) = D21 ∨ pcf(tid) = D22 ∨ pcf(tid) = D23 ∨ pcf(tid) = D24 → mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead ≠ mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first → nextnottid (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs), pcf(tid) = crashed ∨ pcf(tid) = idle ∨ pcf(tid) = ready ∨ pcf(tid) = E1 ∨ pcf(tid) = E2 ∨ pcf(tid) = E3 ∨ pcf(tid) = E4 ∨ pcf(tid) = E5 ∨ pcf(tid) = E6 ∨ pcf(tid) = E7 ∨ pcf(tid) = E8 ∨ pcf(tid) = E9 ∨ pcf(tid) = E10 ∨ pcf(tid) = E11 ∨ pcf(tid) = E12 ∨ pcf(tid) = E13 ∨ pcf(tid) = E14 ∨ pcf(tid) = E15 ∨ pcf(tid) = E16 ∨ pcf(tid) = E17 ∨ pcf(tid) = D1 ∨ pcf(tid) = D2 ∨ pcf(tid) = D3 ∨ pcf(tid) = D4 ∨ pcf(tid) = D5 ∨ pcf(tid) = D6 ∨ pcf(tid) = D7 ∨ pcf(tid) = D16 ∨ pcf(tid) = D17 ∨ pcf(tid) = D25 ∨ pcf(tid) = D26 ∨ pcf(tid) = D27 ∨ pcf(tid) = D28 ∨ pcf(tid) = D29 ∨ pcf(tid) = D30 ∨ pcf(tid) = D31 ∨ pcf(tid) = D32 ∨ pcf(tid) = D33 ∨ pcf(tid) = D34 → noid (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vhead, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs), pcf(tid) = D8 ∨ pcf(tid) = D9 ∨ pcf(tid) = D10 ∨ pcf(tid) = D11 ∨ pcf(tid) = D12 ∨ pcf(tid) = D13 ∨ pcf(tid) = D14 ∨ pcf(tid) = D15 ∨ pcf(tid) = D18 ∨ pcf(tid) = D19 → noid (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).first, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs), pcf(tid) = D22 ∨ pcf(tid) = D23 ∨ pcf(tid) = D24 → noid (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).orl + mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).qrl, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).nxt, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs), pcf(tid) = crashed ∨ pcf(tid) = idle ∨ pcf(tid) = ready ∨ pcf(tid) = D1 ∨ pcf(tid) = D2 ∨ pcf(tid) = D3 ∨ pcf(tid) = D4 ∨ pcf(tid) = D5 ∨ pcf(tid) = D6 ∨ pcf(tid) = D7 ∨ pcf(tid) = D8 ∨ pcf(tid) = D9 ∨ pcf(tid) = D10 ∨ pcf(tid) = D11 ∨ pcf(tid) = D12 ∨ pcf(tid) = D13 ∨ pcf(tid) = D14 ∨ pcf(tid) = D15 ∨ pcf(tid) = D16 ∨ pcf(tid) = D17 ∨ pcf(tid) = D18 ∨ pcf(tid) = D19 ∨ pcf(tid) = D20 ∨ pcf(tid) = D21 ∨ pcf(tid) = D22 ∨ pcf(tid) = D23 ∨ pcf(tid) = D24 ∨ pcf(tid) = D25 ∨ pcf(tid) = D26 ∨ pcf(tid) = D27 ∨ pcf(tid) = D28 ∨ pcf(tid) = D29 ∨ pcf(tid) = D30 ∨ pcf(tid) = D31 ∨ pcf(tid) = D32 ∨ pcf(tid) = D33 ∨ pcf(tid) = D34 ∨ pcf(tid) = E1 ∨ pcf(tid) = E12 ∨ pcf(tid) = E17 → noowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns), pcf(tid) = E2 ∨ pcf(tid) = E3 ∨ pcf(tid) = E5 ∨ pcf(tid) = E6 ∨ pcf(tid) = E7 ∨ pcf(tid) = E8 ∨ pcf(tid) = E9 ∨ pcf(tid) = E13 ∨ pcf(tid) = E14 ∨ pcf(tid) = E15 ∨ pcf(tid) = E16 → oneowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps), pcf(tid) = E10 → (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success ⊃ ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next ≠ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next ⊃ oneweakowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps) ;noowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns) ) ;oneowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps) ), pcf(tid) = E11 → ( mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next ≠ mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs [mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).lst ] .next ⊃ oneweakowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps) ;noowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns) ), pcf(tid) = E4 → (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).success ⊃ noowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns) ;oneowns (mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).tid, mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr).node, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).owns, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).vs, mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns).ps) ), ∀ tid. lsf(tid).tid = tid ∧ DMSQLInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf(tid), pcf(tid)), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null, orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs) ⊦ (pcf(tid) = E10 ∧ success ∨ pcf(tid) = E11) ∧ node = vs[(orl + qrl).last].next ∧ lst = (orl + qrl).last ∧ vtail = (orl + qrl).last

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: ⊦ mkls (tid, value, optval, node, nd, success, node0, node1, rvref, optval0, node2, tid0, rvref0) .node = node; (s) ⊦ mkls (tid, value, optval, node, nd, success, node0, node1, rvref, optval0, node2, tid0, rvref0) .lst = node0; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .ps = ps; (s) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .qrl = qrl; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .orl = qrl0; (s) ⊦ mkls (tid, value, optval, node, nd, success, node0, node1, rvref, optval0, node2, tid0, rvref0) .tid = tid; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .owns = owns; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .vtail = phead1; (s) ⊦ mkls (tid, value, optval, node, nd, success, node0, node1, rvref, optval0, node2, tid0, rvref0) .value = value; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .vs = ps0; (s) ⊦ mkls (tid, value, optval, node, nd, success, node0, node1, rvref, optval0, node2, tid0, rvref0) .success ↔ success; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .vhead = phead0; (s) ⊦ owns(r) = Weak(tid) → ¬ noowns(tid, owns); (s) ⊦ owns(r) = Weak(tid) ∧ r ∈ ps ∧ r ∈ vs → ¬ oneowns(tid, r0, owns, vs, ps); (s)

Proof step 17 from proof DMSQInv-atDoEnq (previous step) (back to tree)

vs[vs[(orl + qrl).last].next].deqID = None, vs[vs[(orl + qrl).last].next].next = null, ps[vs[(orl + qrl).last].next] = vs[vs[(orl + qrl).last].next], dom vrvHp = dom prvHp, lsf(tid) = mkls(tid, value, optval, node, nd, success, lst, nxt, rvref, optval0, first, othertid, addr), owns(vs[(orl + qrl).last].next) = Weak(tid), vs[(orl + qrl).last].next ≠ null, orl ≠ [], pcf(tid) ≠ E4, pcf(tid) ≠ E2, pcf(tid) ≠ E3, pcf(tid) ≠ E5, pcf(tid) ≠ E6, pcf(tid) ≠ E7, pcf(tid) ≠ E8, pcf(tid) ≠ E9, pcf(tid) ≠ E13, pcf(tid) ≠ E14, pcf(tid) ≠ E15, pcf(tid) ≠ E16, pcf(tid) ≠ crashed, pcf(tid) ≠ idle, pcf(tid) ≠ ready, pcf(tid) ≠ D1, pcf(tid) ≠ D2, pcf(tid) ≠ D3, pcf(tid) ≠ D4, pcf(tid) ≠ D5, pcf(tid) ≠ D6, pcf(tid) ≠ D7, pcf(tid) ≠ D8, pcf(tid) ≠ D9, pcf(tid) ≠ D10, pcf(tid) ≠ D11, pcf(tid) ≠ D12, pcf(tid) ≠ D13, pcf(tid) ≠ D14, pcf(tid) ≠ D15, pcf(tid) ≠ D16, pcf(tid) ≠ D17, pcf(tid) ≠ D18, pcf(tid) ≠ D19, pcf(tid) ≠ D20, pcf(tid) ≠ D21, pcf(tid) ≠ D22, pcf(tid) ≠ D23, pcf(tid) ≠ D24, pcf(tid) ≠ D25, pcf(tid) ≠ D26, pcf(tid) ≠ D27, pcf(tid) ≠ D28, pcf(tid) ≠ D29, pcf(tid) ≠ D30, pcf(tid) ≠ D31, pcf(tid) ≠ D32, pcf(tid) ≠ D33, pcf(tid) ≠ D34, pcf(tid) ≠ E1, pcf(tid) ≠ E12, pcf(tid) ≠ E17, allocrv(vretRefs, vrvHp), allocrv(pretRefs, prvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, ps), markedp(orl, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), rvownerok(vretRefs, vrvHp, rvowns), rvownerok(pretRefs, prvHp, rvowns), unmarkedp(qrl, ps), phead ∈ ps, phead ∈ vs, vs[(orl + qrl).last].next ∈ vs, vs[(orl + qrl).last].next ∈ ps, phead ∈ orl, ¬ 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), pcf(tid) = E11 → ps[lst].next ≠ vs[lst].next ∧ oneweakowns(tid, node, owns, vs, ps), pcf(tid) = E10 → success ∧ ps[lst].next ≠ vs[lst].next ∧ oneweakowns(tid, node, owns, vs, ps), pcf(tid) = E10 ∨ pcf(tid) = E11 → noid(tid, orl + qrl, vhead, vs), pcf(tid) = E10 ∨ pcf(tid) = E11 → nextnottid(tid, vhead, vs), pcf(tid) = E10 → ¬ success → ¬ node ∈ orl ∧ ¬ node ∈ qrl ∧ node ≠ null ∧ node ∈ ps ∧ node ∈ vs ∧ owns(node) = Some(tid) ∧ vs[node] = mk(value, None, null) ∧ ps[node] = vs[node], pcf(tid) = E11 → success ∧ vs[lst].next = node ∧ vs[lst].next ≠ null ∧ vs[vs[lst].next].val = value ∧ (lst = vtail ∧ ps[vtail].next = null ∧ owns(vs[vtail].next) = Weak(tid) ∨ (lst ∈ orl ∨ lst ∈ qrl) ∧ ps[lst].next = vs[lst].next), pcf(tid) = E10 → success → vs[lst].next = node ∧ vs[lst].next ≠ null ∧ vs[vs[lst].next].val = value ∧ (lst = vtail ∧ ps[vtail].next = null ∧ owns(vs[vtail].next) = Weak(tid) ∨ (lst ∈ orl ∨ lst ∈ qrl) ∧ ps[lst].next = vs[lst].next), ∀ tid. lsf(tid).tid = tid ∧ DMSQLInv(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), lsf(tid), pcf(tid)), orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null ⊦ (pcf(tid) = E10 ∧ success ∨ pcf(tid) = E11) ∧ node = vs[(orl + qrl).last].next ∧ lst = (orl + qrl).last ∧ vtail = (orl + qrl).last

User applied rule structural induction

And closed the goal!

Rule argument

term: pcf(tid)

Additional information

Used simplifier rules: DMSQPC freely generated by D1, D2, D3, D4, D5, D6, D7, D8, D9, D10, D11, D12, D13, D14, D15, D16, D17, D18, D19, D20, D21, D22, D23, D24, D25, D26, D27, D28, D29, D30, D31, D32, D33, D34, E1, E2, E3, E4, E5, E6, E7, E8, E9, E10, E11, E12, E13, E14, E15, E16, E17, crashed, idle, ready ;; ⊦ y ≠ [] → (x + y).last = y.last; (s) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist]

Proof Tree for DMSQInv-atDoEnq (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