| COM | sci_inv_lemma13 | ---- Lemma 13 -------------------------------------------- |
| ABS | inv13_assump | inv13_assump{}(s; p; q; r) ==
status-p_ = Purging status-p_ = Ftod
 (staying(s;q)  (succ-q_ = p))
(purgeQ(q::[]) buf[p]_)
(purgeR(q::p::[]) buf[r]_) |
| THM | inv13_assump_wf | s:state. p,q,r:PId. inv13_assump{}(s; p; q; r)   |
| ABS | inv13_pre | inv13_pre{}(n; s) == p,q:P. r:P+m. inv13_assump{}(s; p; q; r) |
| THM | inv13_pre_wf | n: . s:state. inv13_pre{}(n; s)   |
| ABS | inv13a_off | inv13a_off{}(s; p) ==
status-p_ = Off status-p_ = Pending  cs-p_ = invalid{} |
| THM | inv13a_off_wf | s:state. p:PId. inv13a_off{}(s; p)   |
| ABS | inv13a_inlist | inv13a_inlist{}(s; p) == status-p_ = Inlist  (cs-p_ = invalid{}) |
| THM | inv13a_inlist_wf | s:state. p:PId. inv13a_inlist{}(s; p)   |
| ABS | inv13a_purging | inv13a_purging{}(s; p) ==
status-p_ = Purging  cs-p_ = dirty{} succ-p_ = nil |
| THM | inv13a_purging_wf | s:state. p:PId. inv13a_purging{}(s; p)   |
| ABS | inv13a_ftod | inv13a_ftod{}(s; p) ==
status-p_ = Ftod  cs-p_ = fresh{} pred-p_ = m |
| THM | inv13a_ftod_wf | s:state. p:PId. inv13a_ftod{}(s; p)   |
| ABS | inv13a_inqueue | inv13a_inqueue{}(s; p) ==
status-p_ = Inqueue  pred-p_ = m succ-p_ = nil |
| THM | inv13a_inqueue_wf | s:state. p:PId. inv13a_inqueue{}(s; p)   |
| ABS | inv13a_delright | inv13a_delright{}(s; p; q; r; cs) ==
delrightQ(q::r::cs::[]) buf[p]_  (r = nil) (cs = invalid{}) |
| THM | inv13a_delright_wf | s:state. p:PId. q,r,cs: . inv13a_delright{}(s; p; q; r; cs)   |
| ABS | inv13a_visiting1 | inv13a_visiting1{}(s; p; q; r; cs) ==
visiting(s;p)
(status-q_ = Delleft)
delrightQ(p::r::cs::[]) buf[q]_
 succ-p_ = q |
| THM | inv13a_visiting1_wf | s:state. p,q:PId. r,cs: . inv13a_visiting1{}(s; p; q; r; cs)   |
| ABS | inv13a_visiting2 | inv13a_visiting2{}(s; p; q) ==
visiting(s;p) delrightR(q::ok{}::[]) buf[p]_  succ-p_ = q |
| THM | inv13a_visiting2_wf | s:state. p:PId. q: . inv13a_visiting2{}(s; p; q)   |
| ABS | inv13a | inv13a{}(s; p; q; r; cs) ==
inv13a_off{}(s; p)
inv13a_inlist{}(s; p)
inv13a_purging{}(s; p)
inv13a_ftod{}(s; p)
inv13a_inqueue{}(s; p)
inv13a_delright{}(s; p; q; r; cs)
inv13a_visiting1{}(s; p; q; r; cs)
inv13a_visiting2{}(s; p; q) |
| THM | inv13a_wf | s:state. p,q:PId. r,cs: . inv13a{}(s; p; q; r; cs)   |
| ABS | inv13a_ | inv13a_{}(s; p; q; r; cs) ==
inv13a_off{}(s; p)
inv13a_inlist{}(s; p)
inv13a_purging{}(s; p)
inv13a_ftod{}(s; p)
inv13a_inqueue{}(s; p)
inv13a_delright{}(s; p; q; r; cs)
inv13a_visiting1_{}(s; p; q; r; cs)
inv13a_visiting2{}(s; p; q) |
| THM | inv13a__wf | s:state. p,q:PId. r,cs: . inv13a_{}(s; p; q; r; cs)   |
| ABS | inv13b_1 | inv13b_1{}(s; p) ==
(status-p_ = Inqueue) cs-p_ = invalid{}
 pred-p_ = nil succ-p_ = nil |
