| Symbol | Specification | Kind | Type |
|---|
| # . | Node-heap | f | heap → nat |
| # . | list-data | f | list → nat |
| . ' | list | f | elem → list |
| . + . | nat-basic | f | nat × nat → nat |
| . + . | list-data | f | elem × list → list |
| . + . | list | f | list × list → list |
| . + . | list | f | list × elem → list |
| . ++ . | list-dup | f | list × elem → list |
| . +1 | nat-basic | f | nat → nat |
| . +2 . | list | f | elem × elem → list |
| . - . | nat | pf | nat × nat → nat with λ n, m. n ≥ m |
| . -- . | Node-heap | f | heap × Ref → heap |
| . -1 | nat-basic | pf | nat → nat with λ n. n ≠ 0 |
| . .butlast | list-last | pf | list → list with λ x. x ≠ [] |
| . .deqID | Node | f | Node → OptTid |
| . .deqID:= . | Node | f | Node × OptTid → Node |
| . .gstate | DQ | f | DQState → DQGState |
| . .gstate:= . | DQ | f | DQState × DQGState → DQState |
| . .head | list-data | pf | list → elem with λ x. x ≠ [] |
| . .ival | DQ | f | DQLState → elem |
| . .ival:= . | DQ | f | DQLState × elem → DQLState |
| . .last | list-last | pf | list → elem with λ x. x ≠ [] |
| . .lsf | DQ | f | DQState → Tid → DQLState |
| . .lsf:= . | DQ | f | DQState × (Tid → DQLState) → DQState |
| . .next | Node | f | Node → Ref |
| . .next:= . | Node | f | Node × Ref → Node |
| . .obsEmpty | DQ | p | DQLState |
| . .obsEmpty:= . | DQ | f | DQLState × bool → DQLState |
| . .optval | DQ | f | DQLState → OptElem |
| . .optval | DQ | pf | DQAction → OptElem with λ a. ∃ tid, optval. a = RetDeq(tid, optval) |
| . .optval:= . | DQ | f | DQLState × OptElem → DQLState |
| . .oval | DQ | f | DQLState → OptElem |
| . .oval:= . | DQ | f | DQLState × OptElem → DQLState |
| . .pcf | DQ | f | DQState → Tid → DQPC |
| . .pcf:= . | DQ | f | DQState × (Tid → DQPC) → DQState |
| . .queue | DQ | f | DQGState → list |
| . .queue:= . | DQ | f | DQGState × list → DQGState |
| . .tail | list-data | pf | list → list with λ x. x ≠ [] |
| . .tid | DQ | f | DQLState → Tid |
| . .tid | opttid | pf | OptTid → Tid with λ opttid. weak?(opttid) ∨ some?(opttid) |
| . .tid | DQ | pf | DQAction → Tid with λ a. a ≠ τ ∧ a ≠ globalCrash |
| . .tid:= . | DQ | f | DQLState × Tid → DQLState |
| . .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 | DQ | pf | DQAction → elem with λ a. ∃ tid, val. a = InvEnq(tid, val) |
| . .val:= . | Node | f | Node × elem → Node |
| . .value | DQ | f | DQLState → elem |
| . .value:= . | DQ | f | DQLState × elem → DQLState |
| . < . | nat-basic | p | nat × nat |
| . < . | list-data | p | list × list |
| . > . | nat | p | nat × nat |
| . [ . ] | Node-heap | f | heap × Ref × Node → heap |
| . [ . ] | Node-heap | pf | heap × Ref → Node with λ st, a. a ∈ st |
| . ∈ . | Node-heap | p | Ref × heap |
| . ∈ . | list | p | elem × list |
| . ≤ . | nat | p | nat × nat |
| . ≥ . | nat | p | nat × nat |
| . ⊆ . | Node-heap | p | heap × heap |
| . ⊑ . | list-last | p | list × list |
| . ⊒ . | list-last | p | list × list |
| [] | list-data | c | list |
| τ | DQ | c | DQAction |
| ∅ | Node-heap | c | heap |
| CHECKEMP | DQ | pr | list : bool |
| CheckEmp | DQ | f | Tid → DQAction |
| Crash | DQ | pr | : (Tid → DQPC) |
| DODEQ | DQ | pr | : OptElem × list |
| DODEQEMPTY | DQ | pr | bool : OptElem |
| DOENQ | DQ | pr | elem : list |
| DQAction | DQ | s | |
| DQGInv | DQ | p | DQGState |
| DQGState | DQ | s | |
| DQInv | DQ | p | DQGState × (Tid → DQLState) × (Tid → DQPC) |
| DQLInv | DQ | p | DQGState × DQLState × DQPC |
| DQLState | DQ | s | |
| DQPC | DQ | s | |
| DQState | DQ | s | |
| DQstep | DQ | p | DQState × DQAction × DQState |
| DoDeq | DQ | f | Tid → DQAction |
| DoDeqEmpty | DQ | f | Tid → DQAction |
| DoEnq | DQ | f | Tid → DQAction |
| Empty | optelem | c | OptElem |
| INVDEQ | DQ | pr | : bool |
| INVENQ | DQ | pr | elem : elem |
| InvDeq | DQ | f | Tid → DQAction |
| InvEnq | DQ | f | Tid × elem → DQAction |
| Node | Node | s | |
| None | opttid | c | OptTid |
| OptElem | optelem | s | |
| OptTid | opttid | s | |
| RETDEQ | DQ | pr | OptElem : : OptElem |
| RETENQ | DQ | pr | : |
| Ref | Ref | s | |
| RetDeq | DQ | f | Tid × OptElem → DQAction |
| RetEnq | DQ | f | Tid → DQAction |
| Run | DQ | pr | : |
| Some | opttid | f | Tid → OptTid |
| Tid | tid | s | |
| Val | optelem | f | elem → OptElem |
| Weak | opttid | f | Tid → OptTid |
| a | DQ-proofs | v | DQAction |
| butlastn | list-last | pf | nat × list → list with λ n, x. n ≤ # x |
| callRun | DQ | f | Tid → DQAction |
| crashed | DQ | c | DQPC |
| disj | list-dup | p | list × list |
| dummytid | tid | c | Tid |
| dups | list-dup | p | list |
| elem | elem | s | |
| fillfirst | list-last | f | nat × elem × list → list |
| globalCrash | DQ | c | DQAction |
| gs | DQ-proofs | v | DQGState |
| gstate | DQ-proofs | v | DQGState |
| gstepf | DQ | f | DQGState × DQLState × DQPC × DQAction → DQGState |
| heap | Node-heap | s | |
| idle | DQ | c | DQPC |
| invDeq | DQ | c | DQPC |
| invEnq | DQ | c | DQPC |
| ival | DQ-proofs | v | elem |
| list | list-data | s | |
| ls | DQ-proofs | v | DQLState |
| lsf | DQ-proofs | v | Tid → DQLState |
| lstep | DQ | p | DQGState × DQLState × DQPC × DQAction × DQGState × DQLState × DQPC |
| lstepf | DQ | f | DQGState × DQLState × DQPC × DQAction → DQLState |
| mk | Node | f | elem × OptTid × Ref → Node |
| mkgs | DQ | f | list → DQGState |
| mklist | list-last | f | elem × nat → list |
| mkls | DQ | f | Tid × bool × elem × OptElem × elem × OptElem → DQLState |
| mkstate | DQ | f | DQGState × (Tid → DQLState) × (Tid → DQPC) → DQState |
| nat | nat-basic | s | |
| null | Ref | c | Ref |
| obsEmpty | DQ-proofs | v | bool |
| optval | DQ-proofs | v | OptElem |
| oval | DQ-proofs | v | OptElem |
| pc | DQ-proofs | v | DQPC |
| pcf | DQ-proofs | v | Tid → DQPC |
| pcstepf | DQ | f | DQGState × DQLState × DQPC × DQAction → DQPC |
| pre | DQ | p | DQGState × DQLState × DQPC × DQAction |
| queue | DQ-proofs | v | list |
| ready | DQ | c | DQPC |
| resDeq | DQ | c | DQPC |
| resEnq | DQ | c | DQPC |
| rev | list-last | f | list → list |
| rmdup | list-dup | f | list → list |
| s | DQ-proofs | v | DQState |
| some? | opttid | p | OptTid |
| tid | DQ-proofs | v | Tid |
| val | DQ-proofs | v | elem |
| value | DQ-proofs | v | elem |
| weak? | opttid | p | OptTid |