[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 rely-E1-E1 (conclusion) (back to tree)

⊦ ls.tid ≠ tid0 ∧ ( ( 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)) ∧ nextnottid(ls.tid, gs.vhead, gs.vs) ∧ noid(ls.tid, gs.orl + gs.qrl, gs.vhead, gs.vs) ∧ noowns(ls.tid, gs.owns)) ∧ pre(gs, ls, E1, a) ∧ pcstepf(gs, ls, E1, a) = E1 → (∃ rl. gs.orl + gs.qrl + rl = gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl) ∧ (∃ rl0. gs.orl + rl0 = gstepf(gs, ls, E1, a).orl) ∧ gstepf(gs, ls, E1, a).vtail ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from gs.vtail ∧ gstepf(gs, ls, E1, a).phead ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from gs.phead ∧ gstepf(gs, ls, E1, a).vhead ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from gs.vhead ∧ equalrl(gs.orl + gs.qrl, gs.vs, gs.ps, gstepf(gs, ls, E1, a).vs, gstepf(gs, ls, E1, a).ps) ∧ equalowns(gs.vs, gs.ps, gs.owns, tid0, gstepf(gs, ls, E1, a).vs, gstepf(gs, ls, E1, a).ps, gstepf(gs, ls, E1, a).owns) ∧ gs.vretRefs(tid0) = gstepf(gs, ls, E1, a).vretRefs(tid0) ∧ (gs.pretRefs(tid0) = gstepf(gs, ls, E1, a).pretRefs(tid0) ∨ gs.vretRefs(tid0) = gstepf(gs, ls, E1, a).pretRefs(tid0)) ∧ rvownsrely(tid0, gs.rvowns, gstepf(gs, ls, E1, a).rvowns, gs.vrvHp) ∧ rvrely(tid0, gs.rvowns, gs.vretRefs, gs.vrvHp, gstepf(gs, ls, E1, a).vretRefs, gstepf(gs, ls, E1, a).vrvHp) ∧ dom gs.vrvHp ⊆ dom gstepf(gs, ls, E1, a).vrvHp ∧ prvHpRely(gs.vrvHp, gs.prvHp, gstepf(gs, ls, E1, a).prvHp) ∧ noidRely(tid0, gs.orl + gs.qrl, gs.vs, gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl, gstepf(gs, ls, E1, a).vs) ∧ nextnottidRely(tid0, gs.vhead, gs.vs, gstepf(gs, ls, E1, a).vhead, gstepf(gs, ls, E1, a).vs) ∧ ownsRely(tid0, gs.owns, gstepf(gs, ls, E1, a).owns)

System applied rule normalize

And obtained the following new goals

Rule argument

Additional information

Proof step 2 from proof rely-E1-E1 (previous step) (back to tree)