| THM | inv13b_1_wf | s:state. p:PId. inv13b_1{}(s; p)   |
| ABS | inv13b_2 | inv13b_2{}(s; p) == (cs-p_ = invalid{})  (pred-p_ = nil) |
| THM | inv13b_2_wf | s:state. p:PId. inv13b_2{}(s; p)   |
| ABS | inv13b | inv13b{}(s; p) == inv13b_1{}(s; p) inv13b_2{}(s; p) |
| THM | inv13b_wf | s:state. p:PId. inv13b{}(s; p)   |
| ABS | inv13c | inv13c{}(n; s) == head-m_ = nil  ( p:P. idle(s;p) leaving(s;p)) |
| THM | inv13c_wf | n: . s:state. inv13c{}(n; s)   |
| ABS | inv13d | inv13d{}(n; s; p) == head-m_ = p (p = nil)  maxrank(n;s;p) |
| THM | inv13d_wf | n: . s:state. p:PId. inv13d{}(n; s; p)   |
| ABS | inv13e | inv13e{}(n; s; p; q; r) ==
idle(s;p) entering(s;p) leaving(s;p) maxrank_visiting(n;s;p)
 (staying(s;q)  (succ-q_ = p))
(purgeQ(q::[]) buf[p]_)
(purgeR(q::p::[]) buf[r]_) |
| THM | inv13e_wf | n: . s:state. p,q,r:PId. inv13e{}(n; s; p; q; r)   |
| ABS | inv13f | inv13f{}(n; s; p; q; cv; arg) ==
read_cache_freshR(m::q::cv::arg) buf[p]_
read_cache_goneR(m::q::cv::arg) buf[p]_
 ((q = nil rank(s;p) = 0 ( r:P. visiting(s;r)))
(isP(q)
((isP(q)  entering(s;q)) maxrank_visiting(n;s;q))
hasrank(s;q)
hasrank(s;p)
rank(s;p) = rank(s;q) + 1))
cv-m_ = cv |
| THM | inv13f_wf | n: . s:state. p,q,cv: . arg: List.
inv13f{}(n; s; p; q; cv; arg)   |
| ABS | inv13g | inv13g{}(s; p) ==
visiting(s;p) (status-p_ = Purging) succ-p_ = nil
 rank(s;p) = 0 |
| THM | inv13g_wf | s:state. p:PId. inv13g{}(s; p)   |
| ABS | inv13h | inv13h{}(n; s; p; q) ==
visiting(s;p) succ-p_ = q (q = nil)
 (isP(q)  visiting(s;q))
hasrank(s;q)
hasrank(s;p)
rank(s;p) = rank(s;q) + 1 |
| THM | inv13h_wf | n: . s:state. p:PId. q: . inv13h{}(n; s; p; q)   |
| ABS | inv13i | inv13i{}(n; s; p; q) ==
prependQ(q::[]) buf[p]_
 hasrank(s;p)
hasrank(s;q)
rank(s;q) = rank(s;p) + 1
((isP(p)  entering(s;p)) maxrank_visiting(n;s;p)) |
| THM | inv13i_wf | n: . s:state. p:PId. q: . inv13i{}(n; s; p; q)   |
| ABS | inv13j | inv13j{}(s; p; q; r; cv) ==
delleftQ(q::r::cv::[]) buf[p]_ visiting(s;q)
 succ-q_ = r pred-q_ = p |
