[Imprint][Data Privacy Statement][E-Mail]

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,

Theorem base for Specification DMSQ-refines-DQ

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-runDMSQInv(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-sametidDMSQGInv(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-dodeqDMSQInv(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-invdeqDMSQInv(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-crashDMSQInv(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-dodeqemptyDMSQInv(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-retdeqDMSQInv(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-checkempDMSQInv(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-doenqDMSQInv(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-invenqDMSQInv(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-abstauren(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-othertidDMSQGInv(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-retenqDMSQInv(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