[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
. 'reflistfRef → reflist
. + .nat-basicfnat × nat → nat
. + .reflistfRef × reflist → reflist
. + .reflistfreflist × reflist → reflist
. + .reflistfreflist × Ref → reflist
. ++ .reflistfreflist × Ref → reflist
. ++ .retval-heapfrvSet × rvRef → rvSet
. +1nat-basicfnat → nat
. +2 .reflistfRef × Ref → reflist
. - .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 ≠ []
. .deqIDNodefNode → OptTid
. .deqID:= .NodefNode × OptTid → Node
. .firstDMSQfDMSQLState → Ref
. .first:= .DMSQfDMSQLState × Ref → DMSQLState
. .gstateDMSQfDMSQState → DMSQGState
. .gstate:= .DMSQfDMSQState × DMSQGState → DMSQState
. .headreflistpfreflist → Ref with λ x. x ≠ []
. .invENQvalueDMSQpfDMSQAction → elem with λ a. ∃ tid, invENQvalue. a = invENQ(tid, invENQvalue)
. .invFLUSHVALrDMSQpfDMSQAction → Ref with λ a. ∃ invFLUSHVALr. a = globalFLUSHVAL(invFLUSHVALr)
. .lastreflistpfreflist → Ref with λ x. x ≠ []
. .lsfDMSQfDMSQState → Tid → DMSQLState
. .lsf:= .DMSQfDMSQState × (Tid → DMSQLState) → DMSQState
. .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
. .optvalDMSQfDMSQLState → OptElem
. .optvalDMSQtrace-absActionpfabsAction → OptElem with λ aa. ∃ tid, optval. aa = ResDEQ(tid, optval)
. .optval:= .DMSQfDMSQLState × OptElem → DMSQLState
. .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
. .ownsDMSQfDMSQGState → Ref → OptTid
. .owns:= .DMSQfDMSQGState × (Ref → OptTid) → DMSQGState
. .pcfDMSQfDMSQState → Tid → DMSQPC
. .pcf:= .DMSQfDMSQState × (Tid → DMSQPC) → DMSQState
. .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
. .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 ≠ []
. .tidrvownerfrvOwner → Tid
. .tidDMSQfDMSQLState → 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))
. .tidDMSQtrace-absActionpfabsAction → Tid with λ aa. aa ≠ globalCRASH ∧ aa ≠ τ
. .tid:= .DMSQfDMSQLState × Tid → DMSQLState
. .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)
. .valDMSQtrace-absActionpfabsAction → elem with λ aa. ∃ tid, val. aa = InvENQ(tid, val)
. .val:= .NodefNode × elem → Node
. .valueDMSQfDMSQLState → elem
. .value:= .DMSQfDMSQLState × elem → DMSQLState
. .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
. > .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
. ∩ .retval-heapfrvSet × rvSet → rvSet
. ∪ .retval-heapfrvSet × rvSet → rvSet
. ≤ .natpnat × nat
. ≥ .natpnat × nat
. ⊆ .Node-heappheap × heap
. ⊆ .retval-heapprvHeap × rvHeap
. ⊆ .retval-heapprvSet × rvSet
. ⊑ .reflistpreflist × reflist
. ⊒ .reflistpreflist × reflist
. ⊕ .retval-heapfrvHeap × rvHeap → rvHeap
. ⊕ .DMSQfheap × heap → heap
. from .DMSQfreflist × Ref → reflist
[]reflistcreflist
{ . }retval-heapfrvRef → rvSet
τDMSQcDMSQAction
τDMSQtrace-absActioncabsAction
∅Node-heapcheap
∅retval-heapcrvHeap
∅retval-heapcrvSet
CRASHDMSQprheap × Ref × (Tid → rvRef) × rvHeap : heap × Ref × Ref × (Tid → rvRef) × rvHeap × (Ref → OptTid) × (Tid → DMSQPC)
CallRUNDMSQtrace-absActionfTid → absAction
ClaimedrvownerfTid × elem → rvOwner
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
DMSQstepDMSQpDMSQState × DMSQAction × DMSQState
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
InvDEQDMSQtrace-absActionfTid → absAction
InvENQDMSQtrace-absActionfTid × elem → absAction
NodeNodes
NoneopttidcOptTid
OptElemoptelems
OptTidopttids
PendingrvownerfTid → rvOwner
RUNDMSQpr :
RefRefs
ResDEQDMSQtrace-absActionfTid × OptElem → absAction
ResENQDMSQtrace-absActionfTid → absAction
SomeopttidfTid → OptTid
Tidtids
Valoptelemfelem → OptElem
WeakopttidfTid → OptTid
absActionDMSQtrace-absActions
allocrvDMSQp(Tid → rvRef) × rvHeap
butlastnreflistpfnat × reflist → reflist with λ n, x. n ≤ # x
callRUNDMSQfTid → DMSQAction
checkEmpDMSQfTid → DMSQAction
chooseD2DMSQfrvRef × OptElem → DMSQAction
chooseE1DMSQfRef × Node × bool → DMSQAction
crashedDMSQcDMSQPC
disjreflistpreflist × reflist
doDeqDMSQfTid → DMSQAction
doDeqEmptyDMSQfTid → DMSQAction
doEnqDMSQfTid → DMSQAction
dom .retval-heapfrvHeap → rvSet
dummytidtidcTid
dupsreflistpreflist
elemelems
equalownsDMSQpheap × heap × (Ref → OptTid) × Tid × heap × heap × (Ref → OptTid)
equalrlDMSQpreflist × heap × heap × heap × heap
fillfirstreflistfnat × Ref × reflist → reflist
globalCRASHDMSQcDMSQAction
globalCRASHDMSQtrace-absActioncabsAction
globalFLUSHHEADDMSQcDMSQAction
globalFLUSHVALDMSQfRef → DMSQAction
gstepfDMSQfDMSQGState × DMSQLState × DMSQPC × DMSQAction → DMSQGState
heapNode-heaps
idleDMSQcDMSQPC
invDEQDMSQfTid → DMSQAction
invENQDMSQfTid × elem → DMSQAction
listpDMSQpreflist × heap × heap × (Ref → OptTid)
lstepDMSQpDMSQGState × DMSQLState × DMSQPC × DMSQAction × DMSQGState × DMSQLState × DMSQPC
lstepfDMSQfDMSQGState × DMSQLState × DMSQPC × DMSQAction → DMSQLState
markedpDMSQpreflist × heap
mkNodefelem × OptTid × Ref → Node
mkgsDMSQfheap × heap × Ref × Ref × Ref × (Tid → rvRef) × (Tid → rvRef) × rvHeap × rvHeap × reflist × reflist × (Ref → OptTid) × (rvRef → rvOwner) → DMSQGState
mklistreflistfRef × nat → reflist
mklsDMSQfTid × elem × OptElem × Ref × Node × bool × Ref × Ref × rvRef × OptElem × Ref × Tid × rvRef → DMSQLState
mkstateDMSQfDMSQGState × (Tid → DMSQLState) × (Tid → DMSQPC) → DMSQState
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
preDMSQpDMSQGState × DMSQLState × DMSQPC × DMSQAction
prvHpRelyDMSQprvHeap × rvHeap × rvHeap
readyDMSQcDMSQPC
reflistreflists
retDEQDMSQfTid × OptElem → DMSQAction
retENQDMSQfTid → DMSQAction
revreflistfreflist → reflist
rmdupreflistfreflist → reflist
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