dom gs.vrvHp = dom gs.prvHp, pcstepf(gs, ls, E1, a) = E1, gs.orl ≠ [], ls.tid ≠ tid0, allocrv(gs.vretRefs, gs.vrvHp), allocrv(gs.pretRefs, gs.prvHp), listp(gs.orl + gs.qrl, gs.vs, gs.ps, gs.owns), markedp(gs.orl, gs.ps), markedp(gs.orl, gs.vs), nextnottid(ls.tid, gs.vhead, gs.vs), noid(ls.tid, gs.orl + gs.qrl, gs.vhead, gs.vs), nonullRetRefs(gs.orl + gs.qrl, gs.vs, gs.vretRefs, gs.pretRefs), noowns(ls.tid, gs.owns), pre(gs, ls, E1, a), rvownerok(gs.vretRefs, gs.vrvHp, gs.rvowns), rvownerok(gs.pretRefs, gs.prvHp, gs.rvowns), unmarkedp(gs.qrl, gs.ps), gs.phead ∈ gs.orl, ¬ dups(gs.orl + gs.qrl), gs.vs[gs.vhead].next ≠ null ∧ gs.vs[gs.vs[gs.vhead].next].deqID ≠ None → gs.rvowns(gs.vretRefs(gs.vs[gs.vs[gs.vhead].next].deqID.tid)) = Claimed(gs.vs[gs.vs[gs.vhead].next].deqID.tid, gs.vs[gs.vs[gs.vhead].next].val), gs.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 ⊦ (∃ rl. gs.orl + gs.qrl + rl = gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl) ∧ (∃ rl0. gs.orl + rl0 = gstepf(gs, ls, E1, a).orl) ∧ gstepf(gs, ls, E1, a).vtail ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from gs.vtail ∧ gstepf(gs, ls, E1, a).phead ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from gs.phead ∧ gstepf(gs, ls, E1, a).vhead ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from gs.vhead ∧ equalrl(gs.orl + gs.qrl, gs.vs, gs.ps, gstepf(gs, ls, E1, a).vs, gstepf(gs, ls, E1, a).ps) ∧ equalowns(gs.vs, gs.ps, gs.owns, tid0, gstepf(gs, ls, E1, a).vs, gstepf(gs, ls, E1, a).ps, gstepf(gs, ls, E1, a).owns) ∧ gs.vretRefs(tid0) = gstepf(gs, ls, E1, a).vretRefs(tid0) ∧ (gs.pretRefs(tid0) = gstepf(gs, ls, E1, a).pretRefs(tid0) ∨ gs.vretRefs(tid0) = gstepf(gs, ls, E1, a).pretRefs(tid0)) ∧ rvownsrely(tid0, gs.rvowns, gstepf(gs, ls, E1, a).rvowns, gs.vrvHp) ∧ rvrely(tid0, gs.rvowns, gs.vretRefs, gs.vrvHp, gstepf(gs, ls, E1, a).vretRefs, gstepf(gs, ls, E1, a).vrvHp) ∧ dom gs.vrvHp ⊆ dom gstepf(gs, ls, E1, a).vrvHp ∧ prvHpRely(gs.vrvHp, gs.prvHp, gstepf(gs, ls, E1, a).prvHp) ∧ noidRely(tid0, gs.orl + gs.qrl, gs.vs, gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl, gstepf(gs, ls, E1, a).vs) ∧ nextnottidRely(tid0, gs.vhead, gs.vs, gstepf(gs, ls, E1, a).vhead, gstepf(gs, ls, E1, a).vs) ∧ ownsRely(tid0, gs.owns, gstepf(gs, ls, E1, a).owns)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] a: ⊦ ¬ dups(x + y) → ¬ dups(x) ∧ ¬ dups(y); (forward) from specification list-dup[reflist] list-elem-in-app11: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ vs; (forward) from specification DMSQ list-elem-in-app12: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ ps; (forward) from specification DMSQ ⊦ y ≠ [] → (x + y).last = y.last; (s) ⊦ pre(gs, ls, E1, a) ↔ (∃ node0, nd0, success0. ( ¬ node0 ∈ gs.vs ∧ ¬ node0 ∈ gs.ps ∧ node0 ≠ null ∧ (success0 ↔ false)) ∧ a = chooseE1(node0, nd0, success0)) ∨ a = τ ∧ ¬ (∃ node0, nd0, success0. ¬ node0 ∈ gs.vs ∧ ¬ node0 ∈ gs.ps ∧ node0 ≠ null ∧ (success0 ↔ false)); (s) ⊦ E1 ≠ E2; (s) ⊦ pcstepf(gs, ls, E1, a) = (∃ node0, nd0, success0. a = chooseE1(node0, nd0, success0) ⊃ E2;E1); (s)

Proof step 3 from proof rely-E1-E1 (previous step) (back to tree)

