[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,

Signature symbols in this unit

Symbol Specification Kind Type
# .Node-heapfheap → nat
# .reflistfreflist → nat
# .retval-heapfrvHeap → nat
# .retval-heapfrvSet → nat
# .list-dataflist → nat
. 'reflistfRef → reflist
. 'listfelem → list
. + .nat-basicfnat × nat → nat
. + .reflistfRef × reflist → reflist
. + .reflistfreflist × reflist → reflist
. + .reflistfreflist × Ref → reflist
. + .list-datafelem × list → list
. + .listflist × list → list
. + .listflist × elem → list
. ++ .reflistfreflist × Ref → reflist
. ++ .retval-heapfrvSet × rvRef → rvSet
. ++ .list-dupflist × elem → list
. +1nat-basicfnat → nat
. +2 .reflistfRef × Ref → reflist
. +2 .listfelem × elem → list
. - .natpfnat × nat → nat with λ n, m. n ≥ m
. -- .Node-heapfheap × Ref → heap
. -- .retval-heapfrvHeap × rvRef → rvHeap
. -- .retval-heapfrvSet × rvRef → rvSet
. -1nat-basicpfnat → nat with λ n. n ≠ 0
. .addrDMSQfDMSQLState → rvRef
. .addr:= .DMSQfDMSQLState × rvRef → DMSQLState
. .butlastreflistpfreflist → reflist with λ x. x ≠ []
. .butlastlist-lastpflist → list with λ x. x ≠ []
. .deqIDNodefNode → OptTid
. .deqID:= .NodefNode × OptTid → Node
. .firstDMSQfDMSQLState → Ref
. .first:= .DMSQfDMSQLState × Ref → DMSQLState
. .gstateDMSQfDMSQState → DMSQGState
. .gstateDQfDQState → DQGState
. .gstate:= .DMSQfDMSQState × DMSQGState → DMSQState
. .gstate:= .DQfDQState × DQGState → DQState
. .headreflistpfreflist → Ref with λ x. x ≠ []
. .headlist-datapflist → elem with λ x. x ≠ []
. .invENQvalueDMSQpfDMSQAction → elem with λ a. ∃ tid, invENQvalue. a = invENQ(tid, invENQvalue)
. .invFLUSHVALrDMSQpfDMSQAction → Ref with λ a. ∃ invFLUSHVALr. a = globalFLUSHVAL(invFLUSHVALr)
. .ivalDQfDQLState → elem
. .ival:= .DQfDQLState × elem → DQLState
. .lastreflistpfreflist → Ref with λ x. x ≠ []
. .lastlist-lastpflist → elem with λ x. x ≠ []
. .lsfDMSQfDMSQState → Tid → DMSQLState
. .lsfDQfDQState → Tid → DQLState
. .lsf:= .DMSQfDMSQState × (Tid → DMSQLState) → DMSQState
. .lsf:= .DQfDQState × (Tid → DQLState) → DQState
. .lstDMSQfDMSQLState → Ref
. .lst:= .DMSQfDMSQLState × Ref → DMSQLState
. .ndDMSQfDMSQLState → Node
. .ndDMSQpfDMSQAction → Node with λ a. ∃ invFLUSHVALr, nd, success. a = chooseE1(invFLUSHVALr, nd, success)
. .nd:= .DMSQfDMSQLState × Node → DMSQLState
. .nextNodefNode → Ref
. .next:= .NodefNode × Ref → Node
. .nodeDMSQfDMSQLState → Ref
. .nodeDMSQpfDMSQAction → Ref with λ a. ∃ invFLUSHVALr, nd, success. a = chooseE1(invFLUSHVALr, nd, success)
. .node:= .DMSQfDMSQLState × Ref → DMSQLState
. .nxtDMSQfDMSQLState → Ref
. .nxt:= .DMSQfDMSQLState × Ref → DMSQLState
. .obsEmptyDQpDQLState
. .obsEmpty:= .DQfDQLState × bool → DQLState
. .optvalDMSQfDMSQLState → OptElem
. .optvalDQfDQLState → OptElem
. .optvalDQpfDQAction → OptElem with λ a. ∃ tid, optval. a = RetDeq(tid, optval)
. .optvalDMSQ-Automaton-absActionpfabsAction → OptElem with λ aa. ∃ tid, optval. aa = ResDEQ(tid, optval)
. .optval:= .DMSQfDMSQLState × OptElem → DMSQLState
. .optval:= .DQfDQLState × OptElem → DQLState
. .optval0DMSQfDMSQLState → OptElem
. .optval0DMSQpfDMSQAction → OptElem with λ a. ∃ rvref, retDEQoptval. a = chooseD2(rvref, retDEQoptval)
. .optval0:= .DMSQfDMSQLState × OptElem → DMSQLState
. .orlDMSQfDMSQGState → reflist
. .orl:= .DMSQfDMSQGState × reflist → DMSQGState
. .othertidDMSQfDMSQLState → Tid
. .othertid:= .DMSQfDMSQLState × Tid → DMSQLState
. .ovalDQfDQLState → OptElem
. .oval:= .DQfDQLState × OptElem → DQLState
. .ownsDMSQfDMSQGState → Ref → OptTid
. .owns:= .DMSQfDMSQGState × (Ref → OptTid) → DMSQGState
. .pcfDMSQfDMSQState → Tid → DMSQPC
. .pcfDQfDQState → Tid → DQPC
. .pcf:= .DMSQfDMSQState × (Tid → DMSQPC) → DMSQState
. .pcf:= .DQfDQState × (Tid → DQPC) → DQState
. .pending?rvownerprvOwner
. .pheadDMSQfDMSQGState → Ref
. .phead:= .DMSQfDMSQGState × Ref → DMSQGState
. .pretRefsDMSQfDMSQGState → Tid → rvRef
. .pretRefs:= .DMSQfDMSQGState × (Tid → rvRef) → DMSQGState
. .prvHpDMSQfDMSQGState → rvHeap
. .prvHp:= .DMSQfDMSQGState × rvHeap → DMSQGState
. .psDMSQfDMSQGState → heap
. .ps:= .DMSQfDMSQGState × heap → DMSQGState
. .qrlDMSQfDMSQGState → reflist
. .qrl:= .DMSQfDMSQGState × reflist → DMSQGState
. .queueDQfDQGState → list
. .queue:= .DQfDQGState × list → DQGState
. .retDEQoptvalDMSQpfDMSQAction → OptElem with λ a. ∃ tid, retDEQoptval. a = retDEQ(tid, retDEQoptval)
. .rvownsDMSQfDMSQGState → rvRef → rvOwner
. .rvowns:= .DMSQfDMSQGState × (rvRef → rvOwner) → DMSQGState
. .rvrefDMSQfDMSQLState → rvRef
. .rvrefDMSQpfDMSQAction → rvRef with λ a. ∃ rvref, retDEQoptval. a = chooseD2(rvref, retDEQoptval)
. .rvref:= .DMSQfDMSQLState × rvRef → DMSQLState
. .successDMSQpDMSQLState
. .successDMSQppDMSQAction with λ a. ∃ invFLUSHVALr, nd, success. a = chooseE1(invFLUSHVALr, nd, success)
. .success:= .DMSQfDMSQLState × bool → DMSQLState
. .tailreflistpfreflist → reflist with λ x. x ≠ []
. .taillist-datapflist → list with λ x. x ≠ []
. .tidrvownerfrvOwner → Tid
. .tidDMSQfDMSQLState → Tid
. .tidDQfDQLState → Tid
. .tidopttidpfOptTid → Tid with λ opttid. weak?(opttid) ∨ some?(opttid)
. .tidDMSQpfDMSQAction → 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))
. .tidDQpfDQAction → Tid with λ a. a ≠ τ ∧ a ≠ globalCrash
. .tidDMSQ-Automaton-absActionpfabsAction → Tid with λ aa. aa ≠ globalCRASH ∧ aa ≠ τ
. .tid:= .DMSQfDMSQLState × Tid → DMSQLState
. .tid:= .DQfDQLState × Tid → DQLState
. .tid:= .opttidpfOptTid × Tid → OptTid with λ opttid, tid. weak?(opttid) ∨ some?(opttid)
. .valNodefNode → elem
. .valoptelempfOptElem → elem with λ optval. optval ≠ Empty
. .valrvownerpfrvOwner → elem with λ ow. ∃ tid, val. ow = Claimed(tid, val)
. .valDQpfDQAction → elem with λ a. ∃ tid, val. a = InvEnq(tid, val)
. .valDMSQ-Automaton-absActionpfabsAction → elem with λ aa. ∃ tid, val. aa = InvENQ(tid, val)
. .val:= .NodefNode × elem → Node
. .valueDMSQfDMSQLState → elem
. .valueDQfDQLState → elem
. .value:= .DMSQfDMSQLState × elem → DMSQLState
. .value:= .DQfDQLState × elem → DQLState
. .vheadDMSQfDMSQGState → Ref
. .vhead:= .DMSQfDMSQGState × Ref → DMSQGState
. .vretRefsDMSQfDMSQGState → Tid → rvRef
. .vretRefs:= .DMSQfDMSQGState × (Tid → rvRef) → DMSQGState
. .vrvHpDMSQfDMSQGState → rvHeap
. .vrvHp:= .DMSQfDMSQGState × rvHeap → DMSQGState
. .vsDMSQfDMSQGState → heap
. .vs:= .DMSQfDMSQGState × heap → DMSQGState
. .vtailDMSQfDMSQGState → Ref
. .vtail:= .DMSQfDMSQGState × Ref → DMSQGState
. < .nat-basicpnat × nat
. < .reflistpreflist × reflist
. < .list-dataplist × list
. > .natpnat × nat
. [ . ]Node-heapfheap × Ref × Node → heap
. [ . ]retval-heapfrvHeap × rvRef × OptElem → rvHeap
. [ . ]Node-heappfheap × Ref → Node with λ st, a. a ∈ st
. [ . ]retval-heappfrvHeap × rvRef → OptElem with λ st, a. a ∈ st
. \ .retval-heapfrvSet × rvSet → rvSet
. \ .retval-heapfrvHeap × rvSet → rvHeap
. | .retval-heapfrvHeap × rvSet → rvHeap
. ∈ .Node-heappRef × heap
. ∈ .reflistpRef × reflist
. ∈ .retval-heapprvRef × rvHeap
. ∈ .retval-heapprvRef × rvSet
. ∈ .retval-heappOptElem × rvHeap
. ∈ .listpelem × list
. ∩ .retval-heapfrvSet × rvSet → rvSet
. ∪ .retval-heapfrvSet × rvSet → rvSet
. ≤ .natpnat × nat
. ≥ .natpnat × nat
. ⊆ .Node-heappheap × heap
. ⊆ .retval-heapprvHeap × rvHeap
. ⊆ .retval-heapprvSet × rvSet
. ⊑ .reflistpreflist × reflist
. ⊑ .list-lastplist × list
. ⊒ .reflistpreflist × reflist
. ⊒ .list-lastplist × list
. ⊕ .retval-heapfrvHeap × rvHeap → rvHeap
. ⊕ .DMSQfheap × heap → heap
. from .DMSQfreflist × Ref → reflist
[]reflistcreflist
[]list-dataclist
{ . }retval-heapfrvRef → rvSet
τDMSQcDMSQAction
τDQcDQAction
τDMSQ-Automaton-absActioncabsAction
∅Node-heapcheap
∅retval-heapcrvHeap
∅retval-heapcrvSet
CHECKEMPDQprlist : bool
CRASHDMSQprheap × Ref × (Tid → rvRef) × rvHeap : heap × Ref × Ref × (Tid → rvRef) × rvHeap × (Ref → OptTid) × (Tid → DMSQPC)
CallRUNDMSQ-Automaton-absActionfTid → absAction
CheckEmpDQfTid → DQAction
ClaimedrvownerfTid × elem → rvOwner
CrashDQpr : (Tid → DQPC)
D1DMSQcDMSQPC
D10DMSQcDMSQPC
D11DMSQcDMSQPC
D12DMSQcDMSQPC
D13DMSQcDMSQPC
D14DMSQcDMSQPC
D15DMSQcDMSQPC
D16DMSQcDMSQPC
D17DMSQcDMSQPC
D18DMSQcDMSQPC
D19DMSQcDMSQPC
D2DMSQcDMSQPC
D20DMSQcDMSQPC
D21DMSQcDMSQPC
D22DMSQcDMSQPC
D23DMSQcDMSQPC
D24DMSQcDMSQPC
D25DMSQcDMSQPC
D26DMSQcDMSQPC
D27DMSQcDMSQPC
D28DMSQcDMSQPC
D29DMSQcDMSQPC
D3DMSQcDMSQPC
D30DMSQcDMSQPC
D31DMSQcDMSQPC
D32DMSQcDMSQPC
D33DMSQcDMSQPC
D34DMSQcDMSQPC
D4DMSQcDMSQPC
D5DMSQcDMSQPC
D6DMSQcDMSQPC
D7DMSQcDMSQPC
D8DMSQcDMSQPC
D9DMSQcDMSQPC
DMSQActionDMSQs
DMSQGInvDMSQpDMSQGState
DMSQGStateDMSQs
DMSQInvDMSQpDMSQGState × (Tid → DMSQLState) × (Tid → DMSQPC)
DMSQLInvDMSQpDMSQGState × DMSQLState × DMSQPC
DMSQLStateDMSQs
DMSQPCDMSQs
DMSQRelyDMSQpDMSQGState × Tid × DMSQGState
DMSQStateDMSQs
DMSQastepDMSQ-Automaton-absActionpDMSQState × DQAction × DMSQState
DMSQinitDMSQ-Automaton-absActionpDMSQState
DMSQstepDMSQpDMSQState × DMSQAction × DMSQState
DODEQDQpr : OptElem × list
DODEQEMPTYDQprbool : OptElem
DOENQDQprelem : list
DQActionDQs
DQGInvDQpDQGState
DQGStateDQs
DQInvDQpDQGState × (Tid → DQLState) × (Tid → DQPC)
DQLInvDQpDQGState × DQLState × DQPC
DQLStateDQs
DQPCDQs
DQStateDQs
DQinitDMSQ-Automaton-absActionpDQState
DQstepDQpDQState × DQAction × DQState
DoDeqDQfTid → DQAction
DoDeqEmptyDQfTid → DQAction
DoEnqDQfTid → DQAction
E1DMSQcDMSQPC
E10DMSQcDMSQPC
E11DMSQcDMSQPC
E12DMSQcDMSQPC
E13DMSQcDMSQPC
E14DMSQcDMSQPC
E15DMSQcDMSQPC
E16DMSQcDMSQPC
E17DMSQcDMSQPC
E2DMSQcDMSQPC
E3DMSQcDMSQPC
E4DMSQcDMSQPC
E5DMSQcDMSQPC
E6DMSQcDMSQPC
E7DMSQcDMSQPC
E8DMSQcDMSQPC
E9DMSQcDMSQPC
EmptyoptelemcOptElem
FLUSHHEADDMSQprRef : Ref
FLUSHNEXTDMSQprRef × heap × reflist : heap × reflist × (Ref → OptTid)
FLUSHOPTTIDDMSQprRef × heap : heap × reflist × reflist
FLUSHRETREFDMSQprTid × (Tid → rvRef) : (Tid → rvRef)
FLUSHRVHPDMSQprrvRef × rvHeap : rvHeap
FLUSHVALDMSQprRef × heap : heap
INVDEQDQpr : bool
INVENQDQprelem : elem
InvDEQDMSQ-Automaton-absActionfTid → absAction
InvDeqDQfTid → DQAction
InvENQDMSQ-Automaton-absActionfTid × elem → absAction
InvEnqDQfTid × elem → DQAction
NodeNodes
NoneopttidcOptTid
OptElemoptelems
OptTidopttids
PendingrvownerfTid → rvOwner
RETDEQDQprOptElem : : OptElem
RETENQDQpr :
RUNDMSQpr :
RefRefs
ResDEQDMSQ-Automaton-absActionfTid × OptElem → absAction
ResENQDMSQ-Automaton-absActionfTid → absAction
RetDeqDQfTid × OptElem → DQAction
RetEnqDQfTid → DQAction
RunDQpr :
SomeopttidfTid → OptTid
Tidtids
Valoptelemfelem → OptElem
WeakopttidfTid → OptTid
absDMSQ-Automaton-absActionpDMSQState × DQState
absActionDMSQ-Automaton-absActions
abslsDMSQ-Automaton-absActionpDMSQGState × DMSQLState × DMSQPC × DQLState
abspcDMSQ-Automaton-absActionfDMSQGState × DMSQLState × DMSQPC → DQPC
allocrvDMSQp(Tid → rvRef) × rvHeap
butlastnreflistpfnat × reflist → reflist with λ n, x. n ≤ # x
butlastnlist-lastpfnat × list → list with λ n, x. n ≤ # x
callRUNDMSQfTid → DMSQAction
callRunDQfTid → DQAction
checkEmpDMSQfTid → DMSQAction
chooseD2DMSQfrvRef × OptElem → DMSQAction
chooseE1DMSQfRef × Node × bool → DMSQAction
contentDMSQ-Automaton-absActionfreflist × heap → list
crashedDMSQcDMSQPC
crashedDQcDQPC
disjreflistpreflist × reflist
disjlist-dupplist × list
doDeqDMSQfTid → DMSQAction
doDeqEmptyDMSQfTid → DMSQAction
doEnqDMSQfTid → DMSQAction
dom .retval-heapfrvHeap → rvSet
dummytidtidcTid
dupsreflistpreflist
dupslist-dupplist
elemelems
equalownsDMSQpheap × heap × (Ref → OptTid) × Tid × heap × heap × (Ref → OptTid)
equalrlDMSQpreflist × heap × heap × heap × heap
fillfirstreflistfnat × Ref × reflist → reflist
fillfirstlist-lastfnat × elem × list → list
globalCRASHDMSQcDMSQAction
globalCRASHDMSQ-Automaton-absActioncabsAction
globalCrashDQcDQAction
globalFLUSHHEADDMSQcDMSQAction
globalFLUSHVALDMSQfRef → DMSQAction
gstepfDMSQfDMSQGState × DMSQLState × DMSQPC × DMSQAction → DMSQGState
gstepfDQfDQGState × DQLState × DQPC × DQAction → DQGState
heapNode-heaps
idleDMSQcDMSQPC
idleDQcDQPC
invDEQDMSQfTid → DMSQAction
invDeqDQcDQPC
invENQDMSQfTid × elem → DMSQAction
invEnqDQcDQPC
listlist-datas
listpDMSQpreflist × heap × heap × (Ref → OptTid)
lstepDMSQpDMSQGState × DMSQLState × DMSQPC × DMSQAction × DMSQGState × DMSQLState × DMSQPC
lstepDQpDQGState × DQLState × DQPC × DQAction × DQGState × DQLState × DQPC
lstepfDMSQfDMSQGState × DMSQLState × DMSQPC × DMSQAction → DMSQLState
lstepfDQfDQGState × DQLState × DQPC × DQAction → DQLState
markedpDMSQpreflist × heap
mkNodefelem × OptTid × Ref → Node
mkgsDMSQfheap × heap × Ref × Ref × Ref × (Tid → rvRef) × (Tid → rvRef) × rvHeap × rvHeap × reflist × reflist × (Ref → OptTid) × (rvRef → rvOwner) → DMSQGState
mkgsDQflist → DQGState
mklistreflistfRef × nat → reflist
mklistlist-lastfelem × nat → list
mklsDMSQfTid × elem × OptElem × Ref × Node × bool × Ref × Ref × rvRef × OptElem × Ref × Tid × rvRef → DMSQLState
mklsDQfTid × bool × elem × OptElem × elem × OptElem → DQLState
mkstateDMSQfDMSQGState × (Tid → DMSQLState) × (Tid → DMSQPC) → DMSQState
mkstateDQfDQGState × (Tid → DQLState) × (Tid → DQPC) → DQState
natnat-basics
nextnottidDMSQpTid × Ref × heap
nextnottidRelyDMSQpTid × Ref × heap × Ref × heap
noidDMSQpTid × reflist × Ref × heap
noidRelyDMSQpTid × reflist × heap × reflist × heap
nonullRetRefsDMSQpreflist × heap × (Tid → rvRef) × (Tid → rvRef)
noownsDMSQpTid × (Ref → OptTid)
nullRefcRef
nullrvRefcrvRef
oneownsDMSQpTid × Ref × (Ref → OptTid) × heap × heap
oneweakownsDMSQpTid × Ref × (Ref → OptTid) × heap × heap
ownsRelyDMSQpTid × (Ref → OptTid) × (Ref → OptTid)
pcstepfDMSQfDMSQGState × DMSQLState × DMSQPC × DMSQAction → DMSQPC
pcstepfDQfDQGState × DQLState × DQPC × DQAction → DQPC
preDMSQpDMSQGState × DMSQLState × DMSQPC × DMSQAction
preDQpDQGState × DQLState × DQPC × DQAction
prvHpRelyDMSQprvHeap × rvHeap × rvHeap
readyDMSQcDMSQPC
readyDQcDQPC
reflistreflists
renDMSQ-Automaton-absActionfDMSQAction → DQAction
resDeqDQcDQPC
resEnqDQcDQPC
retDEQDMSQfTid × OptElem → DMSQAction
retENQDMSQfTid → DMSQAction
revreflistfreflist → reflist
revlist-lastflist → list
rmdupreflistfreflist → reflist
rmduplist-dupflist → list
rvHeapretval-heaps
rvOwnerrvowners
rvRefrvRefs
rvSetretval-heaps
rvownerokDMSQp(Tid → rvRef) × rvHeap × (rvRef → rvOwner)
rvownsrelyDMSQpTid × (rvRef → rvOwner) × (rvRef → rvOwner) × rvHeap
rvrelyDMSQpTid × (rvRef → rvOwner) × (Tid → rvRef) × rvHeap × (Tid → rvRef) × rvHeap
some?opttidpOptTid
unmarkedpDMSQpreflist × heap
weak?opttidpOptTid