| Symbol | Specification | Kind | Type |
|---|
| # . | actionstream | f | actionlist → nat |
| # . | actionstream | f | actionstream → natinf |
| # . | DMSQ-refines-DurQ-instance | f | cstatelist → nat |
| # . | DMSQ-refines-DurQ-instance | f | cstatestream → natinf |
| # . | Node-heap | f | heap → nat |
| # . | reflist | f | reflist → nat |
| # . | retval-heap | f | rvHeap → nat |
| # . | retval-heap | f | rvSet → nat |
| # . | DMSQ-refines-DurQ-instance | f | astatelist → nat |
| # . | DMSQ-refines-DurQ-instance | f | astatestream → natinf |
| # . | list-data | f | list → nat |
| . ' | DMSQ-refines-DurQ-instance | f | absAction → actionlist |
| . ' | DMSQ-refines-DurQ-instance | f | DMSQState → cstatelist |
| . ' | reflist | f | Ref → reflist |
| . ' | DMSQ-refines-DurQ-instance | f | DurQState → astatelist |
| . ' | list | f | elem → list |
| . + . | nat-basic | f | nat × nat → nat |
| . + . | DMSQ-refines-DurQ-instance | f | absAction × actionlist → actionlist |
| . + . | actionstream | f | actionlist × actionlist → actionlist |
| . + . | DMSQ-refines-DurQ-instance | f | actionlist × absAction → actionlist |
| . + . | nat-inf | f | natinf × natinf → natinf |
| . + . | DMSQ-refines-DurQ-instance | f | absAction × actionstream → actionstream |
| . + . | actionstream | f | actionstream × actionstream → actionstream |
| . + . | DMSQ-refines-DurQ-instance | f | DMSQState × cstatelist → cstatelist |
| . + . | DMSQ-refines-DurQ-instance | f | cstatelist × cstatelist → cstatelist |
| . + . | DMSQ-refines-DurQ-instance | f | cstatelist × DMSQState → cstatelist |
| . + . | DMSQ-refines-DurQ-instance | f | DMSQState × cstatestream → cstatestream |
| . + . | DMSQ-refines-DurQ-instance | f | cstatestream × cstatestream → cstatestream |
| . + . | reflist | f | Ref × reflist → reflist |
| . + . | reflist | f | reflist × reflist → reflist |
| . + . | reflist | f | reflist × Ref → reflist |
| . + . | DMSQ-refines-DurQ-instance | f | DurQState × astatelist → astatelist |
| . + . | DMSQ-refines-DurQ-instance | f | astatelist × astatelist → astatelist |
| . + . | DMSQ-refines-DurQ-instance | f | astatelist × DurQState → astatelist |
| . + . | DMSQ-refines-DurQ-instance | f | DurQState × astatestream → astatestream |
| . + . | DMSQ-refines-DurQ-instance | f | astatestream × astatestream → astatestream |
| . + . | list-data | f | elem × list → list |
| . + . | list | f | list × list → list |
| . + . | list | f | list × elem → list |
| . ++ . | DMSQ-refines-DurQ-instance | f | actionlist × absAction → actionlist |
| . ++ . | DMSQ-refines-DurQ-instance | f | cstatelist × DMSQState → cstatelist |
| . ++ . | reflist | f | reflist × Ref → reflist |
| . ++ . | retval-heap | f | rvSet × rvRef → rvSet |
| . ++ . | DMSQ-refines-DurQ-instance | f | astatelist × DurQState → astatelist |
| . ++ . | list-dup | f | list × elem → list |
| . +1 | nat-basic | f | nat → nat |
| . +2 . | reflist | f | Ref × Ref → reflist |
| . +2 . | list | f | elem × elem → list |
| . +l . | DMSQ-refines-DurQ-instance | f | absAction × absAction → actionlist |
| . +l . | DMSQ-refines-DurQ-instance | f | DMSQState × DMSQState → cstatelist |
| . +l . | DMSQ-refines-DurQ-instance | f | DurQState × DurQState → astatelist |
| . - . | nat | pf | nat × nat → nat with λ n, m. n ≥ m |
| . -- . | Node-heap | f | heap × Ref → heap |
| . -- . | retval-heap | f | rvHeap × rvRef → rvHeap |
| . -- . | retval-heap | f | rvSet × rvRef → rvSet |
| . -1 | nat-basic | pf | nat → nat with λ n. n ≠ 0 |
| . -1l . | DMSQ-refines-DurQ-instance | f | actionlist × absAction → actionlist |
| . -1l . | DMSQ-refines-DurQ-instance | f | cstatelist × DMSQState → cstatelist |
| . -1l . | DMSQ-refines-DurQ-instance | f | astatelist × DurQState → astatelist |
| . -l . | DMSQ-refines-DurQ-instance | f | actionlist × absAction → actionlist |
| . -l . | DMSQ-refines-DurQ-instance | f | cstatelist × DMSQState → cstatelist |
| . -l . | DMSQ-refines-DurQ-instance | f | astatelist × DurQState → astatelist |
| . -p . | actionstream | f | actionlist × nat → actionlist |
| . -p . | DMSQ-refines-DurQ-instance | f | cstatelist × nat → cstatelist |
| . -p . | DMSQ-refines-DurQ-instance | f | astatelist × nat → astatelist |
| . .addr | DMSQ | f | DMSQLState → rvRef |
| . .addr:= . | DMSQ | f | DMSQLState × rvRef → DMSQLState |
| . .butlast | actionstream | pf | actionlist → actionlist with λ x. x ≠ [] |
| . .butlast | DMSQ-refines-DurQ-instance | pf | cstatelist → cstatelist with λ x. x ≠ [] |
| . .butlast | reflist | pf | reflist → reflist with λ x. x ≠ [] |
| . .butlast | DMSQ-refines-DurQ-instance | pf | astatelist → astatelist with λ x. x ≠ [] |
| . .butlast | list-last | pf | list → list with λ x. x ≠ [] |
| . .deqID | Node | f | Node → OptTid |
| . .deqID:= . | Node | f | Node × OptTid → Node |
| . .f | DMSQ-refines-DurQ-instance | pf | actionstream → nat → absAction with λ σ. λ m. ∃ nf. σ = ⌜nf⌝ |
| . .f | DMSQ-refines-DurQ-instance | pf | cstatestream → nat → DMSQState with λ σ. λ m. ∃ nf. σ = ⌜nf⌝ |
| . .f | DMSQ-refines-DurQ-instance | pf | astatestream → nat → DurQState with λ σ. λ m. ∃ nf. σ = ⌜nf⌝ |
| . .first | DMSQ | f | DMSQLState → Ref |
| . .first:= . | DMSQ | f | DMSQLState × Ref → DMSQLState |
| . .gstate | DMSQ | f | DMSQState → DMSQGState |
| . .gstate | DurQ | f | DurQState → DurQGState |
| . .gstate:= . | DMSQ | f | DMSQState × DMSQGState → DMSQState |
| . .gstate:= . | DurQ | f | DurQState × DurQGState → DurQState |
| . .head | reflist | pf | reflist → Ref with λ x. x ≠ [] |
| . .head | list-data | pf | list → elem with λ x. x ≠ [] |
| . .invENQvalue | DMSQ | pf | DMSQAction → elem with λ a. ∃ tid, invENQvalue. a = invENQ(tid, invENQvalue) |
| . .invFLUSHVALr | DMSQ | pf | DMSQAction → Ref with λ a. ∃ invFLUSHVALr. a = globalFLUSHVAL(invFLUSHVALr) |
| . .ival | DurQ | f | DurQLState → elem |
| . .ival:= . | DurQ | f | DurQLState × elem → DurQLState |
| . .l | actionstream | pf | actionstream → actionlist with λ σ. finp(σ) |
| . .l | DMSQ-refines-DurQ-instance | pf | cstatestream → cstatelist with λ σ. finp(σ) |
| . .l | DMSQ-refines-DurQ-instance | pf | astatestream → astatelist with λ σ. finp(σ) |
| . .last | DMSQ-refines-DurQ-instance | pf | actionlist → absAction with λ x. x ≠ [] |
| . .last | DMSQ-refines-DurQ-instance | pf | cstatelist → DMSQState with λ x. x ≠ [] |
| . .last | reflist | pf | reflist → Ref with λ x. x ≠ [] |
| . .last | DMSQ-refines-DurQ-instance | pf | astatelist → DurQState with λ x. x ≠ [] |
| . .last | list-last | pf | list → elem with λ x. x ≠ [] |
| . .lsf | DMSQ | f | DMSQState → Tid → DMSQLState |
| . .lsf | DurQ | f | DurQState → Tid → DurQLState |
| . .lsf:= . | DMSQ | f | DMSQState × (Tid → DMSQLState) → DMSQState |
| . .lsf:= . | DurQ | f | DurQState × (Tid → DurQLState) → DurQState |
| . .lst | DMSQ | f | DMSQLState → Ref |
| . .lst:= . | DMSQ | f | DMSQLState × Ref → DMSQLState |
| . .n | nat-inf | pf | natinf → nat with λ n∞. n∞ ≠ ∞ |
| . .nd | DMSQ | f | DMSQLState → Node |
| . .nd | DMSQ | pf | DMSQAction → Node with λ a. ∃ invFLUSHVALr, nd, success. a = chooseE1(invFLUSHVALr, nd, success) |
| . .nd:= . | DMSQ | f | DMSQLState × Node → DMSQLState |
| . .next | Node | f | Node → Ref |
| . .next:= . | Node | f | Node × Ref → Node |
| . .node | DMSQ | f | DMSQLState → Ref |
| . .node | DMSQ | pf | DMSQAction → Ref with λ a. ∃ invFLUSHVALr, nd, success. a = chooseE1(invFLUSHVALr, nd, success) |
| . .node:= . | DMSQ | f | DMSQLState × Ref → DMSQLState |
| . .nxt | DMSQ | f | DMSQLState → Ref |
| . .nxt:= . | DMSQ | f | DMSQLState × Ref → DMSQLState |
| . .optval | DMSQ | f | DMSQLState → OptElem |
| . .optval | DurQ | f | DurQLState → OptElem |
| . .optval | absAction | pf | absAction → OptElem with λ aa. ∃ tid, optval. aa = ResDEQ(tid, optval) |
| . .optval | DurQ | pf | DurQAction → OptElem with λ a. ∃ tid, optval. a = ARetDeq(tid, optval) |
| . .optval:= . | DMSQ | f | DMSQLState × OptElem → DMSQLState |
| . .optval:= . | DurQ | f | DurQLState × OptElem → DurQLState |
| . .optval0 | DMSQ | f | DMSQLState → OptElem |
| . .optval0 | DMSQ | pf | DMSQAction → OptElem with λ a. ∃ rvref, retDEQoptval. a = chooseD2(rvref, retDEQoptval) |
| . .optval0:= . | DMSQ | f | DMSQLState × OptElem → DMSQLState |
| . .orl | DMSQ | f | DMSQGState → reflist |
| . .orl:= . | DMSQ | f | DMSQGState × reflist → DMSQGState |
| . .othertid | DMSQ | f | DMSQLState → Tid |
| . .othertid:= . | DMSQ | f | DMSQLState × Tid → DMSQLState |
| . .oval | DurQ | f | DurQLState → OptElem |
| . .oval:= . | DurQ | f | DurQLState × OptElem → DurQLState |
| . .owns | DMSQ | f | DMSQGState → Ref → OptTid |
| . .owns:= . | DMSQ | f | DMSQGState × (Ref → OptTid) → DMSQGState |
| . .pcf | DMSQ | f | DMSQState → Tid → DMSQPC |
| . .pcf | DurQ | f | DurQState → Tid → DurQPC |
| . .pcf:= . | DMSQ | f | DMSQState × (Tid → DMSQPC) → DMSQState |
| . .pcf:= . | DurQ | f | DurQState × (Tid → DurQPC) → DurQState |
| . .pending? | rvowner | p | rvOwner |
| . .phead | DMSQ | f | DMSQGState → Ref |
| . .phead:= . | DMSQ | f | DMSQGState × Ref → DMSQGState |
| . .pretRefs | DMSQ | f | DMSQGState → Tid → rvRef |
| . .pretRefs:= . | DMSQ | f | DMSQGState × (Tid → rvRef) → DMSQGState |
| . .prvHp | DMSQ | f | DMSQGState → rvHeap |
| . .prvHp:= . | DMSQ | f | DMSQGState × rvHeap → DMSQGState |
| . .ps | DMSQ | f | DMSQGState → heap |
| . .ps:= . | DMSQ | f | DMSQGState × heap → DMSQGState |
| . .qrl | DMSQ | f | DMSQGState → reflist |
| . .qrl:= . | DMSQ | f | DMSQGState × reflist → DMSQGState |
| . .queue | DurQ | f | DurQGState → list |
| . .queue:= . | DurQ | f | DurQGState × list → DurQGState |
| . .retDEQoptval | DMSQ | pf | DMSQAction → OptElem with λ a. ∃ tid, retDEQoptval. a = retDEQ(tid, retDEQoptval) |
| . .rvowns | DMSQ | f | DMSQGState → rvRef → rvOwner |
| . .rvowns:= . | DMSQ | f | DMSQGState × (rvRef → rvOwner) → DMSQGState |
| . .rvref | DMSQ | f | DMSQLState → rvRef |
| . .rvref | DMSQ | pf | DMSQAction → rvRef with λ a. ∃ rvref, retDEQoptval. a = chooseD2(rvref, retDEQoptval) |
| . .rvref:= . | DMSQ | f | DMSQLState × rvRef → DMSQLState |
| . .start | DMSQ-refines-DurQ-instance | f | CIOAutomaton → DMSQState → bool |
| . .start | DMSQ-refines-DurQ-instance | f | AIOAutomaton → DurQState → bool |
| . .step | DMSQ-refines-DurQ-instance | f | CIOAutomaton → DMSQState × absAction × DMSQState → bool |
| . .step | DMSQ-refines-DurQ-instance | f | AIOAutomaton → DurQState × absAction × DurQState → bool |
| . .success | DMSQ | p | DMSQLState |
| . .success | DMSQ | pp | DMSQAction with λ a. ∃ invFLUSHVALr, nd, success. a = chooseE1(invFLUSHVALr, nd, success) |
| . .success:= . | DMSQ | f | DMSQLState × bool → DMSQLState |
| . .tail | reflist | pf | reflist → reflist with λ x. x ≠ [] |
| . .tail | list-data | pf | list → list with λ x. x ≠ [] |
| . .tid | rvowner | f | rvOwner → Tid |
| . .tid | DMSQ | f | DMSQLState → Tid |
| . .tid | DurQ | f | DurQLState → Tid |
| . .tid | opttid | pf | OptTid → Tid with λ opttid. weak?(opttid) ∨ some?(opttid) |
| . .tid | DMSQ | pf | DMSQAction → Tid with λ a.
(∃ tid. a = retENQ(tid))
∨ (∃ tid, retDEQoptval. a = retDEQ(tid, retDEQoptval))
∨ (∃ tid, invENQvalue. a = invENQ(tid, invENQvalue))
∨ (∃ tid. a = invDEQ(tid)) ∨ (∃ tid. a = doEnq(tid))
∨ (∃ tid. a = doDeqEmpty(tid)) ∨ (∃ tid. a = doDeq(tid))
∨ (∃ tid. a = checkEmp(tid)) ∨ (∃ tid. a = callRUN(tid)) |
| . .tid | absAction | pf | absAction → Tid with λ aa. aa ≠ globalCRASH ∧ aa ≠ τ |
| . .tid | DurQ | pf | DurQAction → Tid with λ a. a ≠ τ ∧ a ≠ globalACrash |
| . .tid:= . | DMSQ | f | DMSQLState × Tid → DMSQLState |
| . .tid:= . | DurQ | f | DurQLState × Tid → DurQLState |
| . .tid:= . | opttid | pf | OptTid × Tid → OptTid with λ opttid, tid. weak?(opttid) ∨ some?(opttid) |
| . .val | Node | f | Node → elem |
| . .val | optelem | pf | OptElem → elem with λ optval. optval ≠ Empty |
| . .val | rvowner | pf | rvOwner → elem with λ ow. ∃ tid, val. ow = Claimed(tid, val) |
| . .val | absAction | pf | absAction → elem with λ aa. ∃ tid, val. aa = InvENQ(tid, val) |
| . .val | DurQ | pf | DurQAction → elem with λ a. ∃ tid, val. a = AInvEnq(tid, val) |
| . .val:= . | Node | f | Node × elem → Node |
| . .value | DMSQ | f | DMSQLState → elem |
| . .value | DurQ | f | DurQLState → elem |
| . .value:= . | DMSQ | f | DMSQLState × elem → DMSQLState |
| . .value:= . | DurQ | f | DurQLState × elem → DurQLState |
| . .vhead | DMSQ | f | DMSQGState → Ref |
| . .vhead:= . | DMSQ | f | DMSQGState × Ref → DMSQGState |
| . .vretRefs | DMSQ | f | DMSQGState → Tid → rvRef |
| . .vretRefs:= . | DMSQ | f | DMSQGState × (Tid → rvRef) → DMSQGState |
| . .vrvHp | DMSQ | f | DMSQGState → rvHeap |
| . .vrvHp:= . | DMSQ | f | DMSQGState × rvHeap → DMSQGState |
| . .vs | DMSQ | f | DMSQGState → heap |
| . .vs:= . | DMSQ | f | DMSQGState × heap → DMSQGState |
| . .vtail | DMSQ | f | DMSQGState → Ref |
| . .vtail:= . | DMSQ | f | DMSQGState × Ref → DMSQGState |
| . < . | nat-basic | p | nat × nat |
| . < . | actionstream | p | actionlist × actionlist |
| . < . | nat-inf | p | natinf × natinf |
| . < . | DMSQ-refines-DurQ-instance | p | cstatelist × cstatelist |
| . < . | reflist | p | reflist × reflist |
| . < . | DMSQ-refines-DurQ-instance | p | astatelist × astatelist |
| . < . | list-data | p | list × list |
| . > . | nat | p | nat × nat |
| . [ . ] | Node-heap | f | heap × Ref × Node → heap |
| . [ . ] | retval-heap | f | rvHeap × rvRef × OptElem → rvHeap |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | actionlist × nat → absAction with λ x, n. n < # x |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | actionlist × nat × absAction → actionlist with λ x, n, a. n < # x |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | actionstream × nat → absAction with λ σ, n. finp(σ) → ⌜n⌝ < # σ |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | actionstream × nat × absAction → actionstream with λ σ, n, a. finp(σ) → ⌜n⌝ < # σ |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | cstatelist × nat → DMSQState with λ x, n. n < # x |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | cstatelist × nat × DMSQState → cstatelist with λ x, n, a. n < # x |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | cstatestream × nat → DMSQState with λ σ, n. finp(σ) → ⌜n⌝ < # σ |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | cstatestream × nat × DMSQState → cstatestream with λ σ, n, a. finp(σ) → ⌜n⌝ < # σ |
| . [ . ] | Node-heap | pf | heap × Ref → Node with λ st, a. a ∈ st |
| . [ . ] | retval-heap | pf | rvHeap × rvRef → OptElem with λ st, a. a ∈ st |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | astatelist × nat → DurQState with λ x, n. n < # x |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | astatelist × nat × DurQState → astatelist with λ x, n, a. n < # x |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | astatestream × nat → DurQState with λ σ, n. finp(σ) → ⌜n⌝ < # σ |
| . [ . ] | DMSQ-refines-DurQ-instance | pf | astatestream × nat × DurQState → astatestream with λ σ, n, a. finp(σ) → ⌜n⌝ < # σ |
| . \ . | retval-heap | f | rvSet × rvSet → rvSet |
| . \ . | retval-heap | f | rvHeap × rvSet → rvHeap |
| . ^ | remtau | f | actionstream → actionstream |
| . | . | retval-heap | f | rvHeap × rvSet → rvHeap |
| . ∈ . | DMSQ-refines-DurQ-instance | p | absAction × actionlist |
| . ∈ . | DMSQ-refines-DurQ-instance | p | DMSQState × cstatelist |
| . ∈ . | Node-heap | p | Ref × heap |
| . ∈ . | reflist | p | Ref × reflist |
| . ∈ . | retval-heap | p | rvRef × rvHeap |
| . ∈ . | retval-heap | p | rvRef × rvSet |
| . ∈ . | retval-heap | p | OptElem × rvHeap |
| . ∈ . | DMSQ-refines-DurQ-instance | p | DurQState × astatelist |
| . ∈ . | list | p | elem × list |
| . ∩ . | retval-heap | f | rvSet × rvSet → rvSet |
| . ∪ . | retval-heap | f | rvSet × rvSet → rvSet |
| . ≤ . | nat | p | nat × nat |
| . ≤ . | actionstream | p | actionstream × actionstream |
| . ≤ . | DMSQ-refines-DurQ-instance | p | cstatestream × cstatestream |
| . ≤ . | DMSQ-refines-DurQ-instance | p | astatestream × astatestream |
| . ≥ . | nat | p | nat × nat |
| . ⊆ . | Node-heap | p | heap × heap |
| . ⊆ . | retval-heap | p | rvHeap × rvHeap |
| . ⊆ . | retval-heap | p | rvSet × rvSet |
| . ⊑ . | actionstream | p | actionlist × actionlist |
| . ⊑ . | DMSQ-refines-DurQ-instance | p | cstatelist × cstatelist |
| . ⊑ . | reflist | p | reflist × reflist |
| . ⊑ . | DMSQ-refines-DurQ-instance | p | astatelist × astatelist |
| . ⊑ . | list-last | p | list × list |
| . ⊒ . | actionstream | p | actionlist × actionlist |
| . ⊒ . | DMSQ-refines-DurQ-instance | p | cstatelist × cstatelist |
| . ⊒ . | reflist | p | reflist × reflist |
| . ⊒ . | DMSQ-refines-DurQ-instance | p | astatelist × astatelist |
| . ⊒ . | list-last | p | list × list |
| . ⊕ . | retval-heap | f | rvHeap × rvHeap → rvHeap |
| . ⊕ . | DMSQ | f | heap × heap → heap |
| . from . | DMSQ-refines-DurQ-instance | f | (nat → absAction) × nat → nat → absAction |
| . from . | DMSQ-refines-DurQ-instance | f | (nat → DMSQState) × nat → nat → DMSQState |
| . from . | DMSQ | f | reflist × Ref → reflist |
| . from . | DMSQ-refines-DurQ-instance | f | (nat → DurQState) × nat → nat → DurQState |
| . from . | actionstream | pf | actionstream × nat → actionstream with λ σ, n. finp(σ) → ⌜n⌝ < # σ ∨ ⌜n⌝ = # σ |
| . from . | actionstream | pf | actionlist × nat → actionlist with λ x, n. n ≤ # x |
| . from . | DMSQ-refines-DurQ-instance | pf | cstatestream × nat → cstatestream with λ σ, n. finp(σ) → ⌜n⌝ < # σ ∨ ⌜n⌝ = # σ |
| . from . | DMSQ-refines-DurQ-instance | pf | cstatelist × nat → cstatelist with λ x, n. n ≤ # x |
| . from . | DMSQ-refines-DurQ-instance | pf | astatestream × nat → astatestream with λ σ, n. finp(σ) → ⌜n⌝ < # σ ∨ ⌜n⌝ = # σ |
| . from . | DMSQ-refines-DurQ-instance | pf | astatelist × nat → astatelist with λ x, n. n ≤ # x |
| . to . | DMSQ-refines-DurQ-instance | f | (nat → absAction) × nat → actionlist |
| . to . | DMSQ-refines-DurQ-instance | f | (nat → DMSQState) × nat → cstatelist |
| . to . | DMSQ-refines-DurQ-instance | f | (nat → DurQState) × nat → astatelist |
| . to . | actionstream | pf | actionstream × nat → actionstream with λ σ, n. finp(σ) → ⌜n⌝ < # σ ∨ ⌜n⌝ = # σ |
| . to . | actionstream | pf | actionlist × nat → actionlist with λ x, n. n ≤ # x |
| . to . | DMSQ-refines-DurQ-instance | pf | cstatestream × nat → cstatestream with λ σ, n. finp(σ) → ⌜n⌝ < # σ ∨ ⌜n⌝ = # σ |
| . to . | DMSQ-refines-DurQ-instance | pf | cstatelist × nat → cstatelist with λ x, n. n ≤ # x |
| . to . | DMSQ-refines-DurQ-instance | pf | astatestream × nat → astatestream with λ σ, n. finp(σ) → ⌜n⌝ < # σ ∨ ⌜n⌝ = # σ |
| . to . | DMSQ-refines-DurQ-instance | pf | astatelist × nat → astatelist with λ x, n. n ≤ # x |
| . to∞ . | actionstream | pf | actionstream × natinf → actionstream with λ σ, n∞. finp(σ) → n∞ < # σ ∨ n∞ = # σ |
| . to∞ . | DMSQ-refines-DurQ-instance | pf | cstatestream × natinf → cstatestream with λ σ, n∞. finp(σ) → n∞ < # σ ∨ n∞ = # σ |
| . to∞ . | DMSQ-refines-DurQ-instance | pf | astatestream × natinf → astatestream with λ σ, n∞. finp(σ) → n∞ < # σ ∨ n∞ = # σ |
| [] | actionstream | c | actionlist |
| [] | actionstream | c | actionstream |
| [] | DMSQ-refines-DurQ-instance | c | cstatelist |
| [] | DMSQ-refines-DurQ-instance | c | cstatestream |
| [] | reflist | c | reflist |
| [] | DMSQ-refines-DurQ-instance | c | astatelist |
| [] | DMSQ-refines-DurQ-instance | c | astatestream |
| [] | list-data | c | list |
| { . } | retval-heap | f | rvRef → rvSet |
| τ | DMSQ | c | DMSQAction |
| τ | absAction | c | absAction |
| τ | DurQ | c | DurQAction |
| ∅ | Node-heap | c | heap |
| ∅ | retval-heap | c | rvHeap |
| ∅ | retval-heap | c | rvSet |
| ∞ | nat-inf | c | natinf |
| ⌜ . ⌝ | actionstream | f | actionlist → actionstream |
| ⌜ . ⌝ | DMSQ-refines-DurQ-instance | f | (nat → absAction) → actionstream |
| ⌜ . ⌝ | nat-inf | f | nat → natinf |
| ⌜ . ⌝ | DMSQ-refines-DurQ-instance | f | cstatelist → cstatestream |
| ⌜ . ⌝ | DMSQ-refines-DurQ-instance | f | (nat → DMSQState) → cstatestream |
| ⌜ . ⌝ | DMSQ-refines-DurQ-instance | f | astatelist → astatestream |
| ⌜ . ⌝ | DMSQ-refines-DurQ-instance | f | (nat → DurQState) → astatestream |
| ACrash | DurQ | pr | : (Tid → DurQPC) |
| ADODEQ | DurQ | pr | : OptElem × list |
| ADOENQ | DurQ | pr | elem : list |
| ADoDeq | DurQ | f | Tid → DurQAction |
| ADoEnq | DurQ | f | Tid → DurQAction |
| AINVDEQ | DurQ | pr | : |
| AINVENQ | DurQ | pr | elem : elem |
| AIOAut | DMSQ-refines-DurQ-instance | f | (DurQState → bool) × (DurQState × absAction × DurQState → bool) → AIOAutomaton |
| AIOAut? | DMSQ-refines-DurQ-instance | p | AIOAutomaton |
| AIOAutomaton | DMSQ-refines-DurQ-instance | s | |
| AInvDeq | DurQ | f | Tid → DurQAction |
| AInvEnq | DurQ | f | Tid × elem → DurQAction |
| ARETDEQ | DurQ | pr | OptElem : : OptElem |
| ARETENQ | DurQ | pr | : |
| ARetDeq | DurQ | f | Tid × OptElem → DurQAction |
| ARetEnq | DurQ | f | Tid → DurQAction |
| ARun | DurQ | pr | : |
| CIOAut | DMSQ-refines-DurQ-instance | f | (DMSQState → bool) × (DMSQState × absAction × DMSQState → bool) → CIOAutomaton |
| CIOAut? | DMSQ-refines-DurQ-instance | p | CIOAutomaton |
| CIOAutomaton | DMSQ-refines-DurQ-instance | s | |
| CRASH | DMSQ | pr | heap × Ref × (Tid → rvRef) × rvHeap
: heap × Ref × Ref × (Tid → rvRef) × rvHeap × (Ref → OptTid) × (Tid → DMSQPC) |
| CallRUN | absAction | f | Tid → absAction |
| Claimed | rvowner | f | Tid × elem → rvOwner |
| D1 | DMSQ | c | DMSQPC |
| D10 | DMSQ | c | DMSQPC |
| D11 | DMSQ | c | DMSQPC |
| D12 | DMSQ | c | DMSQPC |
| D13 | DMSQ | c | DMSQPC |
| D14 | DMSQ | c | DMSQPC |
| D15 | DMSQ | c | DMSQPC |
| D16 | DMSQ | c | DMSQPC |
| D17 | DMSQ | c | DMSQPC |
| D18 | DMSQ | c | DMSQPC |
| D19 | DMSQ | c | DMSQPC |
| D2 | DMSQ | c | DMSQPC |
| D20 | DMSQ | c | DMSQPC |
| D21 | DMSQ | c | DMSQPC |
| D22 | DMSQ | c | DMSQPC |
| D23 | DMSQ | c | DMSQPC |
| D24 | DMSQ | c | DMSQPC |
| D25 | DMSQ | c | DMSQPC |
| D26 | DMSQ | c | DMSQPC |
| D27 | DMSQ | c | DMSQPC |
| D28 | DMSQ | c | DMSQPC |
| D29 | DMSQ | c | DMSQPC |
| D3 | DMSQ | c | DMSQPC |
| D30 | DMSQ | c | DMSQPC |
| D31 | DMSQ | c | DMSQPC |
| D32 | DMSQ | c | DMSQPC |
| D33 | DMSQ | c | DMSQPC |
| D34 | DMSQ | c | DMSQPC |
| D4 | DMSQ | c | DMSQPC |
| D5 | DMSQ | c | DMSQPC |
| D6 | DMSQ | c | DMSQPC |
| D7 | DMSQ | c | DMSQPC |
| D8 | DMSQ | c | DMSQPC |
| D9 | DMSQ | c | DMSQPC |
| DMSQAction | DMSQ | s | |
| DMSQGInv | DMSQ | p | DMSQGState |
| DMSQGState | DMSQ | s | |
| DMSQInv | DMSQ | p | DMSQGState × (Tid → DMSQLState) × (Tid → DMSQPC) |
| DMSQLInv | DMSQ | p | DMSQGState × DMSQLState × DMSQPC |
| DMSQLState | DMSQ | s | |
| DMSQPC | DMSQ | s | |
| DMSQRely | DMSQ | p | DMSQGState × Tid × DMSQGState |
| DMSQState | DMSQ | s | |
| DMSQstep | DMSQ | p | DMSQState × DMSQAction × DMSQState |
| DurQAction | DurQ | s | |
| DurQGInv | DurQ | p | DurQGState |
| DurQGState | DurQ | s | |
| DurQInv | DurQ | p | DurQGState × (Tid → DurQLState) × (Tid → DurQPC) |
| DurQLInv | DurQ | p | DurQGState × DurQLState × DurQPC |
| DurQLState | DurQ | s | |
| DurQPC | DurQ | s | |
| DurQState | DurQ | s | |
| DurQstep | DurQ | p | DurQState × DurQAction × DurQState |
| E1 | DMSQ | c | DMSQPC |
| E10 | DMSQ | c | DMSQPC |
| E11 | DMSQ | c | DMSQPC |
| E12 | DMSQ | c | DMSQPC |
| E13 | DMSQ | c | DMSQPC |
| E14 | DMSQ | c | DMSQPC |
| E15 | DMSQ | c | DMSQPC |
| E16 | DMSQ | c | DMSQPC |
| E17 | DMSQ | c | DMSQPC |
| E2 | DMSQ | c | DMSQPC |
| E3 | DMSQ | c | DMSQPC |
| E4 | DMSQ | c | DMSQPC |
| E5 | DMSQ | c | DMSQPC |
| E6 | DMSQ | c | DMSQPC |
| E7 | DMSQ | c | DMSQPC |
| E8 | DMSQ | c | DMSQPC |
| E9 | DMSQ | c | DMSQPC |
| Empty | optelem | c | OptElem |
| FLUSHHEAD | DMSQ | pr | Ref : Ref |
| FLUSHNEXT | DMSQ | pr | Ref × heap × reflist : heap × reflist × (Ref → OptTid) |
| FLUSHOPTTID | DMSQ | pr | Ref × heap : heap × reflist × reflist |
| FLUSHRETREF | DMSQ | pr | Tid × (Tid → rvRef) : (Tid → rvRef) |
| FLUSHRVHP | DMSQ | pr | rvRef × rvHeap : rvHeap |
| FLUSHVAL | DMSQ | pr | Ref × heap : heap |
| InvDEQ | absAction | f | Tid → absAction |
| InvENQ | absAction | f | Tid × elem → absAction |
| Node | Node | s | |
| None | opttid | c | OptTid |
| OptElem | optelem | s | |
| OptTid | opttid | s | |
| Pending | rvowner | f | Tid → rvOwner |
| RUN | DMSQ | pr | : |
| Ref | Ref | s | |
| ResDEQ | absAction | f | Tid × OptElem → absAction |
| ResENQ | absAction | f | Tid → absAction |
| Some | opttid | f | Tid → OptTid |
| Tid | tid | s | |
| Val | optelem | f | elem → OptElem |
| Weak | opttid | f | Tid → OptTid |
| absAction | absAction | s | |
| actionlist | actionstream | s | |
| actionstream | actionstream | s | |
| aexec | DMSQ-refines-DurQ-instance | f | AIOAutomaton → astatestream × actionstream → bool |
| aexec* | DMSQ-refines-DurQ-instance | f | AIOAutomaton → astatestream × actionstream → bool |
| aexecω | DMSQ-refines-DurQ-instance | f | AIOAutomaton → astatestream × actionstream → bool |
| afrag | DMSQ-refines-DurQ-instance | f | AIOAutomaton → astatestream × actionstream → bool |
| afrag* | DMSQ-refines-DurQ-instance | f | AIOAutomaton → astatestream × actionstream → bool |
| afragω | DMSQ-refines-DurQ-instance | f | AIOAutomaton → astatestream × actionstream → bool |
| allocrv | DMSQ | p | (Tid → rvRef) × rvHeap |
| amove | DMSQ-refines-DurQ-instance | f | AIOAutomaton → DurQState × actionstream × DurQState → bool |
| astatelist | DMSQ-refines-DurQ-instance | s | |
| astatestream | DMSQ-refines-DurQ-instance | s | |
| atrace | DMSQ-refines-DurQ-instance | f | AIOAutomaton → actionstream → bool |
| atrace* | DMSQ-refines-DurQ-instance | f | AIOAutomaton → actionstream → bool |
| atraceω | DMSQ-refines-DurQ-instance | f | AIOAutomaton → actionstream → bool |
| butlastn | actionstream | pf | nat × actionlist → actionlist with λ n, x. n ≤ # x |
| butlastn | DMSQ-refines-DurQ-instance | pf | nat × cstatelist → cstatelist with λ n, x. n ≤ # x |
| butlastn | reflist | pf | nat × reflist → reflist with λ n, x. n ≤ # x |
| butlastn | DMSQ-refines-DurQ-instance | pf | nat × astatelist → astatelist with λ n, x. n ≤ # x |
| butlastn | list-last | pf | nat × list → list with λ n, x. n ≤ # x |
| callARun | DurQ | f | Tid → DurQAction |
| callRUN | DMSQ | f | Tid → DMSQAction |
| cexec | DMSQ-refines-DurQ-instance | f | CIOAutomaton → cstatestream × actionstream → bool |
| cexec* | DMSQ-refines-DurQ-instance | f | CIOAutomaton → cstatestream × actionstream → bool |
| cexecω | DMSQ-refines-DurQ-instance | f | CIOAutomaton → cstatestream × actionstream → bool |
| cfrag | DMSQ-refines-DurQ-instance | f | CIOAutomaton → cstatestream × actionstream → bool |
| cfrag* | DMSQ-refines-DurQ-instance | f | CIOAutomaton → cstatestream × actionstream → bool |
| cfragω | DMSQ-refines-DurQ-instance | f | CIOAutomaton → cstatestream × actionstream → bool |
| checkEmp | DMSQ | f | Tid → DMSQAction |
| chooseD2 | DMSQ | f | rvRef × OptElem → DMSQAction |
| chooseE1 | DMSQ | f | Ref × Node × bool → DMSQAction |
| cmove | DMSQ-refines-DurQ-instance | f | CIOAutomaton → DMSQState × actionstream × DMSQState → bool |
| crashed | DMSQ | c | DMSQPC |
| crashed | DurQ | c | DurQPC |
| cstatelist | DMSQ-refines-DurQ-instance | s | |
| cstatestream | DMSQ-refines-DurQ-instance | s | |
| ctrace | DMSQ-refines-DurQ-instance | f | CIOAutomaton → actionstream → bool |
| ctrace* | DMSQ-refines-DurQ-instance | f | CIOAutomaton → actionstream → bool |
| ctraceω | DMSQ-refines-DurQ-instance | f | CIOAutomaton → actionstream → bool |
| disj | actionstream | p | actionlist × actionlist |
| disj | DMSQ-refines-DurQ-instance | p | cstatelist × cstatelist |
| disj | reflist | p | reflist × reflist |
| disj | DMSQ-refines-DurQ-instance | p | astatelist × astatelist |
| disj | list-dup | p | list × list |
| doDeq | DMSQ | f | Tid → DMSQAction |
| doDeqEmpty | DMSQ | f | Tid → DMSQAction |
| doEnq | DMSQ | f | Tid → DMSQAction |
| dom . | retval-heap | f | rvHeap → rvSet |
| dummytid | tid | c | Tid |
| dups | actionstream | p | actionlist |
| dups | DMSQ-refines-DurQ-instance | p | cstatelist |
| dups | reflist | p | reflist |
| dups | DMSQ-refines-DurQ-instance | p | astatelist |
| dups | list-dup | p | list |
| elem | elem | s | |
| equalowns | DMSQ | p | heap × heap × (Ref → OptTid) × Tid × heap × heap × (Ref → OptTid) |
| equalrl | DMSQ | p | reflist × heap × heap × heap × heap |
| fillfirst | DMSQ-refines-DurQ-instance | f | nat × absAction × actionlist → actionlist |
| fillfirst | DMSQ-refines-DurQ-instance | f | nat × DMSQState × cstatelist → cstatelist |
| fillfirst | reflist | f | nat × Ref × reflist → reflist |
| fillfirst | DMSQ-refines-DurQ-instance | f | nat × DurQState × astatelist → astatelist |
| fillfirst | list-last | f | nat × elem × list → list |
| finp | actionstream | p | actionstream |
| finp | DMSQ-refines-DurQ-instance | p | cstatestream |
| finp | DMSQ-refines-DurQ-instance | p | astatestream |
| firstn | actionstream | pf | nat × actionlist → actionlist with λ n, x. n ≤ # x |
| firstn | DMSQ-refines-DurQ-instance | pf | nat × cstatelist → cstatelist with λ n, x. n ≤ # x |
| firstn | DMSQ-refines-DurQ-instance | pf | nat × astatelist → astatelist with λ n, x. n ≤ # x |
| frome | DMSQ-refines-DurQ-instance | f | actionlist × absAction → actionlist |
| frome | DMSQ-refines-DurQ-instance | f | cstatelist × DMSQState → cstatelist |
| frome | DMSQ-refines-DurQ-instance | f | astatelist × DurQState → astatelist |
| globalACrash | DurQ | c | DurQAction |
| globalCRASH | DMSQ | c | DMSQAction |
| globalCRASH | absAction | c | absAction |
| globalFLUSHHEAD | DMSQ | c | DMSQAction |
| globalFLUSHVAL | DMSQ | f | Ref → DMSQAction |
| gstepf | DMSQ | f | DMSQGState × DMSQLState × DMSQPC × DMSQAction → DMSQGState |
| gstepf | DurQ | f | DurQGState × DurQLState × DurQPC × DurQAction → DurQGState |
| hd | DMSQ-refines-DurQ-instance | pf | actionlist → absAction with λ x. x ≠ [] |
| hd | DMSQ-refines-DurQ-instance | pf | actionstream → absAction with λ σ. σ ≠ [] |
| hd | DMSQ-refines-DurQ-instance | pf | cstatelist → DMSQState with λ x. x ≠ [] |
| hd | DMSQ-refines-DurQ-instance | pf | cstatestream → DMSQState with λ σ. σ ≠ [] |
| hd | DMSQ-refines-DurQ-instance | pf | astatelist → DurQState with λ x. x ≠ [] |
| hd | DMSQ-refines-DurQ-instance | pf | astatestream → DurQState with λ σ. σ ≠ [] |
| heap | Node-heap | s | |
| idle | DMSQ | c | DMSQPC |
| idle | DurQ | c | DurQPC |
| invDEQ | DMSQ | f | Tid → DMSQAction |
| invDeq | DurQ | c | DurQPC |
| invENQ | DMSQ | f | Tid × elem → DMSQAction |
| invEnq | DurQ | c | DurQPC |
| lastn | actionstream | pf | nat × actionlist → actionlist with λ n, x. n ≤ # x |
| lastn | DMSQ-refines-DurQ-instance | pf | nat × cstatelist → cstatelist with λ n, x. n ≤ # x |
| lastn | DMSQ-refines-DurQ-instance | pf | nat × astatelist → astatelist with λ n, x. n ≤ # x |
| list | list-data | s | |
| listp | DMSQ | p | reflist × heap × heap × (Ref → OptTid) |
| lstep | DMSQ | p | DMSQGState × DMSQLState × DMSQPC × DMSQAction × DMSQGState × DMSQLState × DMSQPC |
| lstep | DurQ | p | DurQGState × DurQLState × DurQPC × DurQAction × DurQGState × DurQLState × DurQPC |
| lstepf | DMSQ | f | DMSQGState × DMSQLState × DMSQPC × DMSQAction → DMSQLState |
| lstepf | DurQ | f | DurQGState × DurQLState × DurQPC × DurQAction → DurQLState |
| markedp | DMSQ | p | reflist × heap |
| min | nat-inf | f | natinf × natinf → natinf |
| mk | Node | f | elem × OptTid × Ref → Node |
| mkdgs | DurQ-ren | f | list → DurQGState |
| mkgs | DMSQ | f | heap × heap × Ref × Ref × Ref × (Tid → rvRef) × (Tid → rvRef) × rvHeap × rvHeap ×
reflist × reflist × (Ref → OptTid) × (rvRef → rvOwner)
→ DMSQGState |
| mklist | DMSQ-refines-DurQ-instance | f | absAction × nat → actionlist |
| mklist | DMSQ-refines-DurQ-instance | f | DMSQState × nat → cstatelist |
| mklist | reflist | f | Ref × nat → reflist |
| mklist | DMSQ-refines-DurQ-instance | f | DurQState × nat → astatelist |
| mklist | list-last | f | elem × nat → list |
| mkls | DMSQ | f | Tid × elem × OptElem × Ref × Node × bool × Ref × Ref × rvRef × OptElem × Ref ×
Tid × rvRef
→ DMSQLState |
| mkls | DurQ | f | Tid × elem × OptElem × elem × OptElem → DurQLState |
| mkstate | DMSQ | f | DMSQGState × (Tid → DMSQLState) × (Tid → DMSQPC) → DMSQState |
| mkstate | DurQ | f | DurQGState × (Tid → DurQLState) × (Tid → DurQPC) → DurQState |
| nat | nat-basic | s | |
| natinf | nat-inf | s | |
| nextnottid | DMSQ | p | Tid × Ref × heap |
| nextnottidRely | DMSQ | p | Tid × Ref × heap × Ref × heap |
| noid | DMSQ | p | Tid × reflist × Ref × heap |
| noidRely | DMSQ | p | Tid × reflist × heap × reflist × heap |
| nonullRetRefs | DMSQ | p | reflist × heap × (Tid → rvRef) × (Tid → rvRef) |
| noowns | DMSQ | p | Tid × (Ref → OptTid) |
| null | Ref | c | Ref |
| null | rvRef | c | rvRef |
| oneowns | DMSQ | p | Tid × Ref × (Ref → OptTid) × heap × heap |
| oneweakowns | DMSQ | p | Tid × Ref × (Ref → OptTid) × heap × heap |
| ownsRely | DMSQ | p | Tid × (Ref → OptTid) × (Ref → OptTid) |
| pcstepf | DMSQ | f | DMSQGState × DMSQLState × DMSQPC × DMSQAction → DMSQPC |
| pcstepf | DurQ | f | DurQGState × DurQLState × DurQPC × DurQAction → DurQPC |
| pos | DMSQ-refines-DurQ-instance | f | absAction × actionlist → nat |
| pos | DMSQ-refines-DurQ-instance | f | DMSQState × cstatelist → nat |
| pos | DMSQ-refines-DurQ-instance | f | DurQState × astatelist → nat |
| pre | DMSQ | p | DMSQGState × DMSQLState × DMSQPC × DMSQAction |
| pre | DurQ | p | DurQGState × DurQLState × DurQPC × DurQAction |
| prvHpRely | DMSQ | p | rvHeap × rvHeap × rvHeap |
| ready | DMSQ | c | DMSQPC |
| ready | DurQ | c | DurQPC |
| reflist | reflist | s | |
| resDeq | DurQ | c | DurQPC |
| resEnq | DurQ | c | DurQPC |
| restn | actionstream | pf | nat × actionlist → actionlist with λ n, x. n ≤ # x |
| restn | DMSQ-refines-DurQ-instance | pf | nat × cstatelist → cstatelist with λ n, x. n ≤ # x |
| restn | DMSQ-refines-DurQ-instance | pf | nat × astatelist → astatelist with λ n, x. n ≤ # x |
| retDEQ | DMSQ | f | Tid × OptElem → DMSQAction |
| retENQ | DMSQ | f | Tid → DMSQAction |
| rev | actionstream | f | actionlist → actionlist |
| rev | DMSQ-refines-DurQ-instance | f | cstatelist → cstatelist |
| rev | reflist | f | reflist → reflist |
| rev | DMSQ-refines-DurQ-instance | f | astatelist → astatelist |
| rev | list-last | f | list → list |
| rmdup | actionstream | f | actionlist → actionlist |
| rmdup | DMSQ-refines-DurQ-instance | f | cstatelist → cstatelist |
| rmdup | reflist | f | reflist → reflist |
| rmdup | DMSQ-refines-DurQ-instance | f | astatelist → astatelist |
| rmdup | list-dup | f | list → list |
| rvHeap | retval-heap | s | |
| rvOwner | rvowner | s | |
| rvRef | rvRef | s | |
| rvSet | retval-heap | s | |
| rvownerok | DMSQ | p | (Tid → rvRef) × rvHeap × (rvRef → rvOwner) |
| rvownsrely | DMSQ | p | Tid × (rvRef → rvOwner) × (rvRef → rvOwner) × rvHeap |
| rvrely | DMSQ | p | Tid × (rvRef → rvOwner) × (Tid → rvRef) × rvHeap × (Tid → rvRef) × rvHeap |
| some? | opttid | p | OptTid |
| sublist | actionstream | pf | nat × nat × actionlist → actionlist with λ n, m, x. n + m ≤ # x |
| sublist | DMSQ-refines-DurQ-instance | pf | nat × nat × cstatelist → cstatelist with λ n, m, x. n + m ≤ # x |
| sublist | DMSQ-refines-DurQ-instance | pf | nat × nat × astatelist → astatelist with λ n, m, x. n + m ≤ # x |
| tl | actionstream | pf | actionlist → actionlist with λ x. x ≠ [] |
| tl | actionstream | pf | actionstream → actionstream with λ σ. σ ≠ [] |
| tl | DMSQ-refines-DurQ-instance | pf | cstatelist → cstatelist with λ x. x ≠ [] |
| tl | DMSQ-refines-DurQ-instance | pf | cstatestream → cstatestream with λ σ. σ ≠ [] |
| tl | DMSQ-refines-DurQ-instance | pf | astatelist → astatelist with λ x. x ≠ [] |
| tl | DMSQ-refines-DurQ-instance | pf | astatestream → astatestream with λ σ. σ ≠ [] |
| unmarkedp | DMSQ | p | reflist × heap |
| weak? | opttid | p | OptTid |