| ⊦ CIOAut?(CIOAut(DMSQinit, DMSQstep)) |
¬ CIOAut?(CIOAut(DMSQinit, DMSQstep)) ⊦
| ¬ CIOAut?(CIOAut(DMSQinit, DMSQstep)) ⊦ |
⊦ ∃ s. DMSQinit(s)
Used simplifier rules: ⊦ CIOAut?(CIOAut(startf, stepf)) ↔ (∃ s. startf(s)); (s)
| ⊦ ∃ s. DMSQinit(s) |
⊦ ∃ node. node ≠ null ∧ ¬ node ∈ ps
∃ node. node ≠ null ∧ ¬ node ∈ ∅ ⊦ ∃ s. DMSQinit(s)
Used terms: ∅
| ⊦ ∃ node. node ≠ null ∧ ¬ node ∈ ps |
| ∃ node. node ≠ null ∧ ¬ node ∈ ∅ ⊦ ∃ s. DMSQinit(s) |
vhead ≠ null ⊦ ∃ s. DMSQinit(s)
Used simplifier rules: ⊦ ¬ a ∈ ∅; (s)
| vhead ≠ null ⊦ ∃ s. DMSQinit(s) |
vhead ≠ null, ∃ vs. vs = ∅[vhead, mk(val, Some(dummytid), null)] ⊦ ∃ s. DMSQinit(s)
Used formulas: ∃ vs. vs = ∅[vhead, mk(val, Some(dummytid), null)]
| vhead ≠ null, ∃ vs. vs = ∅[vhead, mk(val, Some(dummytid), null)] ⊦ ∃ s. DMSQinit(s) |
vs = ∅[vhead, mk(val, Some(dummytid), null)], vhead ≠ null ⊦ ∃ s. DMSQinit(s)
| vs = ∅[vhead, mk(val, Some(dummytid), null)], vhead ≠ null ⊦ ∃ s. DMSQinit(s) |
⊦ ∃ lsf. ∀ tid. lsf(tid).tid = tid
vs = ∅[vhead, mk(val, Some(dummytid), null)], vhead ≠ null, ∃ lsf. ∀ tid. lsf(tid).tid = tid ⊦ ∃ s. DMSQinit(s)
Used terms:
| ⊦ ∃ lsf. ∀ tid. lsf(tid).tid = tid |
| vs = ∅[vhead, mk(val, Some(dummytid), null)], vhead ≠ null, ∃ lsf. ∀ tid. lsf(tid).tid = tid ⊦ ∃ s. DMSQinit(s) |
vs = ∅[vhead, mk(val, Some(dummytid), null)], vhead ≠ null, ∀ tid. lsf(tid).tid = tid ⊦ ∃ s. DMSQinit(s)
| vs = ∅[vhead, mk(val, Some(dummytid), null)], vhead ≠ null, ∀ tid. lsf(tid).tid = tid ⊦ ∃ s. DMSQinit(s) |
vs = ∅[vhead, mk(val, Some(dummytid), null)], vhead ≠ null, ¬ DMSQinit(mkstate(mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)), lsf, λ tid. idle)), ∀ tid. lsf(tid).tid = tid ⊦ ∃ s. DMSQinit(s)
Used terms: mkstate (mkgs (vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)), lsf, λ tid. idle)
| vs = ∅[vhead, mk(val, Some(dummytid), null)], vhead ≠ null, ¬ DMSQinit(mkstate(mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)), lsf, λ tid. idle)), ∀ tid. lsf(tid).tid = tid ⊦ ∃ s. DMSQinit(s) |
⊦ DMSQinit(mkstate(gs, lsf, pcf)) ↔ (∃ r, val. r ≠ null ∧ gs.ps = ∅[r, mk(val, Some(dummytid), null)] ∧ gs.phead = r ∧ gs.vhead = r ∧ gs.vtail = r ∧ gs.orl = r ' ∧ gs.qrl = [] ∧ gs.vs = gs.ps) ∧ gs.vrvHp = ∅ ∧ gs.prvHp = ∅ ∧ gs.vretRefs = (λ tid. null) ∧ gs.pretRefs = (λ tid. null) ∧ gs.owns = (λ r. None) ∧ pcf = (λ tid. idle) ∧ (∀ tid. lsf(tid).tid = tid)
vs = ∅[vhead, mk(val, Some(dummytid), null)], vhead ≠ null, ∀ tid. lsf(tid).tid = tid, (∀ r, val. ¬ ( r ≠ null ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).ps = ∅[r, mk(val, Some(dummytid), null)] ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).phead = r ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).vhead = r ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).vtail = r ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).orl = r ' ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).qrl = [] ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).vs = mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).ps)) ∨ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).vrvHp ≠ ∅ ∨ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).prvHp ≠ ∅ ∨ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).vretRefs ≠ (λ tid. null) ∨ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).pretRefs ≠ (λ tid. null) ∨ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).owns ≠ (λ r. None) ∨ (λ tid. idle) ≠ (λ tid. idle) ∨ (∃ tid. lsf(tid).tid ≠ tid) ⊦ ∃ s. DMSQinit(s)
Used terms: mkgs (vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)), lsf, λ tid. idle
| ⊦ DMSQinit(mkstate(gs, lsf, pcf)) ↔ (∃ r, val. r ≠ null ∧ gs.ps = ∅[r, mk(val, Some(dummytid), null)] ∧ gs.phead = r ∧ gs.vhead = r ∧ gs.vtail = r ∧ gs.orl = r ' ∧ gs.qrl = [] ∧ gs.vs = gs.ps) ∧ gs.vrvHp = ∅ ∧ gs.prvHp = ∅ ∧ gs.vretRefs = (λ tid. null) ∧ gs.pretRefs = (λ tid. null) ∧ gs.owns = (λ r. None) ∧ pcf = (λ tid. idle) ∧ (∀ tid. lsf(tid).tid = tid) |
| vs = ∅[vhead, mk(val, Some(dummytid), null)], vhead ≠ null, ∀ tid. lsf(tid).tid = tid, (∀ r, val. ¬ ( r ≠ null ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).ps = ∅[r, mk(val, Some(dummytid), null)] ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).phead = r ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).vhead = r ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).vtail = r ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).orl = r ' ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).qrl = [] ∧ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).vs = mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).ps)) ∨ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).vrvHp ≠ ∅ ∨ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).prvHp ≠ ∅ ∨ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).vretRefs ≠ (λ tid. null) ∨ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).pretRefs ≠ (λ tid. null) ∨ mkgs(vs, vs, vhead, vhead, vhead, λ tid. null, λ tid. null, ∅, ∅, [], vhead ', λ r. None, λ rvref. Pending(tid)).owns ≠ (λ r. None) ∨ (λ tid. idle) ≠ (λ tid. idle) ∨ (∃ tid. lsf(tid).tid ≠ tid) ⊦ ∃ s. DMSQinit(s) |
lsf(tid).tid ≠ tid, vhead ≠ null, ∀ tid. lsf(tid).tid = tid ⊦ ∃ s. DMSQinit(s)
Used simplifier rules: ⊦ 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) .pretRefs = vretRefs0; (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) .prvHp = vrvHp0; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .vrvHp = vrvHp; (s) ⊦ st[a, d0] = st[a, d1] ↔ d0 = d1; (s) ⊦ mkgs (ps, ps0, phead, phead0, phead1, vretRefs, vretRefs0, vrvHp, vrvHp0, qrl, qrl0, owns, rvowns) .ps = ps; (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) .qrl = qrl; (s) ⊦ a ' = b ' ↔ a = b; (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) .vtail = phead1; (s) ⊦ 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) .phead = phead; (s) ⊦ mk(val, opttid, nxt) = mk(val0, opttid0, nxt0) ↔ val = val0 ∧ opttid = opttid0 ∧ nxt = nxt0; (ws)
| lsf(tid).tid ≠ tid, vhead ≠ null, ∀ tid. lsf(tid).tid = tid ⊦ ∃ s. DMSQinit(s) |
lsf(tid) = mkls(tid0, val, optval, vhead0, nd, obsEmpty, vhead1, vhead2, rvref, optval0, vhead3, tid1, addr), tid0 ≠ tid, vhead ≠ null, ∀ tid. lsf(tid).tid = tid ⊦ ∃ s. DMSQinit(s)
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(tid), addr, tid0, lst, first, rvref, othertid, success, optval
| lsf(tid) = mkls(tid0, val, optval, vhead0, nd, obsEmpty, vhead1, vhead2, rvref, optval0, vhead3, tid1, addr), tid0 ≠ tid, vhead ≠ null, ∀ tid. lsf(tid).tid = tid ⊦ ∃ s. DMSQinit(s) |
Used simplifier rules: ⊦ mkls (tid, value, optval, node, nd, success, node0, node1, rvref, optval0, node2, tid0, rvref0) .tid = tid; (s) Used terms: tid
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.