dom gs.vrvHp = dom gs.prvHp, gs.orl ≠ [], ls.tid ≠ tid0, allocrv(gs.pretRefs, gs.prvHp), allocrv(gs.vretRefs, gs.vrvHp), listp(gs.orl + gs.qrl, gs.vs, gs.ps, gs.owns), markedp(gs.orl, gs.vs), markedp(gs.orl, gs.ps), nextnottid(ls.tid, gs.vhead, gs.vs), noid(ls.tid, gs.orl + gs.qrl, gs.vhead, gs.vs), nonullRetRefs(gs.orl + gs.qrl, gs.vs, gs.vretRefs, gs.pretRefs), noowns(ls.tid, gs.owns), rvownerok(gs.pretRefs, gs.prvHp, gs.rvowns), rvownerok(gs.vretRefs, gs.vrvHp, gs.rvowns), unmarkedp(gs.qrl, gs.ps), gs.phead ∈ gs.orl, gs.phead ∈ gs.vs, gs.phead ∈ gs.ps, ¬ dups(gs.orl + gs.qrl), ¬ dups(gs.orl), ¬ dups(gs.qrl), gs.vs[gs.vhead].next ≠ null ∧ gs.vs[gs.vs[gs.vhead].next].deqID ≠ None → gs.rvowns(gs.vretRefs(gs.vs[gs.vs[gs.vhead].next].deqID.tid)) = Claimed(gs.vs[gs.vs[gs.vhead].next].deqID.tid, gs.vs[gs.vs[gs.vhead].next].val), gs.orl.last = gs.vhead ∧ (gs.qrl ≠ [] → unmarkedp(gs.qrl.tail, gs.vs)) ∨ gs.orl.butlast ≠ [] ∧ gs.orl.butlast.last = gs.vhead ∧ gs.phead ≠ gs.orl.last ∧ unmarkedp(gs.qrl, gs.vs), ¬ node0 ∈ gs.vs ∧ ¬ node0 ∈ gs.ps ∧ node0 ≠ null ∧ ¬ success0 ∧ a = chooseE1(node0, nd0, false) ∨ a = τ ∧ ¬(∃ node. ¬ node ∈ gs.vs ∧ ¬ node ∈ gs.ps ∧ node ≠ null), gs.vtail = (gs.orl + gs.qrl).last ∨ gs.qrl ≠ [] ∧ gs.vtail = (gs.orl + gs.qrl.butlast).last ∧ gs.vs[gs.qrl.last].deqID = None ∧ gs.vs[gs.qrl.last].next = null ⊦ ∃ node0, nd0, success0. a = chooseE1(node0, nd0, success0), (∃ rl. gs.orl + gs.qrl + rl = gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl) ∧ (∃ rl0. gs.orl + rl0 = gstepf(gs, ls, E1, a).orl) ∧ gstepf(gs, ls, E1, a).vtail ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from gs.vtail ∧ gstepf(gs, ls, E1, a).phead ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from gs.phead ∧ gstepf(gs, ls, E1, a).vhead ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from gs.vhead ∧ equalrl(gs.orl + gs.qrl, gs.vs, gs.ps, gstepf(gs, ls, E1, a).vs, gstepf(gs, ls, E1, a).ps) ∧ equalowns(gs.vs, gs.ps, gs.owns, tid0, gstepf(gs, ls, E1, a).vs, gstepf(gs, ls, E1, a).ps, gstepf(gs, ls, E1, a).owns) ∧ gs.vretRefs(tid0) = gstepf(gs, ls, E1, a).vretRefs(tid0) ∧ (gs.pretRefs(tid0) = gstepf(gs, ls, E1, a).pretRefs(tid0) ∨ gs.vretRefs(tid0) = gstepf(gs, ls, E1, a).pretRefs(tid0)) ∧ rvownsrely(tid0, gs.rvowns, gstepf(gs, ls, E1, a).rvowns, gs.vrvHp) ∧ rvrely(tid0, gs.rvowns, gs.vretRefs, gs.vrvHp, gstepf(gs, ls, E1, a).vretRefs, gstepf(gs, ls, E1, a).vrvHp) ∧ dom gs.prvHp ⊆ dom gstepf(gs, ls, E1, a).vrvHp ∧ prvHpRely(gs.vrvHp, gs.prvHp, gstepf(gs, ls, E1, a).prvHp) ∧ noidRely(tid0, gs.orl + gs.qrl, gs.vs, gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl, gstepf(gs, ls, E1, a).vs) ∧ nextnottidRely(tid0, gs.vhead, gs.vs, gstepf(gs, ls, E1, a).vhead, gstepf(gs, ls, E1, a).vs) ∧ ownsRely(tid0, gs.owns, gstepf(gs, ls, E1, a).owns)

Heuristic elimination applied rule apply elim lemma

And obtained the following new goals

Rule argument

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

Additional information

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

Proof step 4 from proof rely-E1-E1 (previous step) (back to tree)