| THM | inv13j_wf | s:state. p,q:PId. r,cv: . inv13j{}(s; p; q; r; cv)   |
| ABS | inv13k | inv13k{}(n; s; p; q; r; cv; cs) ==
prependR(q::q::ok{}::cv::cs::[]) buf[p]_
 maxrank_visiting(n;s;q)
hasrank(s;p)
(cs = invalid{})
pred-q_ = p
rank(s;p) = rank(s;q) + 1
(staying(s;r)  (pred-r_ = m)) |
| THM | inv13k_wf | n: . s:state. p,q,r:PId. cv,cs: .
inv13k{}(n; s; p; q; r; cv; cs)   |
| ABS | inv13l | inv13l{}(n; s; p; q; cv; cs) ==
prependR(q::nil::ok{}::cv::cs::[]) buf[p]_
 ( r:P. visiting(s;r)) rank(s;p) = 0 (cs = invalid{}) |
| THM | inv13l_wf | n: . s:state. p:PId. q,cv,cs: . inv13l{}(n; s; p; q; cv; cs)   |
| ABS | inv13m | inv13m{}(n; s; p; q; r; cv; cs) ==
prependR(q::r::retry{}::cv::cs::[]) buf[p]_
 isP(r)
 (entering(s;r) maxrank_visiting(n;s;r))
hasrank(s;r)
hasrank(s;p)
rank(s;p) = rank(s;r) + 1
((visiting(s;r) (q = r)) q = r) |
| THM | inv13m_wf | n: . s:state. p:PId. q,r,cv,cs: .
inv13m{}(n; s; p; q; r; cv; cs)   |
| ABS | inv13n | inv13n{}(s; p; q) ==
purgeQ(q::[]) buf[p]_
 visiting(s;p)
hasrank(s;p)
hasrank(s;q)
rank(s;q) = rank(s;p) + 1 |
| THM | inv13n_wf | s:state. p:PId. q: . inv13n{}(s; p; q)   |
| ABS | inv13o | inv13o{}(n; s; p; q; r) ==
purgeR(q::r::[]) buf[p]_
 visiting(s;q)
