| ⊦ listp(rl, vs, ps, owns) ∧ vs[rl.last].next ≠ null → listp(rl, vs, ps[vs[rl.last].next, ps[vs[rl.last].next].val:= vs[vs[rl.last].next].val], owns) |
vs[rl.last].next ≠ null, listp(rl, vs, ps, owns), ¬ listp(rl, vs, ps[vs[rl.last].next, ps[vs[rl.last].next].val:= vs[vs[rl.last].next].val], owns) ⊦
| vs[rl.last].next ≠ null, listp(rl, vs, ps, owns), ¬ listp(rl, vs, ps[vs[rl.last].next, ps[vs[rl.last].next].val:= vs[vs[rl.last].next].val], owns) ⊦ |
vs[vs[rl.last].next].deqID = None, vs[vs[rl.last].next].next = null, ps[vs[rl.last].next] = vs[vs[rl.last].next], vs[rl.last].next ≠ null, listp(rl, vs, ps, owns), weak?(owns(vs[rl.last].next)), vs[rl.last].next ∈ vs, vs[rl.last].next ∈ ps, ¬ listp(rl, vs, ps[vs[rl.last].next, vs[vs[rl.last].next].val:= vs[vs[rl.last].next].val], owns) ⊦
Used simplifier rules: 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
| vs[vs[rl.last].next].deqID = None, vs[vs[rl.last].next].next = null, ps[vs[rl.last].next] = vs[vs[rl.last].next], vs[rl.last].next ≠ null, listp(rl, vs, ps, owns), weak?(owns(vs[rl.last].next)), vs[rl.last].next ∈ vs, vs[rl.last].next ∈ ps, ¬ listp(rl, vs, ps[vs[rl.last].next, vs[vs[rl.last].next].val:= vs[vs[rl.last].next].val], owns) ⊦ |
vs[vs[(address + rl0).last].next].deqID = None, vs[vs[(address + rl0).last].next].next = null, ps[vs[(address + rl0).last].next] = vs[vs[(address + rl0).last].next], vs[(address + rl0).last].next ≠ null, listp(address + rl0, vs, ps, owns), weak?(owns(vs[(address + rl0).last].next)), vs[(address + rl0).last].next ∈ ps, vs[(address + rl0).last].next ∈ vs, ¬ listp(address + rl0, vs, ps[vs[(address + rl0).last].next, vs[vs[(address + rl0).last].next].val:= vs[vs[(address + rl0).last].next].val], owns), ∀ vs, ps, owns. ¬ ( vs[vs[rl0.last].next].deqID = None ∧ vs[vs[rl0.last].next].next = null ∧ ps[vs[rl0.last].next] = vs[vs[rl0.last].next] ∧ vs[rl0.last].next ≠ null ∧ listp(rl0, vs, ps, owns) ∧ weak?(owns(vs[rl0.last].next)) ∧ vs[rl0.last].next ∈ vs ∧ vs[rl0.last].next ∈ ps ∧ ¬ listp(rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns)) ⊦
Used simplifier rules: reflist freely generated by [], +;; ⊦ ¬ listp([], vs, ps, owns); (s)
| vs[vs[(address + rl0).last].next].deqID = None, vs[vs[(address + rl0).last].next].next = null, ps[vs[(address + rl0).last].next] = vs[vs[(address + rl0).last].next], vs[(address + rl0).last].next ≠ null, listp(address + rl0, vs, ps, owns), weak?(owns(vs[(address + rl0).last].next)), vs[(address + rl0).last].next ∈ ps, vs[(address + rl0).last].next ∈ vs, ¬ listp(address + rl0, vs, ps[vs[(address + rl0).last].next, vs[vs[(address + rl0).last].next].val:= vs[vs[(address + rl0).last].next].val], owns), ∀ vs, ps, owns. ¬ ( vs[vs[rl0.last].next].deqID = None ∧ vs[vs[rl0.last].next].next = null ∧ ps[vs[rl0.last].next] = vs[vs[rl0.last].next] ∧ vs[rl0.last].next ≠ null ∧ listp(rl0, vs, ps, owns) ∧ weak?(owns(vs[rl0.last].next)) ∧ vs[rl0.last].next ∈ vs ∧ vs[rl0.last].next ∈ ps ∧ ¬ listp(rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns)) ⊦ |
vs[vs[(address ' + rl0).last].next].deqID = None, vs[vs[(address ' + rl0).last].next].next = null, ps[vs[(address ' + rl0).last].next] = vs[vs[(address ' + rl0).last].next], vs[(address ' + rl0).last].next ≠ null, listp(address ' + rl0, vs, ps, owns), weak?(owns(vs[(address ' + rl0).last].next)), vs[(address ' + rl0).last].next ∈ ps, vs[(address ' + rl0).last].next ∈ vs, ¬ listp (address ' + rl0, vs, ps[vs[(address ' + rl0).last].next, vs[vs[(address ' + rl0).last].next].val:= vs[vs[(address ' + rl0).last].next].val], owns), ∀ vs0, ps0, owns0. vs0[vs0[rl0.last].next].deqID ≠ None ∨ vs0[vs0[rl0.last].next].next ≠ null ∨ ps0[vs0[rl0.last].next] ≠ vs0[vs0[rl0.last].next] ∨ vs0[rl0.last].next = null ∨ ¬ listp(rl0, vs0, ps0, owns0) ∨ ¬ weak?(owns0(vs0[rl0.last].next)) ∨ ¬ vs0[rl0.last].next ∈ vs0 ∨ ¬ vs0[rl0.last].next ∈ ps0 ∨ listp(rl0, vs0, ps0[vs0[rl0.last].next, vs0[vs0[rl0.last].next].val:= vs0[vs0[rl0.last].next].val], owns0) ⊦
Used simplifier rules: 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 ⊦ a + x = a ' + x; (s)
| vs[vs[(address ' + rl0).last].next].deqID = None, vs[vs[(address ' + rl0).last].next].next = null, ps[vs[(address ' + rl0).last].next] = vs[vs[(address ' + rl0).last].next], vs[(address ' + rl0).last].next ≠ null, listp(address ' + rl0, vs, ps, owns), weak?(owns(vs[(address ' + rl0).last].next)), vs[(address ' + rl0).last].next ∈ ps, vs[(address ' + rl0).last].next ∈ vs, ¬ listp (address ' + rl0, vs, ps[vs[(address ' + rl0).last].next, vs[vs[(address ' + rl0).last].next].val:= vs[vs[(address ' + rl0).last].next].val], owns), ∀ vs0, ps0, owns0. vs0[vs0[rl0.last].next].deqID ≠ None ∨ vs0[vs0[rl0.last].next].next ≠ null ∨ ps0[vs0[rl0.last].next] ≠ vs0[vs0[rl0.last].next] ∨ vs0[rl0.last].next = null ∨ ¬ listp(rl0, vs0, ps0, owns0) ∨ ¬ weak?(owns0(vs0[rl0.last].next)) ∨ ¬ vs0[rl0.last].next ∈ vs0 ∨ ¬ vs0[rl0.last].next ∈ ps0 ∨ listp(rl0, vs0, ps0[vs0[rl0.last].next, vs0[vs0[rl0.last].next].val:= vs0[vs0[rl0.last].next].val], owns0) ⊦ |
⊦ y ≠ [] → (x + y).last = y.last
vs[vs[(address ' + rl0).last].next].deqID = None, vs[vs[(address ' + rl0).last].next].next = null, ps[vs[(address ' + rl0).last].next] = vs[vs[(address ' + rl0).last].next], rl0 = [], vs[(address ' + rl0).last].next ≠ null, listp(address ' + rl0, vs, ps, owns), weak?(owns(vs[(address ' + rl0).last].next)), vs[(address ' + rl0).last].next ∈ vs, vs[(address ' + rl0).last].next ∈ ps, ¬ listp (address ' + rl0, vs, ps[vs[(address ' + rl0).last].next, vs[vs[(address ' + rl0).last].next].val:= vs[vs[(address ' + rl0).last].next].val], owns), ∀ vs0, ps0, owns0. vs0[vs0[rl0.last].next].deqID ≠ None ∨ vs0[vs0[rl0.last].next].next ≠ null ∨ ps0[vs0[rl0.last].next] ≠ vs0[vs0[rl0.last].next] ∨ vs0[rl0.last].next = null ∨ ¬ listp(rl0, vs0, ps0, owns0) ∨ ¬ weak?(owns0(vs0[rl0.last].next)) ∨ ¬ vs0[rl0.last].next ∈ vs0 ∨ ¬ vs0[rl0.last].next ∈ ps0 ∨ listp(rl0, vs0, ps0[vs0[rl0.last].next, vs0[vs0[rl0.last].next].val:= vs0[vs0[rl0.last].next].val], owns0) ⊦
vs[vs[rl0.last].next].deqID = None, vs[vs[rl0.last].next].next = null, ps[vs[rl0.last].next] = vs[vs[rl0.last].next], vs[rl0.last].next ≠ null, rl0 ≠ [], listp(address ' + rl0, vs, ps, owns), weak?(owns(vs[rl0.last].next)), vs[rl0.last].next ∈ vs, vs[rl0.last].next ∈ ps, ¬ listp(address ' + rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns), ∀ vs0, ps0, owns0. vs0[vs0[rl0.last].next].deqID ≠ None ∨ vs0[vs0[rl0.last].next].next ≠ null ∨ ps0[vs0[rl0.last].next] ≠ vs0[vs0[rl0.last].next] ∨ vs0[rl0.last].next = null ∨ ¬ listp(rl0, vs0, ps0, owns0) ∨ ¬ weak?(owns0(vs0[rl0.last].next)) ∨ ¬ vs0[rl0.last].next ∈ vs0 ∨ ¬ vs0[rl0.last].next ∈ ps0 ∨ listp(rl0, vs0, ps0[vs0[rl0.last].next, vs0[vs0[rl0.last].next].val:= vs0[vs0[rl0.last].next].val], owns0) ⊦
Used terms: address ', rl0
| ⊦ y ≠ [] → (x + y).last = y.last |
| vs[vs[(address ' + rl0).last].next].deqID = None, vs[vs[(address ' + rl0).last].next].next = null, ps[vs[(address ' + rl0).last].next] = vs[vs[(address ' + rl0).last].next], rl0 = [], vs[(address ' + rl0).last].next ≠ null, listp(address ' + rl0, vs, ps, owns), weak?(owns(vs[(address ' + rl0).last].next)), vs[(address ' + rl0).last].next ∈ vs, vs[(address ' + rl0).last].next ∈ ps, ¬ listp (address ' + rl0, vs, ps[vs[(address ' + rl0).last].next, vs[vs[(address ' + rl0).last].next].val:= vs[vs[(address ' + rl0).last].next].val], owns), ∀ vs0, ps0, owns0. vs0[vs0[rl0.last].next].deqID ≠ None ∨ vs0[vs0[rl0.last].next].next ≠ null ∨ ps0[vs0[rl0.last].next] ≠ vs0[vs0[rl0.last].next] ∨ vs0[rl0.last].next = null ∨ ¬ listp(rl0, vs0, ps0, owns0) ∨ ¬ weak?(owns0(vs0[rl0.last].next)) ∨ ¬ vs0[rl0.last].next ∈ vs0 ∨ ¬ vs0[rl0.last].next ∈ ps0 ∨ listp(rl0, vs0, ps0[vs0[rl0.last].next, vs0[vs0[rl0.last].next].val:= vs0[vs0[rl0.last].next].val], owns0) ⊦ |
vs[vs[address].next].deqID = None, ps[address].next = null, vs[vs[address].next].next = null, ps[address].val = vs[address].val, ps[vs[address].next] = vs[vs[address].next], owns(address) = None, vs[address].next ≠ null, address ≠ null, weak?(owns(vs[address].next)), address ∈ ps, address ∈ vs, vs[address].next ∈ vs, vs[address].next ∈ ps, address ∈ ps[vs[address].next, vs[vs[address].next].val:= vs[vs[address].next].val], ¬ weak?(vs[address].deqID), ps[address].deqID = vs[address].deqID ∨ ps[address].deqID = None ⊦ vs[vs[address].next].val:= vs[vs[address].next].val = vs[vs[address].next] ∧ ps[vs[address].next, vs[vs[address].next].val:= vs[vs[address].next].val][address].next = null ∧ ps[vs[address].next, vs[vs[address].next].val:= vs[vs[address].next].val][address].val = vs[address].val ∧ ( ps[vs[address].next, vs[vs[address].next].val:= vs[vs[address].next].val][address].deqID = vs[address].deqID ∨ ps[vs[address].next, vs[vs[address].next].val:= vs[vs[address].next].val][address].deqID = None)
Used simplifier rules: ⊦ a ∈ st[b, d] ↔ a = b ∨ a ∈ st; (ws) ⊦ ¬ listp([], vs, ps, owns); (s) ⊦ (nd.val:= val).next = nd.next; (s) ⊦ a = b → st[b, d][a] = d; (s) ⊦ (nd.val:= val).deqID = nd.deqID; (s) ⊦ a ∈ st[a, d]; (s) ⊦ listp(r ', vs, ps, owns) ↔ owns(r) = None ∧ r ∈ vs ∧ r ∈ ps ∧ r ≠ null ∧ ¬ weak?(vs[r].deqID) ∧ (ps[r].deqID = vs[r].deqID ∨ ps[r].deqID = None) ∧ ps[r].val = vs[r].val ∧ ps[r].next = null ∧ ( vs[r].next ≠ null → vs[r].next ∈ vs ∧ vs[r].next ∈ ps ∧ ps[vs[r].next] = vs[vs[r].next] ∧ ps[vs[r].next].deqID = None ∧ ps[vs[r].next].next = null ∧ weak?(owns(vs[r].next))); (s) ⊦ a '.last = a; (s) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] ⊦ x + [] = x; (s)
| vs[vs[address].next].deqID = None, ps[address].next = null, vs[vs[address].next].next = null, ps[address].val = vs[address].val, ps[vs[address].next] = vs[vs[address].next], owns(address) = None, vs[address].next ≠ null, address ≠ null, weak?(owns(vs[address].next)), address ∈ ps, address ∈ vs, vs[address].next ∈ vs, vs[address].next ∈ ps, address ∈ ps[vs[address].next, vs[vs[address].next].val:= vs[vs[address].next].val], ¬ weak?(vs[address].deqID), ps[address].deqID = vs[address].deqID ∨ ps[address].deqID = None ⊦ vs[vs[address].next].val:= vs[vs[address].next].val = vs[vs[address].next] ∧ ps[vs[address].next, vs[vs[address].next].val:= vs[vs[address].next].val][address].next = null ∧ ps[vs[address].next, vs[vs[address].next].val:= vs[vs[address].next].val][address].val = vs[address].val ∧ ( ps[vs[address].next, vs[vs[address].next].val:= vs[vs[address].next].val][address].deqID = vs[address].deqID ∨ ps[vs[address].next, vs[vs[address].next].val:= vs[vs[address].next].val][address].deqID = None) |
Used simplifier rules: ⊦ mk(val, opttid, nxt).deqID = opttid; (s) ⊦ mk(val, opttid, nxt).next = nxt; (s) ⊦ mk(val, opttid, nxt) = mk(val0, opttid0, nxt0) ↔ val = val0 ∧ opttid = opttid0 ∧ nxt = nxt0; (ws) ⊦ mk(val, opttid, nxt).val = val; (s) ⊦ st[a] = d ∧ a ∈ st → st[a, d] = st; (s)
| vs[vs[rl0.last].next].deqID = None, vs[vs[rl0.last].next].next = null, ps[vs[rl0.last].next] = vs[vs[rl0.last].next], vs[rl0.last].next ≠ null, rl0 ≠ [], listp(address ' + rl0, vs, ps, owns), weak?(owns(vs[rl0.last].next)), vs[rl0.last].next ∈ vs, vs[rl0.last].next ∈ ps, ¬ listp(address ' + rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns), ∀ vs0, ps0, owns0. vs0[vs0[rl0.last].next].deqID ≠ None ∨ vs0[vs0[rl0.last].next].next ≠ null ∨ ps0[vs0[rl0.last].next] ≠ vs0[vs0[rl0.last].next] ∨ vs0[rl0.last].next = null ∨ ¬ listp(rl0, vs0, ps0, owns0) ∨ ¬ weak?(owns0(vs0[rl0.last].next)) ∨ ¬ vs0[rl0.last].next ∈ vs0 ∨ ¬ vs0[rl0.last].next ∈ ps0 ∨ listp(rl0, vs0, ps0[vs0[rl0.last].next, vs0[vs0[rl0.last].next].val:= vs0[vs0[rl0.last].next].val], owns0) ⊦ |
vs[vs[rl0.last].next].deqID = None, vs[vs[rl0.last].next].next = null, ps[vs[rl0.last].next] = vs[vs[rl0.last].next], vs[rl0.last].next ≠ null, rl0 ≠ [], listp(address ' + rl0, vs, ps, owns), weak?(owns(vs[rl0.last].next)), vs[rl0.last].next ∈ ps, vs[rl0.last].next ∈ vs, ¬ listp(address ' + rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns), vs[vs[rl0.last].next].deqID ≠ None ∨ vs[vs[rl0.last].next].next ≠ null ∨ ps[vs[rl0.last].next] ≠ vs[vs[rl0.last].next] ∨ vs[rl0.last].next = null ∨ ¬ listp(rl0, vs, ps, owns) ∨ ¬ weak?(owns(vs[rl0.last].next)) ∨ ¬ vs[rl0.last].next ∈ vs ∨ ¬ vs[rl0.last].next ∈ ps ∨ listp(rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns) ⊦
Used terms: vs, ps, owns
| vs[vs[rl0.last].next].deqID = None, vs[vs[rl0.last].next].next = null, ps[vs[rl0.last].next] = vs[vs[rl0.last].next], vs[rl0.last].next ≠ null, rl0 ≠ [], listp(address ' + rl0, vs, ps, owns), weak?(owns(vs[rl0.last].next)), vs[rl0.last].next ∈ ps, vs[rl0.last].next ∈ vs, ¬ listp(address ' + rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns), vs[vs[rl0.last].next].deqID ≠ None ∨ vs[vs[rl0.last].next].next ≠ null ∨ ps[vs[rl0.last].next] ≠ vs[vs[rl0.last].next] ∨ vs[rl0.last].next = null ∨ ¬ listp(rl0, vs, ps, owns) ∨ ¬ weak?(owns(vs[rl0.last].next)) ∨ ¬ vs[rl0.last].next ∈ vs ∨ ¬ vs[rl0.last].next ∈ ps ∨ listp(rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns) ⊦ |
vs[vs[rl0.last].next].deqID = None, vs[vs[rl0.last].next].next = null, ps[vs[rl0.last].next] = vs[vs[rl0.last].next], vs[rl0.last].next ≠ null, rl0 ≠ [], listp(address ' + rl0, vs, ps, owns), weak?(owns(vs[rl0.last].next)), vs[rl0.last].next ∈ vs, vs[rl0.last].next ∈ ps, ¬ listp(address ' + rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns), ¬ listp(rl0, vs, ps, owns) ∨ listp(rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns) ⊦
| vs[vs[rl0.last].next].deqID = None, vs[vs[rl0.last].next].next = null, ps[vs[rl0.last].next] = vs[vs[rl0.last].next], vs[rl0.last].next ≠ null, rl0 ≠ [], listp(address ' + rl0, vs, ps, owns), weak?(owns(vs[rl0.last].next)), vs[rl0.last].next ∈ vs, vs[rl0.last].next ∈ ps, ¬ listp(address ' + rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns), ¬ listp(rl0, vs, ps, owns) ∨ listp(rl0, vs, ps[vs[rl0.last].next, vs[vs[rl0.last].next].val:= vs[vs[rl0.last].next].val], owns) ⊦ |
⊦ listp(rl + rl0, vs, ps, owns) → (listp(rl0, vs, ps, owns) ↔ rl0 ≠ [])
Used simplifier rules: ⊦ (nd.val:= val).next = nd.next; (s) ⊦ (nd.val:= val).deqID = nd.deqID; (s) ⊦ a = b → st[b, d][a] = d; (s) ⊦ a ∈ st[a, d]; (s) 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 ⊦ st[a] = d ∧ a ∈ st → st[a, d] = st; (s) Used terms: ps, address ', owns, rl0, vs
| ⊦ listp(rl + rl0, vs, ps, owns) → (listp(rl0, vs, ps, owns) ↔ rl0 ≠ []) |
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.