dom vrvHp = dom prvHp, gs = mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls.tid ≠ tid0, orl ≠ [], allocrv(vretRefs, vrvHp), allocrv(pretRefs, prvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, ps), markedp(orl, vs), nextnottid(ls.tid, vhead, vs), noid(ls.tid, orl + qrl, vhead, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), noowns(ls.tid, owns), rvownerok(vretRefs, vrvHp, rvowns), rvownerok(pretRefs, prvHp, rvowns), unmarkedp(qrl, ps), phead ∈ ps, phead ∈ vs, 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), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null, ¬ node0 ∈ vs ∧ ¬ node0 ∈ ps ∧ node0 ≠ null ∧ ¬ success0 ∧ a = chooseE1(node0, nd0, false) ∨ a = τ ∧ ¬(∃ node. ¬ node ∈ vs ∧ ¬ node ∈ ps ∧ node ≠ null), orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs) ⊦ ∃ node0, nd0, success0. a = chooseE1(node0, nd0, success0), (∃ rl. orl + qrl + rl = gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl) ∧ (∃ rl0. orl + rl0 = gstepf(gs, ls, E1, a).orl) ∧ gstepf(gs, ls, E1, a).vtail ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from vtail ∧ gstepf(gs, ls, E1, a).phead ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from phead ∧ gstepf(gs, ls, E1, a).vhead ∈ gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl from vhead ∧ equalrl(orl + qrl, vs, ps, gstepf(gs, ls, E1, a).vs, gstepf(gs, ls, E1, a).ps) ∧ equalowns(vs, ps, owns, tid0, gstepf(gs, ls, E1, a).vs, gstepf(gs, ls, E1, a).ps, gstepf(gs, ls, E1, a).owns) ∧ vretRefs(tid0) = gstepf(gs, ls, E1, a).vretRefs(tid0) ∧ (pretRefs(tid0) = gstepf(gs, ls, E1, a).pretRefs(tid0) ∨ vretRefs(tid0) = gstepf(gs, ls, E1, a).pretRefs(tid0)) ∧ rvownsrely(tid0, rvowns, gstepf(gs, ls, E1, a).rvowns, vrvHp) ∧ rvrely(tid0, rvowns, vretRefs, vrvHp, gstepf(gs, ls, E1, a).vretRefs, gstepf(gs, ls, E1, a).vrvHp) ∧ dom prvHp ⊆ dom gstepf(gs, ls, E1, a).vrvHp ∧ prvHpRely(vrvHp, prvHp, gstepf(gs, ls, E1, a).prvHp) ∧ noidRely(tid0, orl + qrl, vs, gstepf(gs, ls, E1, a).orl + gstepf(gs, ls, E1, a).qrl, gstepf(gs, ls, E1, a).vs) ∧ nextnottidRely(tid0, vhead, vs, gstepf(gs, ls, E1, a).vhead, gstepf(gs, ls, E1, a).vs) ∧ ownsRely(tid0, owns, gstepf(gs, ls, E1, a).owns)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] a: ⊦ ¬ dups(x + y) → ¬ dups(x) ∧ ¬ dups(y); (forward) from specification list-dup[reflist] list-elem-in-app11: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ vs; (forward) from specification DMSQ list-elem-in-app12: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ ps; (forward) from specification DMSQ

Proof step 5 from proof rely-E1-E1 (previous step) (back to tree)

dom vrvHp = dom prvHp, ls.tid ≠ tid0, orl ≠ [], allocrv(pretRefs, prvHp), allocrv(vretRefs, vrvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, vs), markedp(orl, ps), nextnottid(ls.tid, vhead, vs), noid(ls.tid, orl + qrl, vhead, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), noowns(ls.tid, owns), rvownerok(pretRefs, prvHp, rvowns), rvownerok(vretRefs, vrvHp, rvowns), unmarkedp(qrl, ps), phead ∈ orl, 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), orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs), ¬ node0 ∈ vs ∧ ¬ node0 ∈ ps ∧ node0 ≠ null ∧ ¬ success0 ∧ a = chooseE1(node0, nd0, false) ∨ a = τ ∧ ¬(∃ node. ¬ node ∈ vs ∧ ¬ node ∈ ps ∧ node ≠ null), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null ⊦ ∃ node0, nd0, success0. a = chooseE1(node0, nd0, success0), (∃ rl. orl + qrl + rl = gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).orl + gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).qrl) ∧ (∃ rl0. orl + rl0 = gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).orl) ∧ gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).vtail ∈ gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).orl + gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).qrl from vtail ∧ gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).phead ∈ gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).orl + gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).qrl from phead ∧ gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).vhead ∈ gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).orl + gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).qrl from vhead ∧ equalrl (orl + qrl, vs, ps, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).vs, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).ps) ∧ equalowns (vs, ps, owns, tid0, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).vs, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).ps, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).owns) ∧ vretRefs(tid0) = gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).vretRefs(tid0) ∧ ( pretRefs(tid0) = gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).pretRefs(tid0) ∨ vretRefs(tid0) = gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).pretRefs(tid0)) ∧ rvownsrely (tid0, rvowns, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).rvowns, vrvHp) ∧ rvrely (tid0, rvowns, vretRefs, vrvHp, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).vretRefs, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).vrvHp) ∧ dom prvHp ⊆ dom gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).vrvHp ∧ prvHpRely(vrvHp, prvHp, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).prvHp) ∧ noidRely (tid0, orl + qrl, vs, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).orl + gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).qrl, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).vs) ∧ nextnottidRely (tid0, vhead, vs, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).vhead, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).vs) ∧ ownsRely(tid0, owns, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a).owns)