((r = nil rank(s;p) = 0)
(isP(r)
hasrank(s;p)
hasrank(s;r)
rank(s;p) = rank(s;r) + 1
(isP(r)  visiting(s;r)))) |
| THM | inv13o_wf | n: . s:state. p: . q:PId. r: . inv13o{}(n; s; p; q; r)   |
| ABS | inv13p | inv13p{}(n; s; p; q; cv; cs) ==
(pred-p_ = m staying(s;p)  maxrank_staying(n;s;p))
(maxrank_staying(n;s;p)
 ((pred-p_ = m)
( r:P. prependR(p::p::ok{}::cv::cs::[]) buf[r]_)))
(prependR(q::m::cs::[]) buf[p]_  maxrank_staying(n;s;q)) |
| THM | inv13p_wf | n: . s:state. p,q:PId. cv,cs: . inv13p{}(n; s; p; q; cv; cs)   |
| ABS | inv13q | inv13q{}(n; s; p; q; r; cs) ==
( (cs-p_ = invalid{})
 pred-p_ = m
( r':P
pred-p_ = r' ((cs-r'_ = invalid{}) smallrank(n;s;r';p))))
(visiting(s;q) delrightQ(q::r::cs::[]) buf[p]_
 r = m
(isP(r) (isP(r)  cs-r_ = invalid{}))
(isP(r)
(isP(r)  (cs-r_ = invalid{}) smallrank(n;s;r;q)))) |
| THM | inv13q_wf | n: . s:state. p,q:PId. r,cs: . inv13q{}(n; s; p; q; r; cs)   |
| DISP | inv13all_df | inv13all(<n:n:*><s:s:*>)== inv13all(<n><s>) |
| ABS | inv13all | inv13all(n;s) ==
( p:P. q:P+m. r,cs: . inv13a{}(s; p; q; r; cs))
( p:P. inv13b{}(s; p))
inv13c{}(n; s)
( p:P. inv13d{}(n; s; p))
( p,q:P. r:P+m. inv13e{}(n; s; p; q; r))
( p:P. q,cv: . arg: List. inv13f{}(n; s; p; q; cv; arg))
( p:P. inv13g{}(s; p))
( p:P. q: . inv13h{}(n; s; p; q))
( p:P. q: . inv13i{}(n; s; p; q))
( p:P+m. q:P. r,cv: . inv13j{}(s; p; q; r; cv))
( p,q,r:P. cv,cs: . inv13k{}(n; s; p; q; r; cv; cs))
( p:P. q,cv,cs: . inv13l{}(n; s; p; q; cv; cs))
( p:P. q,r,cv,cs: . inv13m{}(n; s; p; q; r; cv; cs))
( p,q:P. inv13n{}(s; p; q))
( p,q:P. r: . inv13o{}(n; s; p; q; r))
( p,q:P. r,cv: . inv13p{}(n; s; p; q; r; cv))
( p,q:P. r,cs: . inv13q{}(n; s; p; q; r; cs)) |
| THM | inv13all_wf | n: . s:state. inv13all(n;s)   |
| DISP | inv13all_assump_df | inv13all_assump(<n:n:*><s:s:*>)== inv13all_assump(<n><s>) |
| ABS | inv13all_assump | inv13all_assump(n;s) ==
( p,q:P. r:P+m. inv13_assump{}(s; p; q; r))
( p:P. q:P+m. r,cs: . inv13a{}(s; p; q; r; cs))
( p:P. inv13b{}(s; p))
inv13c{}(n; s)
( p:P. inv13d{}(n; s; p))
( p,q:P. r:P+m. inv13e{}(n; s; p; q; r))
( p:P. q,cv: . arg: List. inv13f{}(n; s; p; q; cv; arg))
( p:P. inv13g{}(s; p))
( p:P. q: . inv13h{}(n; s; p; q))
( p:P. q: . inv13i{}(n; s; p; q))
( p:P+m. q:P. r,cv: . inv13j{}(s; p; q; r; cv))
( p,q,r:P. cv,cs: . inv13k{}(n; s; p; q; r; cv; cs))
( p:P. q,cv,cs: . inv13l{}(n; s; p; q; cv; cs))
( p:P. q,r,cv,cs: . inv13m{}(n; s; p; q; r; cv; cs))
( p,q:P. inv13n{}(s; p; q))
( p,q:P. r: . inv13o{}(n; s; p; q; r))
( p,q:P. r,cv: . inv13p{}(n; s; p; q; r; cv))
( p,q:P. r,cs: . inv13q{}(n; s; p; q; r; cs)) |
| THM | inv13all_assump_wf | n: . s:state. inv13all_assump(n;s)   |
| ABS | inv13 | inv13{}(n; s) ==
( p:P. q:P+m. r,cs: . inv13a{}(s; p; q; r; cs))
( p:P. inv13b{}(s; p))
inv13c{}(n; s)
( p:P. inv13d{}(n; s; p))
( p,q:P. r:P+m. inv13e{}(n; s; p; q; r))
( p:P. q,cv: . arg: List. inv13f{}(n; s; p; q; cv; arg))
( p:P. inv13g{}(s; p))
( p:P. q: . inv13h{}(n; s; p; q))
( p:P. q: . inv13i{}(n; s; p; q))
( p:P+m. q:P. r,cv: . inv13j{}(s; p; q; r; cv))
( p,q,r:P. cv,cs: . inv13k{}(n; s; p; q; r; cv; cs))
( p:P. q,cv,cs: . inv13l{}(n; s; p; q; cv; cs))
( p:P. q,r,cv,cs: . inv13m{}(n; s; p; q; r; cv; cs))
( p,q:P. inv13n{}(s; p; q))
( p,q:P. r: . inv13o{}(n; s; p; q; r))
( p,q:P. r,cv: . inv13p{}(n; s; p; q; r; cv)) |
| THM | inv13_wf | n: . s:state. inv13{}(n; s)   |
| THM | decidable__inbuf | s:state. M:mesg. p: . Dec(M buf[p]_) |
| THM | decidable__all_vproc | n: . P:P  . ( x:P. Dec(P[x]))  Dec( x:P. P[x]) |
| THM | decidable__exists_vproc | n: . P:P  . ( x:P. Dec(P[x]))  Dec( x:P. P[x]) |
| THM | decidable__hasrank | s:state. p: . Dec(hasrank(s;p)) |
| THM | decidable__maxrank | n: . s:state. p: . Dec(maxrank(n;s;p)) |
| THM | decidable__staying | s:state. p:PId. Dec(staying(s;p)) |
| THM | decidable__maxrank_visiting | n: . s:state. p:PId. Dec(maxrank_visiting(n;s;p)) |
| THM | decidable__implies2 | P,Q: . Dec(P)  (P  Dec(Q))  Dec(implies2{}(P; Q)) |
| THM | decidable__is_proc | p: . N: . Dec(isP(N,p)) |
| THM | decidable__maxrank_staying | n: . s:state. p:PId. Dec(maxrank_staying(n;s;p)) |
| THM | decidable__xor | p,q: . Dec(p)  Dec(q)  Dec(p q) |
| THM | decidable__inv13a | s:state. p,q:PId. r,cs: . Dec(inv13a{}(s; p; q; r; cs)) |
| THM | decidable__inv13b | s:state. p:PId. Dec(inv13b{}(s; p)) |
| THM | decidable__inv13c | n: . s:state. Dec(inv13c{}(n; s)) |
| THM | decidable__inv13d | n: . s:state. p:PId. Dec(inv13d{}(n; s; p)) |
| THM | decidable__inv13e | n: . s:state. p,q,r:PId. Dec(inv13e{}(n; s; p; q; r)) |
| THM | decidable__inv13f | n: . s:state. p,q,cv: . arg: List.
Dec(inv13f{}(n; s; p; q; cv; arg)) |
| THM | decidable__inv13g | s:state. p:PId. Dec(inv13g{}(s; p)) |
| THM | decidable__inv13h | n: . s:state. p:PId. q: . Dec(inv13h{}(n; s; p; q)) |
| THM | decidable__inv13i | n: . s:state. p:PId. q: . Dec(inv13i{}(n; s; p; q)) |
| THM | decidable__inv13j | s:state. p,q:PId. r,cv: . Dec(inv13j{}(s; p; q; r; cv)) |
| THM | decidable__inv13k | n: . s:state. p,q,r:PId. cv,cs: .
Dec(inv13k{}(n; s; p; q; r; cv; cs)) |
| THM | decidable__inv13l | n: . s:state. p:PId. q,cv,cs: . Dec(inv13l{}(n; s; p; q; cv; cs)) |
| THM | decidable__inv13m | n: . s:state. p:PId. q,r,cv,cs: .
Dec(inv13m{}(n; s; p; q; r; cv; cs)) |
| THM | decidable__inv13n | s:state. p:PId. q: . Dec(inv13n{}(s; p; q)) |
| THM | decidable__inv13o | n: . s:state. p: . q:PId. r: . Dec(inv13o{}(n; s; p; q; r)) |
| THM | decidable__inv13p | n: . s:state. p,q:PId. cv,cs: . Dec(inv13p{}(n; s; p; q; cv; cs)) |
| THM | decidable__inv13q | n: . s:state. p,q:PId. r,cs: . inv13q{}(n; s; p; q; r; cs)   |