This is a listing of all goals defined over the current specification. Axioms are marked yellow, proved theorems green and unproved theorems blue. Click on individual names to get more information on the proof.
| Name: | Sequent: | Type: |
|---|---|---|
| exals-tidok | ⊦ ∃ als. als.tid = tid | A User Theorem |
| fwsim-step-run | DMSQInv(gs, lsf, pcf), DMSQstep(mkstate(gs, lsf, pcf), callRUN(tid), mkstate(gs0, lsf0, pcf0)), abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf)) ⊦ pre(mkgs(q), alsf(tid), apcf(tid), callRun(tid)) ∧ abs (mkstate(gs0, lsf0, pcf0), mkstate (gstepf(mkgs(q), alsf(tid), apcf(tid), callRun(tid)), alsf(tid; lstepf(mkgs(q), alsf(tid), apcf(tid), callRun(tid))), apcf(tid; pcstepf(mkgs(q), alsf(tid), apcf(tid), callRun(tid))))) | A User Theorem |
| pre-invDEQ | ⊦ pre(gs, ls, pc, invDEQ(tid)) ↔ pc = ready ∧ ls.tid = tid | A User Theorem |
| fwsim-tau-sametid | DMSQGInv(gs), DMSQLInv(gs, ls, pc), pre(gs, ls, pc, τ), absls(gs, ls, pc, als) ⊦ content(gstepf(gs, ls, pc, τ).qrl, gstepf(gs, ls, pc, τ).ps) = content(gs.qrl, gs.ps) ∧ abspc(gstepf(gs, ls, pc, τ), lstepf(gs, ls, pc, τ), pcstepf(gs, ls, pc, τ)) = abspc(gs, ls, pc) ∧ absls(gstepf(gs, ls, pc, τ), lstepf(gs, ls, pc, τ), pcstepf(gs, ls, pc, τ), als) | A User Theorem |
| pre-doDeqEmpty | ⊦ pre(gs, ls, pc, doDeqEmpty(tid)) ↔ pc = D14 ∧ ls.tid = tid | A User Theorem |
| fwsim-step-dodeq | DMSQInv(gs, lsf, pcf), DMSQstep(mkstate(gs, lsf, pcf), doDeq(tid), mkstate(gs0, lsf0, pcf0)), abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf)) ⊦ pre(mkgs(q), alsf(tid), apcf(tid), DoDeq(tid)) ∧ abs (mkstate(gs0, lsf0, pcf0), mkstate (gstepf(mkgs(q), alsf(tid), apcf(tid), DoDeq(tid)), alsf(tid; lstepf(mkgs(q), alsf(tid), apcf(tid), DoDeq(tid))), apcf(tid; pcstepf(mkgs(q), alsf(tid), apcf(tid), DoDeq(tid))))) | A User Theorem |
| fwsim-step-invdeq | DMSQInv(gs, lsf, pcf), DMSQstep(mkstate(gs, lsf, pcf), invDEQ(tid), mkstate(gs0, lsf0, pcf0)), abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf)) ⊦ pre(mkgs(q), alsf(tid), apcf(tid), InvDeq(tid)) ∧ abs (mkstate(gs0, lsf0, pcf0), mkstate (gstepf(mkgs(q), alsf(tid), apcf(tid), InvDeq(tid)), alsf(tid; lstepf(mkgs(q), alsf(tid), apcf(tid), InvDeq(tid))), apcf(tid; pcstepf(mkgs(q), alsf(tid), apcf(tid), InvDeq(tid))))) | A User Theorem |
| exlsf-tidok | ⊦ ∃ lsf. ∀ tid. lsf(tid).tid = tid | A User Theorem |
| pre-retDEQ | ⊦ pre(gs, ls, pc, retDEQ(tid, optval)) ↔ pc = D34 ∧ ls.tid = tid ∧ ls.optval = optval | A User Theorem |
| obsEmptyf | ⊦ obsEmptyf = obsEmptyf(tid; obsEmpty) ↔ obsEmptyf(tid) ↔ obsEmpty | A User Theorem |
| refines | ⊦ C_≤T_A(CIOAut(DMSQinit, DMSQstep), AIOAut(DQinit, DQstep)) | A User Theorem |
| fwsim-step-crash | DMSQInv(gs, lsf, pcf), DMSQstep(mkstate(gs, lsf, pcf), globalCRASH, mkstate(gs0, lsf0, pcf0)), abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf)) ⊦ abs(mkstate(gs0, lsf0, pcf0), mkstate(mkgs(q), alsf, λ tid. (apcf(tid) = idle ⊃ idle;crashed))) | A User Theorem |
| CIOAut-lem | ⊦ CIOAut?(CIOAut(DMSQinit, DMSQstep)) | A User Theorem |
| pre-doEnq | ⊦ pre(gs, ls, pc, doEnq(tid)) ↔ pc = E11 ∧ ls.tid = tid ∧ gs.ps[ls.lst].next ≠ gs.vs[ls.lst].next ∨ (pc = D16 ∨ pc = E14) ∧ gs.owns(ls.nxt).tid = tid ∧ ls.lst = (gs.orl + gs.qrl).last | A User Theorem |
| DMSQstep | ⊦ DMSQstep(cs, aa, cs0) ↔ (∃ a. aa = aabs(a) ∧ DMSQastep(cs, a, cs0)) | An Axiom |
| not-pre-FLUSHHEAD | ⊦ ¬ pre(gs, ls, pc, globalFLUSHHEAD) | A User Theorem |
| fwsim-step-dodeqempty | DMSQInv(gs, lsf, pcf), DMSQstep(mkstate(gs, lsf, pcf), doDeqEmpty(tid), mkstate(gs0, lsf0, pcf0)), abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf)) ⊦ pre(mkgs(q), alsf(tid), apcf(tid), DoDeqEmpty(tid)) ∧ abs (mkstate(gs0, lsf0, pcf0), mkstate (gstepf(mkgs(q), alsf(tid), apcf(tid), DoDeqEmpty(tid)), alsf(tid; lstepf(mkgs(q), alsf(tid), apcf(tid), DoDeqEmpty(tid))), apcf(tid; pcstepf(mkgs(q), alsf(tid), apcf(tid), DoDeqEmpty(tid))))) | A User Theorem |
| fwsim-step | ⊦ DMSQInv(gs, lsf, pcf) ∧ abs(mkstate(gs, lsf, pcf), as) ∧ DMSQastep(mkstate(gs, lsf, pcf), a, mkstate(gs0, lsf0, pcf0)) → (∃ as0. (a = τ ⊃ as0 = as;DQstep(as, a, as0)) ∧ abs(mkstate(gs0, lsf0, pcf0), as0)) | A User Theorem |
| pre-callRUN | ⊦ pre(gs, ls, pc, callRUN(tid)) ↔ pc = idle ∧ ls.tid = tid | A User Theorem |
| exls-tidok | ⊦ ∃ ls. ls.tid = tid | A User Theorem |
| fwsim-step-retdeq | DMSQInv(gs, lsf, pcf), DMSQstep(mkstate(gs, lsf, pcf), retDEQ(tid, optval), mkstate(gs0, lsf0, pcf0)), abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf)) ⊦ pre(mkgs(q), alsf(tid), apcf(tid), RetDeq(tid, optval)) ∧ abs (mkstate(gs0, lsf0, pcf0), mkstate (gstepf(mkgs(q), alsf(tid), apcf(tid), RetDeq(tid, optval)), alsf(tid; lstepf(mkgs(q), alsf(tid), apcf(tid), RetDeq(tid, optval))), apcf(tid; pcstepf(mkgs(q), alsf(tid), apcf(tid), RetDeq(tid, optval))))) | A User Theorem |
| pre-invENQ | ⊦ pre(gs, ls, pc, invENQ(tid, val)) ↔ pc = ready ∧ ls.tid = tid | A User Theorem |
| fwrefines | ⊦ ≤F(CIOAut(DMSQinit, DMSQstep), AIOAut(DQinit, DQstep)) | A User Theorem |
| fwsim | ⊦ fwsim(CIOAut(DMSQinit, DMSQstep), AIOAut(DQinit, DQstep), λ as, cs. abs(cs, as) ∧ DMSQInv(cs.gstate, cs.lsf, cs.pcf)) | A User Theorem |
| fwsim-step-checkemp | DMSQInv(gs, lsf, pcf), DMSQstep(mkstate(gs, lsf, pcf), checkEmp(tid), mkstate(gs0, lsf0, pcf0)), abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf)) ⊦ pre(mkgs(q), alsf(tid), apcf(tid), CheckEmp(tid)) ∧ abs (mkstate(gs0, lsf0, pcf0), mkstate (gstepf(mkgs(q), alsf(tid), apcf(tid), CheckEmp(tid)), alsf(tid; lstepf(mkgs(q), alsf(tid), apcf(tid), CheckEmp(tid))), apcf(tid; pcstepf(mkgs(q), alsf(tid), apcf(tid), CheckEmp(tid))))) | A User Theorem |
| AIOAut-lem | ⊦ AIOAut?(AIOAut(DQinit, DQstep)) | A User Theorem |
| DQstep | ⊦ DQstep(as, aa, as0) ↔ (∃ a. aa = aabs(a) ∧ DQstep(as, a, as0)) | An Axiom |
| not-pre-FLUSHVAL | ⊦ ¬ pre(gs, ls, pc, globalFLUSHVAL(r)) | A User Theorem |
| exalsf-tidok | ⊦ ∃ alsf. ∀ tid. alsf(tid).tid = tid | A User Theorem |
| fwsim-step-doenq | DMSQInv(gs, lsf, pcf), DMSQstep(mkstate(gs, lsf, pcf), doEnq(tid), mkstate(gs0, lsf0, pcf0)), abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf)) ⊦ pre(mkgs(q), alsf(tid), apcf(tid), DoEnq(tid)) ∧ abs (mkstate(gs0, lsf0, pcf0), mkstate (gstepf(mkgs(q), alsf(tid), apcf(tid), DoEnq(tid)), alsf(tid; lstepf(mkgs(q), alsf(tid), apcf(tid), DoEnq(tid))), apcf(tid; pcstepf(mkgs(q), alsf(tid), apcf(tid), DoEnq(tid))))) | A User Theorem |
| heap-updnxt-id | ⊦ ps[r].next = vs[r].next ∧ r ∈ ps → ps[r, ps[r].next:= vs[r].next] = ps | A User Theorem |
| fwsim-step-invenq | DMSQInv(gs, lsf, pcf), DMSQstep(mkstate(gs, lsf, pcf), invENQ(tid, val), mkstate(gs0, lsf0, pcf0)), abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf)) ⊦ pre(mkgs(q), alsf(tid), apcf(tid), InvEnq(tid, val)) ∧ abs (mkstate(gs0, lsf0, pcf0), mkstate (gstepf(mkgs(q), alsf(tid), apcf(tid), InvEnq(tid, val)), alsf(tid; lstepf(mkgs(q), alsf(tid), apcf(tid), InvEnq(tid, val))), apcf(tid; pcstepf(mkgs(q), alsf(tid), apcf(tid), InvEnq(tid, val))))) | A User Theorem |
| pre-retENQ | ⊦ pre(gs, ls, pc, retENQ(tid)) ↔ pc = E17 ∧ ls.tid = tid | A User Theorem |
| fwsim-init | ⊦ DMSQinit(cs) → (∃ as. abs(cs, as) ∧ DQinit(as)) | A User Theorem |
| fwsim-step-abstau | ren(ca) = τ, DMSQInv(gs, lsf, pcf), DMSQstep(mkstate(gs, lsf, pcf), ca, mkstate(gs0, lsf0, pcf0)), abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf)) ⊦ abs(mkstate(gs0, lsf0, pcf0), mkstate(mkgs(q), alsf, apcf)) | A User Theorem |
| fwsim-tau-othertid | DMSQGInv(gs), DMSQLInv(gs, ls, pc), DMSQLInv(gs, ls0, pc0), ls.tid ≠ ls0.tid, absls(gs, ls0, pc0, als), pre(gs, ls, pc, τ) ⊦ abspc(gstepf(gs, ls, pc, τ), ls0, pc0) = abspc(gs, ls0, pc0) ∧ absls(gstepf(gs, ls, pc, τ), ls0, pc0, als) | A User Theorem |
| pre-checkEmp | ⊦ pre(gs, ls, pc, checkEmp(tid)) ↔ pc = D9 ∧ ls.tid = tid ∧ gs.qrl = [] | A User Theorem |
| pre-doDeq | ⊦ pre(gs, ls, pc, doDeq(tid)) ↔ gs.ps[ls.nxt].deqID = None ∧ (pc = D21 ∧ ls.tid = tid ∨ pc = D28 ∧ ls.othertid = tid) | A User Theorem |
| fwsim-step-retenq | DMSQInv(gs, lsf, pcf), DMSQstep(mkstate(gs, lsf, pcf), retENQ(tid), mkstate(gs0, lsf0, pcf0)), abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf)) ⊦ pre(mkgs(q), alsf(tid), apcf(tid), RetEnq(tid)) ∧ abs (mkstate(gs0, lsf0, pcf0), mkstate (gstepf(mkgs(q), alsf(tid), apcf(tid), RetEnq(tid)), alsf(tid; lstepf(mkgs(q), alsf(tid), apcf(tid), RetEnq(tid))), apcf(tid; pcstepf(mkgs(q), alsf(tid), apcf(tid), RetEnq(tid))))) | A User Theorem |