Heuristic elimination applied rule apply elim lemma

And obtained the following new goals

Rule argument

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

Additional information

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

Proof step 6 from proof rely-E1-E1 (previous step) (back to tree)

dom vrvHp = dom prvHp, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a) = mkgs(ps0, vs0, phead0, vhead0, vtail0, vretRefs0, pretRefs0, vrvHp0, prvHp0, qrl0, orl0, owns0, rvowns0), ls.tid ≠ tid0, orl ≠ [], allocrv(vretRefs, vrvHp), allocrv(pretRefs, prvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, ps), markedp(orl, vs), nextnottid(ls.tid, vhead, vs), noid(ls.tid, orl + qrl, vhead, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), noowns(ls.tid, owns), rvownerok(vretRefs, vrvHp, rvowns), rvownerok(pretRefs, prvHp, rvowns), unmarkedp(qrl, ps), phead ∈ ps, phead ∈ vs, 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), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null, ¬ node0 ∈ vs ∧ ¬ node0 ∈ ps ∧ node0 ≠ null ∧ ¬ success0 ∧ a = chooseE1(node0, nd0, false) ∨ a = τ ∧ ¬(∃ node. ¬ node ∈ vs ∧ ¬ node ∈ ps ∧ node ≠ null), orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs) ⊦ ∃ node0, nd0, success0. a = chooseE1(node0, nd0, success0), (∃ rl. orl + qrl + rl = orl0 + qrl0) ∧ (∃ rl0. orl + rl0 = orl0) ∧ vtail0 ∈ orl0 + qrl0 from vtail ∧ phead0 ∈ orl0 + qrl0 from phead ∧ vhead0 ∈ orl0 + qrl0 from vhead ∧ equalrl(orl + qrl, vs, ps, vs0, ps0) ∧ equalowns(vs, ps, owns, tid0, vs0, ps0, owns0) ∧ vretRefs(tid0) = vretRefs0(tid0) ∧ (pretRefs(tid0) = pretRefs0(tid0) ∨ vretRefs(tid0) = pretRefs0(tid0)) ∧ rvownsrely(tid0, rvowns, rvowns0, vrvHp) ∧ rvrely(tid0, rvowns, vretRefs, vrvHp, vretRefs0, vrvHp0) ∧ dom prvHp ⊆ dom vrvHp0 ∧ prvHpRely(vrvHp, prvHp, prvHp0) ∧ noidRely(tid0, orl + qrl, vs, orl0 + qrl0, vs0) ∧ nextnottidRely(tid0, vhead, vs, vhead0, vs0) ∧ ownsRely(tid0, owns, owns0)

User applied rule case distinction

And obtained the following new goals

Rule argument

pos: left 25

Additional information

Proof step 7 from proof rely-E1-E1 (previous step) (back to tree)

a = chooseE1(node0, nd0, false), dom vrvHp = dom prvHp, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a) = mkgs(ps0, vs0, phead0, vhead0, vtail0, vretRefs0, pretRefs0, vrvHp0, prvHp0, qrl0, orl0, owns0, rvowns0), ¬ success0, ls.tid ≠ tid0, node0 ≠ null, orl ≠ [], allocrv(pretRefs, prvHp), allocrv(vretRefs, vrvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, vs), markedp(orl, ps), nextnottid(ls.tid, vhead, vs), noid(ls.tid, orl + qrl, vhead, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), noowns(ls.tid, owns), rvownerok(pretRefs, prvHp, rvowns), rvownerok(vretRefs, vrvHp, rvowns), unmarkedp(qrl, ps), phead ∈ orl, phead ∈ vs, phead ∈ ps, ¬ dups(orl + qrl), ¬ dups(orl), ¬ dups(qrl), ¬ node0 ∈ ps, ¬ node0 ∈ vs, vs[vhead].next ≠ null ∧ vs[vs[vhead].next].deqID ≠ None → rvowns(vretRefs(vs[vs[vhead].next].deqID.tid)) = Claimed(vs[vs[vhead].next].deqID.tid, vs[vs[vhead].next].val), orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs), vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[qrl.last].next = null ⊦ ∃ node0, nd0, success0. a = chooseE1(node0, nd0, success0), (∃ rl. orl + qrl + rl = orl0 + qrl0) ∧ (∃ rl0. orl + rl0 = orl0) ∧ vtail0 ∈ orl0 + qrl0 from vtail ∧ phead0 ∈ orl0 + qrl0 from phead ∧ vhead0 ∈ orl0 + qrl0 from vhead ∧ equalrl(orl + qrl, vs, ps, vs0, ps0) ∧ equalowns(vs, ps, owns, tid0, vs0, ps0, owns0) ∧ vretRefs(tid0) = vretRefs0(tid0) ∧ (pretRefs(tid0) = pretRefs0(tid0) ∨ vretRefs(tid0) = pretRefs0(tid0)) ∧ rvownsrely(tid0, rvowns, rvowns0, vrvHp) ∧ rvrely(tid0, rvowns, vretRefs, vrvHp, vretRefs0, vrvHp0) ∧ dom prvHp ⊆ dom vrvHp0 ∧ prvHpRely(vrvHp, prvHp, prvHp0) ∧ noidRely(tid0, orl + qrl, vs, orl0 + qrl0, vs0) ∧ nextnottidRely(tid0, vhead, vs, vhead0, vs0) ∧ ownsRely(tid0, owns, owns0)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: ⊦ # s = # s0 → (s ⊆ s0 ↔ s = s0); (s) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] a: ⊦ ¬ dups(x + y) → ¬ dups(x) ∧ ¬ dups(y); (forward) from specification list-dup[reflist] list-elem-in-app11: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ vs; (forward) from specification DMSQ list-elem-in-app12: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ ps; (forward) from specification DMSQ ⊦ prvHpRely(vrvHp, prvHp, prvHp); (s) ⊦ rvrely(tid, rvowns, vretRefs, vrvHp, vretRefs, vrvHp); (s) ⊦ rvownsrely(tid, rvowns, rvowns, vrvHp); (s) ⊦ r ∈ rl → r ∈ rl from r; (ss) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) ⊦ r ∈ orl → orl + qrl from r = (orl from r) + qrl; (s) ⊦ x = x + y ↔ y = []; (s) ⊦ # x = # z → (x + y = z + y0 ↔ x = z ∧ y = y0); (ws) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) = mkgs (ps1, ps2, phead2, phead3, phead4, vretRefs1, vretRefs2, vrvHp1, vrvHp2, qrl1, qrl2, owns0, rvowns0) ↔ ps = ps1 ∧ ps0 = ps2 ∧ phead = phead2 ∧ phead0 = phead3 ∧ phead1 = phead4 ∧ vretRefs = vretRefs1 ∧ vretRefs0 = vretRefs2 ∧ vrvHp = vrvHp1 ∧ vrvHp0 = vrvHp2 ∧ qrl = qrl1 ∧ qrl0 = qrl2 ∧ owns = owns0 ∧ rvowns = rvowns0; (ws) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .owns:= owns0 = mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns0, rvowns); (s) ⊦ (ls.node:= node).tid = ls.tid; (s) ⊦ (ls.nd:= nd).tid = ls.tid; (s) ⊦ (ls.success:= success).tid = ls.tid; (s) ⊦ (ls.node:= node).node = node; (s) ⊦ (ls.nd:= nd).node = ls.node; (s) ⊦ (ls.success:= success).node = ls.node; (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) .vs:= ps2 = mkgs (ps, ps2, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns); (s) ⊦ (ls.nd:= nd).nd = nd; (s) ⊦ (ls.success:= success).nd = ls.nd; (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) .ps:= ps1 = mkgs (ps1, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns); (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .ps = ps; (s) ⊦ gstepf(gs, ls, E1, chooseE1(node0, nd0, success0)) = ( ( gs .ps:= gs.ps [(((ls.node:= node0).nd:= nd0).success:= success0 ).node, (((ls.node:= node0).nd:= nd0).success:= success0).nd ]) .vs:= gs.vs [(((ls.node:= node0).nd:= nd0).success:= success0).node, (((ls.node:= node0).nd:= nd0).success:= success0).nd ]) .owns:= gs.owns ((((ls.node:= node0).nd:= nd0).success:= success0).node ; Some((((ls.node:= node0).nd:= nd0).success:= success0).tid) ); (s)

Proof step 8 from proof rely-E1-E1 (previous step) (back to tree)

dom vrvHp0 = dom prvHp0, ls.tid ≠ tid0, node0 ≠ null, orl0 ≠ [], allocrv(vretRefs0, vrvHp0), allocrv(pretRefs0, prvHp0), listp(orl0 + qrl0, vs, ps, owns), markedp(orl0, ps), markedp(orl0, vs), nextnottid(ls.tid, vhead0, vs), noid(ls.tid, orl0 + qrl0, vhead0, vs), nonullRetRefs(orl0 + qrl0, vs, vretRefs0, pretRefs0), noowns(ls.tid, owns), rvownerok(vretRefs0, vrvHp0, rvowns0), rvownerok(pretRefs0, prvHp0, rvowns0), unmarkedp(qrl0, ps), phead0 ∈ ps, phead0 ∈ vs, phead0 ∈ orl0, ¬ dups(qrl0), ¬ dups(orl0), ¬ dups(orl0 + qrl0), ¬ node0 ∈ ps, ¬ node0 ∈ vs, vs[vhead0].next ≠ null ∧ vs[vs[vhead0].next].deqID ≠ None → rvowns0(vretRefs0(vs[vs[vhead0].next].deqID.tid)) = Claimed(vs[vs[vhead0].next].deqID.tid, vs[vs[vhead0].next].val), vtail0 = (orl0 + qrl0).last ∨ qrl0 ≠ [] ∧ vtail0 = (orl0 + qrl0.butlast).last ∧ vs[qrl0.last].deqID = None ∧ vs[qrl0.last].next = null, orl0.last = vhead0 ∧ (qrl0 ≠ [] → unmarkedp(qrl0.tail, vs)) ∨ orl0.butlast ≠ [] ∧ orl0.butlast.last = vhead0 ∧ phead0 ≠ orl0.last ∧ unmarkedp(qrl0, vs) ⊦ ∃ node, nd, success0. chooseE1(node0, nd0, false) = chooseE1(node, nd, success0), vtail0 ∈ orl0 + qrl0 from vtail0 ∧ vhead0 ∈ orl0 + qrl0 from vhead0 ∧ equalrl(orl0 + qrl0, vs, ps, vs[node0, nd0], ps[node0, nd0]) ∧ equalowns(vs, ps, owns, tid0, vs[node0, nd0], ps[node0, nd0], owns(node0; Some(ls.tid))) ∧ noidRely(tid0, orl0 + qrl0, vs, orl0 + qrl0, vs[node0, nd0]) ∧ nextnottidRely(tid0, vhead0, vs, vhead0, vs[node0, nd0]) ∧ ownsRely(tid0, owns, owns(node0; Some(ls.tid)))

Heuristic quantifier closing applied rule exists right

And closed the goal!

Rule argument

pos: right 1 terms: node0, nd0, false

Additional information

Used terms: node0, nd0, false

Proof step 9 from proof rely-E1-E1 (previous step) (back to tree)

a = τ, dom vrvHp = dom prvHp, gstepf(mkgs(ps, vs, phead, vhead, vtail, vretRefs, pretRefs, vrvHp, prvHp, qrl, orl, owns, rvowns), ls, E1, a) = mkgs(ps0, vs0, phead0, vhead0, vtail0, vretRefs0, pretRefs0, vrvHp0, prvHp0, qrl0, orl0, owns0, rvowns0), ls.tid ≠ tid0, orl ≠ [], allocrv(pretRefs, prvHp), allocrv(vretRefs, vrvHp), listp(orl + qrl, vs, ps, owns), markedp(orl, vs), markedp(orl, ps), nextnottid(ls.tid, vhead, vs), noid(ls.tid, orl + qrl, vhead, vs), nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs), noowns(ls.tid, owns), rvownerok(pretRefs, prvHp, rvowns), rvownerok(vretRefs, vrvHp, rvowns), unmarkedp(qrl, ps), phead ∈ orl, 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), 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 ⊦ ∃ node0, nd0, success0. a = chooseE1(node0, nd0, success0), ∃ node. ¬ node ∈ vs ∧ ¬ node ∈ ps ∧ node ≠ null, (∃ rl. orl + qrl + rl = orl0 + qrl0) ∧ (∃ rl0. orl + rl0 = orl0) ∧ vtail0 ∈ orl0 + qrl0 from vtail ∧ phead0 ∈ orl0 + qrl0 from phead ∧ vhead0 ∈ orl0 + qrl0 from vhead ∧ equalrl(orl + qrl, vs, ps, vs0, ps0) ∧ equalowns(vs, ps, owns, tid0, vs0, ps0, owns0) ∧ vretRefs(tid0) = vretRefs0(tid0) ∧ (pretRefs(tid0) = pretRefs0(tid0) ∨ vretRefs(tid0) = pretRefs0(tid0)) ∧ rvownsrely(tid0, rvowns, rvowns0, vrvHp) ∧ rvrely(tid0, rvowns, vretRefs, vrvHp, vretRefs0, vrvHp0) ∧ dom prvHp ⊆ dom vrvHp0 ∧ prvHpRely(vrvHp, prvHp, prvHp0) ∧ noidRely(tid0, orl + qrl, vs, orl0 + qrl0, vs0) ∧ nextnottidRely(tid0, vhead, vs, vhead0, vs0) ∧ ownsRely(tid0, owns, owns0)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: ⊦ # s = # s0 → (s ⊆ s0 ↔ s = s0); (s) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] a: ⊦ ¬ dups(x + y) → ¬ dups(x) ∧ ¬ dups(y); (forward) from specification list-dup[reflist] list-elem-in-app11: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ vs; (forward) from specification DMSQ list-elem-in-app12: ⊦ listp(orl + qrl, vs, ps, owns) ∧ node ∈ orl → node ∈ ps; (forward) from specification DMSQ ⊦ ownsRely(tid, owns, owns); (s) ⊦ nextnottidRely(tid, vhead, vs, vhead, vs); (s) ⊦ noidRely(tid, rl, vs, rl, vs); (s) ⊦ prvHpRely(vrvHp, prvHp, prvHp); (s) ⊦ rvrely(tid, rvowns, vretRefs, vrvHp, vretRefs, vrvHp); (s) ⊦ rvownsrely(tid, rvowns, rvowns, vrvHp); (s) ⊦ equalowns(vs, ps, owns, tid, vs, ps, owns); (s) ⊦ equalrl(rl, vs, ps, vs, ps); (s) ⊦ r ∈ rl → r ∈ rl from r; (ss) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) ⊦ r ∈ orl → orl + qrl from r = (orl from r) + qrl; (s) ⊦ x = x + y ↔ y = []; (s) ⊦ # x = # z → (x + y = z + y0 ↔ x = z ∧ y = y0); (ws) ⊦ chooseE1(node, nd, success) ≠ τ; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) = mkgs (ps1, ps2, phead2, phead3, phead4, vretRefs1, vretRefs2, vrvHp1, vrvHp2, qrl1, qrl2, owns0, rvowns0) ↔ ps = ps1 ∧ ps0 = ps2 ∧ phead = phead2 ∧ phead0 = phead3 ∧ phead1 = phead4 ∧ vretRefs = vretRefs1 ∧ vretRefs0 = vretRefs2 ∧ vrvHp = vrvHp1 ∧ vrvHp0 = vrvHp2 ∧ qrl = qrl1 ∧ qrl0 = qrl2 ∧ owns = owns0 ∧ rvowns = rvowns0; (ws) ⊦ gstepf(gs, ls, E1, τ) = gs; (s)

Proof step 10 from proof rely-E1-E1 (previous step) (back to tree)

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

User applied rule apply lemma

And obtained the following new goals

Rule argument

spec: DMSQ, name:unbounded-memory, seq: ⊦ ∃ node. node ≠ null ∧ ¬ node ∈ ps, subst:[ps] → [vs0 ⊕ ps0]

Additional information

Used terms: vs0 ⊕ ps0

Proof step 11 from proof rely-E1-E1 (previous step) (back to tree)

⊦ ∃ node. node ≠ null ∧ ¬ node ∈ ps

A spec-lemma

Proof step 12 from proof rely-E1-E1 (previous step) (back to tree)

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

Heuristic simplifier applied rule simplifier

And obtained the following new goals

Rule argument

Additional information

Used simplifier rules: ⊦ r ∈ ps ⊕ vs ↔ r ∈ ps ∨ r ∈ vs; (s)

Proof step 13 from proof rely-E1-E1 (previous step) (back to tree)

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

Heuristic quantifier closing applied rule exists right

And closed the goal!

Rule argument

pos: right 1 terms: node

Additional information

Used terms: node

Proof Tree for rely-E1-E1 (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