| COM | sci_rank_1 | ---- General Definitions and Theorems -------------------- |
| THM | filter_eq_int | x: . l: List. P:  .
 (P x)  filter( y. (y = x);filter(P;l)) = filter(P;l) |
| THM | filter_eq_int_false_el | x,z: . l: List.
(z = x)
 (list_el( ;x;l)   list_el( ;x;filter( y. (y = z);l))) |
| DISP | rank_fn_df | rank_fn(<x:x:*><l:l:*>)== rank_fn(<x><l>) |
| ML | rank_fn_ml | rank_fn(x;l)
==r if null(l)
then -1
else if (x = hd(l)) then ||tl(l)|| else rank_fn(x;tl(l)) fi
fi |
| THM | rank_fn_wf | x: . l: List. rank_fn(x;l)  |
| THM | rank_fn_cons | x,y: . l: List.
rank_fn(x;y::l) = if (x = y) then ||l|| else rank_fn(x;l) fi |
| THM | rank_fn_el | x: . l: List. rank_fn(x;l) 0  list_el( ;x;l) |
| THM | rank_fn_range | x: . l: List. -1 rank_fn(x;l) < ||l|| |
| DISP | ranked_df | ranked(<x:x:*><l:l:*>)== ranked(<x><l>) |
| ABS | ranked | ranked(x;l) == rank_fn(x;l) 0 |
| THM | ranked_wf | x: . l: List. ranked(x;l)   |
| THM | ranked_el_rw | x: . l: List. ranked(x;l)   list_el( ;x;l) |
| THM | rank_fn_unique | x,y: . l: List.
ranked(x;l)  rank_fn(x;l) = rank_fn(y;l)  x = y |
| THM | rank_fn_succ_char | x: . l: List.
ranked(x;l)
 (rank_fn(x;l) = ||l|| - 1   ( k: List. l = (x::k))) |
| THM | ranked_filter | x,y: . l: List.
ranked(x;l)  (x = y)  ranked(x;filter( x. (x = y);l)) |
| DISP | nonranked_df | nonranked(<x:x:*><l:l:*>)== nonranked(<x><l>) |
| ABS | nonranked | nonranked(x;l) == rank_fn(x;l) = -1 |
| THM | nonranked_wf | x: . l: List. nonranked(x;l)   |
| THM | ranked_or_nonranked | x: . l: List. ranked(x;l) nonranked(x;l) |
| DISP | first_occurrences_df | first_occurrences(<l:l:*>)== first_occurrences(<l>) |
| ML | first_occurrences_ml | first_occurrences(l)
==r if null(l)
then []
else hd(l)::filter( x. (x = hd(l));first_occurrences(tl(l)))
fi |
| THM | first_occurrences_wf | l: List. first_occurrences(l) List |
| THM | first_occurrences_char | first_occurrences([]) = []
( y: . l: List.
first_occurrences(y::l)
= (y::filter( x. (x = y);first_occurrences(l)))) |
| COM | sci_rank_2 | ---- Pid versions of theorems needed(?) for rank --------- |
| THM | filter_eq_pid | x:PId. l:PId List. P:PId  .
 (P x)  filter( y. (y = x);filter(P;l)) = filter(P;l) |
| THM | filter_eq_int_false_pid | P,Q:PId  . x:PId. l:PId List.
 (Q x)
 ( y:PId. (x = y)  ( (Q y)   (P y)))
 filter(Q;l) = filter( y. (y = x);filter(P;l)) |
| THM | rank_fn_el_pid | x:PId. l:PId List. rank_fn(x;l) 0  list_el(PId;x;l) |
| THM | rank_fn_succ_char_pid | x:PId. l:PId List.
ranked(x;l)
 (rank_fn(x;l) = ||l|| - 1   ( k:PId List. l = (x::k))) |
| THM | rank_fn_le_filter_pid | p,q,r:PId. l:PId List.
ranked(r;l)
 ranked(q;l)
 (p = r)
 (p = q)
 (rank_fn(r;l) rank_fn(q;l)
  rank_fn(r;filter( x. (x = p);l)) rank_fn(q;filter( x. (x
= p);l))) |
| THM | rank_fn_lt_filter_pid | p,q,r:PId. l:PId List.
ranked(r;l)
 ranked(q;l)
 (p = r)
 (p = q)
 (rank_fn(r;l) < rank_fn(q;l)
  rank_fn(r;filter( x. (x = p);l)) < rank_fn(q;filter( x. (x
= p);l))) |
| THM | rank_fn_succ_filter_pid | p,q,r:PId. l:PId List.
ranked(r;l)
 ranked(q;l)
 (p = r)
 (p = q)
 rank_fn(r;l) = rank_fn(q;l) + 1
 rank_fn(r;filter( x. (x = p);l))
= rank_fn(q;filter( x. (x = p);l)) + 1 |
| THM | rank_fn_zero_filter_pid | p,q:PId. l:PId List.
(p = q)
 rank_fn(q;l) = 0
 rank_fn(q;filter( x. (x = p);l)) = 0 |
| THM | first_occurrences_wf1 | l:PId List. first_occurrences(l) PId List |
| THM | first_occurrences_char1 | first_occurrences([]) = []
( y:PId. l:PId List.
first_occurrences(y::l)
= (y::filter( x. (x = y);first_occurrences(l)))) |
| ML | rank_simpset | map ((simpset_add `rank`) o lemma_simp)
``assert_of_bactive rank_fn_cons``;;
map (simpset_add `rank`) (lemma_simps `first_occurrences_char1`) ;;
% for historic reasons only %
map (simpset_add `base1`) (lemma_simps `first_occurrences_char1`) ;;
|
| COM | sci_rank_3 | ---- SCI Rank -------------------------------------------- |
| DISP | query_received_hist_df | query_received_hist(<s:s:*>)== query_received_hist(<s>) |
| ABS | query_received_hist | query_received_hist(s) ==
filter( he.(he.send? = false)
 ((he.mesg.type = read_cache_freshQ)
 (he.mesg.type = read_cache_goneQ));s.h) |
| THM | query_received_hist_wf | s:state. query_received_hist(s) hist |
| DISP | query_received_queue_df | query_received_queue(<s:s:*>)== query_received_queue(<s>) |
| ABS | query_received_queue | query_received_queue(s) ==
first_occurrences(map( he.he.src;query_received_hist(s))) |
| THM | query_received_queue_wf | s:state. query_received_queue(s) PId List |
| THM | query_received_queue_char | ( v:id  . query_received_queue(mk_state(v;[])) = [])
( v:id  . he:hist_el. h:hist.
he.send? = false
(he.mesg.type = read_cache_freshQ
he.mesg.type = read_cache_goneQ)
 query_received_queue(mk_state(v;he::h))
= (he.src
::filter( x. (x = he.src);query_received_queue(mk_state(v;
h)))))
( v:id  . he:hist_el. h:hist.
(he.send? = false
(he.mesg.type = read_cache_freshQ
he.mesg.type = read_cache_goneQ))
 query_received_queue(mk_state(v;he::h))
= query_received_queue(mk_state(v;h))) |
| DISP | active_queue_df | active_queue(<s:s:*>)== active_queue(<s>) |
| ABS | active_queue | active_queue(s) == filter( p.bactive(s;p);query_received_queue(s)) |
| THM | active_queue_wf | s:state. active_queue(s) PId List |
| DISP | rank_df | rank(<s:s:*><p:p:*>)== rank(<s><p>) |
| ABS | rank | rank(s;p) == rank_fn(p;active_queue(s)) |
| THM | rank_wf | s:state. p: . rank(s;p)  |
| DISP | hasrank_df | hasrank(<s:s:*><p:p:*>)== hasrank(<s><p>) |
| ABS | hasrank | hasrank(s;p) == rank(s;p) 0 |
| THM | hasrank_wf | s:state. p: . hasrank(s;p)   |
| THM | hasrank_active | s:state. p:PId. hasrank(s;p)  active(s;p) |
| THM | rank_unique | s:state. p,q: . hasrank(s;p)  rank(s;p) = rank(s;q)  p = q |
| DISP | maxrank_df | maxrank(<n:n:*><s:s:*><p:p:*>)== maxrank(<n><s><p>) |
| ABS | maxrank | maxrank(n;s;p) ==
hasrank(s;p) ( q:P. hasrank(s;q)  rank(s;q) rank(s;p)) |
| THM | maxrank_wf | n: . s:state. p: . maxrank(n;s;p)   |
| DISP | smallrank_df | smallrank(<n:n:*><s:s:*><p:p:*><q:q:*>)
== smallrank(<n><s><p><q>) |
| ABS | smallrank | smallrank(n;s;p;q) ==
(entering(s;q) staying(s;q))
rank(s;p) < rank(s;q)
hasrank(s;q)
hasrank(s;p)
( r:P
(entering(s;r) staying(s;r)) rank(s;p) rank(s;r)
 rank(s;q) rank(s;r)) |
| THM | smallrank_wf | n: . s:state. p: . q:PId. smallrank(n;s;p;q)   |
| DISP | maxrank_visiting_df | maxrank_visiting(<n:n:*><s:s:*><p:p:*>)
== maxrank_visiting(<n><s><p>) |
| ABS | maxrank_visiting | maxrank_visiting(n;s;p) ==
visiting(s;p)
hasrank(s;p)
( q:P. visiting(s;q) hasrank(s;q)  rank(s;q) rank(s;p)) |
| THM | maxrank_visiting_wf | n: . s:state. p:PId. maxrank_visiting(n;s;p)   |
| DISP | maxrank_staying_df | maxrank_staying(<n:n:*><s:s:*><p:p:*>)
== maxrank_staying(<n><s><p>) |
| ABS | maxrank_staying | maxrank_staying(n;s;p) ==
staying(s;p)
hasrank(s;p)
( q:P. staying(s;q) hasrank(s;q)  rank(s;q) rank(s;p)) |
| THM | maxrank_staying_wf | n: . s:state. p:PId. maxrank_staying(n;s;p)   |
| DISP | maxrank_active_df | maxrank_active(<n:n:*><s:s:*><p:p:*>)== maxrank_active(<n><s><p>) |
| ABS | maxrank_active | maxrank_active(n;s;p) ==
active(s;p)
hasrank(s;p)
( q:P. active(s;q) hasrank(s;q)  rank(s;q) rank(s;p)) |
| THM | maxrank_active_wf | n: . s:state. p:PId. maxrank_active(n;s;p)   |
| COM | sci_rank_4 | ---- Lemmas for Rank Rewrites ---------------------------- |
| THM | filter_active_iff | s:state. c:com. l:PId List.
( p:PId. active(c s;p)   active(s;p))
 filter( p.bactive(c s;p);l) = filter( p.bactive(s;p);l) |
| THM | filter_neq_active_iff | s:state. c:com. q: . l:PId List.
( p:PId. (p = q)  (active(c s;p)   active(s;p)))
 filter( p.bactive(c s;p);filter( x. (x = q);l))
= filter( p.bactive(s;p);filter( x. (x = q);l)) |
| THM | query_received_hist_cassign_rw | s:state. x:id. e:zexp.
query_received_hist(x:=e s) = query_received_hist(s) |
| THM | query_received_hist_hsend_rw | s:state. p:PId. q: . M:mesg.
query_received_hist([h<-(hsend(p;q;M)::h)] s)
= query_received_hist(s) |
| THM | query_received_hist_hreceive_ni_rw | s:state. p: .
(next_mesg(p;s.h).type = read_cache_freshQ)
 (next_mesg(p;s.h).type = read_cache_goneQ)
 query_received_hist([h<-(hreceive(p;h)::h)] s)
= query_received_hist(s) |
| THM | query_received_hist_hreceive_rw | s:state. p: .
next_mesg(p;s.h).type = read_cache_freshQ
next_mesg(p;s.h).type = read_cache_goneQ
 query_received_hist([h<-(hreceive(p;h)::h)] s)
= (hreceive(p;s.h)::query_received_hist(s)) |
| THM | query_received_queue_cassign_rw | s:state. x:id. e:zexp.
query_received_queue(x:=e s) = query_received_queue(s) |
| THM | query_received_queue_hsend_rw | s:state. p:PId. q: . M:mesg.
query_received_queue([h<-(hsend(p;q;M)::h)] s)
= query_received_queue(s) |
| THM | query_received_queue_hreceive_ni_rw | s:state. p: .
(next_mesg(p;s.h).type = read_cache_freshQ)
 (next_mesg(p;s.h).type = read_cache_goneQ)
 query_received_queue([h<-(hreceive(p;h)::h)] s)
= query_received_queue(s) |
| THM | query_received_queue_hreceive_rw | s:state. p: .
next_mesg(p;s.h).type = read_cache_freshQ
next_mesg(p;s.h).type = read_cache_goneQ
 query_received_queue([h<-(hreceive(p;h)::h)] s)
= (next_he(p;s.h).src
::filter( x. (x = next_he(p;s.h).src);query_received_queue(s)
)) |
| THM | active_queue_cassign_rw | s:state. x:id. e:zexp.
( p:PId. active(x:=e s;p)   active(s;p))
 active_queue(x:=e s) = active_queue(s) |
| THM | active_queue_hsend_rw | s:state. p:PId. q: . M:mesg.
( r:PId. active([h<-(hsend(p;q;M)::h)] s;r)   active(s;r))
 active_queue([h<-(hsend(p;q;M)::h)] s) = active_queue(s) |
| THM | active_queue_hreceive_active_rw | s:state. q: .
next_mesg(q;s.h).type = read_cache_freshQ
next_mesg(q;s.h).type = read_cache_goneQ
 ( p:PId
(p = next_he(q;s.h).src)
 (active([h<-(hreceive(q;h)::h)] s;p)   active(s;p)))
 active([h<-(hreceive(q;h)::h)] s;next_he(q;s.h).src)
 active_queue([h<-(hreceive(q;h)::h)] s)
= (next_he(q;s.h).src
::filter( x. (x = next_he(q;s.h).src);active_queue(s))) |
| THM | active_queue_hreceive_inactive_rw | s:state. q: .
( p:PId. active([h<-(hreceive(q;h)::h)] s;p)   active(s;p))
 active(s;next_he(q;s.h).src)
 active_queue([h<-(hreceive(q;h)::h)] s) = active_queue(s) |
| THM | active_queue_hreceive_ni_rw | s:state. q: .
( p:PId. active([h<-(hreceive(q;h)::h)] s;p)   active(s;p))
 (next_mesg(q;s.h).type = read_cache_freshQ)
 (next_mesg(q;s.h).type = read_cache_goneQ)
 active_queue([h<-(hreceive(q;h)::h)] s) = active_queue(s) |
| THM | active_queue_inactive_rw | s:state. p:PId. x:id. e:zexp.
active(x:=e s;p)
 ( q:PId. (p = q)  (active(x:=e s;q)   active(s;q)))
 active_queue(x:=e s) = filter( x. (x = p);active_queue(s)) |
| THM | active_queue_hsend_inactive_rw | s:state. p,r:PId. M:mesg.
active([h<-(hsend(r;p;M)::h)] s;p)
 ( q:PId
(p = q)
 (active([h<-(hsend(r;p;M)::h)] s;q)   active(s;q)))
 active_queue([h<-(hsend(r;p;M)::h)] s)
= filter( x. (x = p);active_queue(s)) |
| THM | rank_active_cassign_rw | s:state. x:id. e:zexp.
( p:PId. active(x:=e s;p)   active(s;p))
 ( p:PId. rank(x:=e s;p) = rank(s;p)) |
| THM | rank_active_hsend_rw | s:state. p:PId. q: . M:mesg.
( r:PId. active([h<-(hsend(p;q;M)::h)] s;r)   active(s;r))
 ( r:PId. rank([h<-(hsend(p;q;M)::h)] s;r) = rank(s;r)) |
| THM | rank_active_hreceive_inactive_rw | s:state. p:PId. q: .
( p:PId. active([h<-(hreceive(q;h)::h)] s;p)   active(s;p))
 active(s;next_he(q;s.h).src)
 ( p:PId. rank([h<-(hreceive(q;h)::h)] s;p) = rank(s;p)) |
| THM | rank_active_hreceive_ni_rw | s:state. p:PId. q: .
( p:PId. active([h<-(hreceive(q;h)::h)] s;p)   active(s;p))
 (next_mesg(q;s.h).type = read_cache_freshQ)
 (next_mesg(q;s.h).type = read_cache_goneQ)
 ( p:PId. rank([h<-(hreceive(q;h)::h)] s;p) = rank(s;p)) |
| COM | sci_rank_5 | ---- Rank Rewrites --------------------------------------- |
| THM | rank_hsend_gone_rw | s:state. p,q:PId.
status-p_ = Off
 rank([h<-(hsend(p;m;read_cache_goneQ(p::[]))::h)] s;q)
= rank(s;q) |
| THM | rank_hsend_fresh_rw | s:state. p,q:PId.
status-p_ = Off
 rank([h<-(hsend(p;m;read_cache_freshQ(p::[]))::h)] s;q)
= rank(s;q) |
| THM | rank_hsend_reject_rw | s:state. p,q,r:PId.
rank([h<-(hsend(q;p;delleftR(q::zreject{}::[]))::h)] s;r)
= rank(s;r) |
| THM | rank_hsend_ni_rw | s:state. p,q:PId. r: . M:mesg.
(M.type = read_cache_freshQ)
 (M.type = read_cache_goneQ)
 (M.type = delleftR)
 rank([h<-(hsend(q;r;M)::h)] s;p) = rank(s;p) |
| THM | rank_hreceive_ni_rw | s:state. p:PId. q: .
(next_mesg(q;s.h).type = read_cache_freshQ)
 (next_mesg(q;s.h).type = read_cache_goneQ)
 (next_mesg(q;s.h).type = delleftR)
 (next_mesg(q;s.h).type = 0)
 rank([h<-(hreceive(q;h)::h)] s;p) = rank(s;p) |
| THM | rank_delleftr_reject_rw | s:state. p:PId. q: .
( qq: . next_mesg(q;s.h) = delleftR(qq::zreject{}::[]))
 rank([h<-(hreceive(q;h)::h)] s;p) = rank(s;p) |
| THM | rank_diff_id_rw | s:state. p:PId. x:id. e:zexp.
((x.name) = "status")
 ((x.name) = "cs")
 rank(x:=e s;p) = rank(s;p) |
| THM | rank_znil_assign_rw | s:state. p:PId. x:Atom. e:zexp. rank(xnil:=e s;p) = rank(s;p) |
| THM | rank_pending_rw | s:state. p:PId. q:PId?.
list_el(mesg;read_cache_freshQ(q::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(q::[]);buf[m]_)
 rank(statusq:=Pending s;p) = rank(s;p) |
| THM | rank_pending_inqueue_rw | s:state. p:PId. q:PId?.
status-q_ = Pending  rank(statusq:=Inqueue s;p) = rank(s;p) |
| THM | rank_pending_inlist_rw | s:state. p:PId. q:PId?.
status-q_ = Pending  rank(statusq:=Inlist s;p) = rank(s;p) |
| THM | rank_inqueue_inlist_rw | s:state. p:PId. q:PId?.
status-q_ = Inqueue  rank(statusq:=Inlist s;p) = rank(s;p) |
| THM | rank_inlist_purging_rw | s:state. p:PId. q:PId?.
status-q_ = Inlist  rank(statusq:=Purging s;p) = rank(s;p) |
| THM | rank_inlist_ftod_rw | s:state. p:PId. q:PId?.
status-q_ = Inlist  rank(statusq:=Ftod s;p) = rank(s;p) |
| THM | rank_ftod_inlist_rw | s:state. p:PId. q:PId?.
status-q_ = Ftod  rank(statusq:=Inlist s;p) = rank(s;p) |
| THM | rank_inlist_delright_rw | s:state. p:PId. q:PId?.
status-q_ = Inlist
 (cs-q_ = invalid{})
 ( qq: . list_el(mesg;delleftR(qq::ok{}::[]);buf[q]_))
 rank(statusq:=Delright s;p) = rank(s;p) |
| THM | rank_inlist_delleft_rw | s:state. p:PId. q:PId?.
status-q_ = Inlist
 (cs-q_ = invalid{})
 ( qq: . list_el(mesg;delleftR(qq::ok{}::[]);buf[q]_))
 rank(statusq:=Delleft s;p) = rank(s;p) |
| THM | rank_delright_off_rw | s:state. p:PId. q:PId?.
status-q_ = Delright
 cs-q_ = invalid{}
 rank(statusq:=Off s;p) = rank(s;p) |
| THM | rank_delright_inlist_rw | s:state. p:PId. q:PId?.
status-q_ = Delright
 (cs-q_ = invalid{})
 ( qq: . list_el(mesg;delleftR(qq::ok{}::[]);buf[q]_))
 rank(statusq:=Inlist s;p) = rank(s;p) |
| THM | rank_delright_delleft_rw | s:state. p:PId. q:PId?.
status-q_ = Delright  rank(statusq:=Delleft s;p) = rank(s;p) |
| THM | rank_delleft_off_rw | s:state. p:PId. q:PId?.
status-q_ = Delleft
 cs-q_ = invalid{}
 rank(statusq:=Off s;p) = rank(s;p) |
| THM | rank_purging_inlist_rw | s:state. p:PId. q:PId?.
status-q_ = Purging  rank(statusq:=Inlist s;p) = rank(s;p) |
| THM | rank_cs_ni_rw | s:state. p:PId. q:PId?. e:zexp.
(status-q_ = Delleft)
 (status-q_ = Delright)
 rank(csq:=e s;p) = rank(s;p) |
| COM | sci_rank_6 | ---- hasrank Rewrites ------------------------------------ |
| THM | hasrank_hsend_gone_rw | s:state. p,q:PId.
status-p_ = Off
 (hasrank([h<-(hsend(p;m;read_cache_goneQ(p::[]))::h)] s;q)
  hasrank(s;q)) |
| THM | hasrank_hsend_fresh_rw | s:state. p,q:PId.
status-p_ = Off
 (hasrank([h<-(hsend(p;m;read_cache_freshQ(p::[]))::h)] s;q)
  hasrank(s;q)) |
| THM | hasrank_hsend_reject_rw | s:state. p,q,r:PId.
hasrank([h<-(hsend(q;p;delleftR(q::zreject{}::[]))::h)] s;r)
  hasrank(s;r) |
| THM | hasrank_hsend_ni_rw | s:state. p,q:PId. r: . M:mesg.
(M.type = read_cache_freshQ)
 (M.type = read_cache_goneQ)
 (M.type = delleftR)
 (hasrank([h<-(hsend(q;r;M)::h)] s;p)   hasrank(s;p)) |
| THM | hasrank_hreceive_ni_rw | s:state. p:PId. q: .
(next_mesg(q;s.h).type = read_cache_freshQ)
 (next_mesg(q;s.h).type = read_cache_goneQ)
 (next_mesg(q;s.h).type = delleftR)
 (next_mesg(q;s.h).type = 0)
 (hasrank([h<-(hreceive(q;h)::h)] s;p)   hasrank(s;p)) |
| THM | hasrank_delleftr_reject_rw | s:state. p:PId. q: .
( qq: . next_mesg(q;s.h) = delleftR(qq::zreject{}::[]))
 (hasrank([h<-(hreceive(q;h)::h)] s;p)   hasrank(s;p)) |
| THM | hasrank_diff_id_rw | s:state. p:PId. x:id. e:zexp.
((x.name) = "status")
 ((x.name) = "cs")
 (hasrank(x:=e s;p)   hasrank(s;p)) |
| THM | hasrank_znil_assign_rw | s:state. p:PId. x:Atom. e:zexp.
hasrank(xnil:=e s;p)   hasrank(s;p) |
| THM | hasrank_pending_rw | s:state. p:PId. q:PId?.
list_el(mesg;read_cache_freshQ(q::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(q::[]);buf[m]_)
 (hasrank(statusq:=Pending s;p)   hasrank(s;p)) |
| THM | hasrank_pending_inqueue_rw | s:state. p:PId. q:PId?.
status-q_ = Pending
 (hasrank(statusq:=Inqueue s;p)   hasrank(s;p)) |
| THM | hasrank_pending_inlist_rw | s:state. p:PId. q:PId?.
status-q_ = Pending
 (hasrank(statusq:=Inlist s;p)   hasrank(s;p)) |
| THM | hasrank_inqueue_inlist_rw | s:state. p:PId. q:PId?.
status-q_ = Inqueue
 (hasrank(statusq:=Inlist s;p)   hasrank(s;p)) |
| THM | hasrank_inlist_purging_rw | s:state. p:PId. q:PId?.
status-q_ = Inlist
 (hasrank(statusq:=Purging s;p)   hasrank(s;p)) |
| THM | hasrank_inlist_ftod_rw | s:state. p:PId. q:PId?.
status-q_ = Inlist  (hasrank(statusq:=Ftod s;p)   hasrank(s;p)) |
| THM | hasrank_ftod_inlist_rw | s:state. p:PId. q:PId?.
status-q_ = Ftod  (hasrank(statusq:=Inlist s;p)   hasrank(s;p)) |
| THM | hasrank_inlist_delright_rw | s:state. p:PId. q:PId?.
status-q_ = Inlist
 (cs-q_ = invalid{})
 ( qq: . list_el(mesg;delleftR(qq::ok{}::[]);buf[q]_))
 (hasrank(statusq:=Delright s;p)   hasrank(s;p)) |
| THM | hasrank_inlist_delleft_rw | s:state. p:PId. q:PId?.
status-q_ = Inlist
 (cs-q_ = invalid{})
 ( qq: . list_el(mesg;delleftR(qq::ok{}::[]);buf[q]_))
 (hasrank(statusq:=Delleft s;p)   hasrank(s;p)) |
| THM | hasrank_delright_off_rw | s:state. p:PId. q:PId?.
status-q_ = Delright
 cs-q_ = invalid{}
 (hasrank(statusq:=Off s;p)   hasrank(s;p)) |
| THM | hasrank_delright_inlist_rw | s:state. p:PId. q:PId?.
status-q_ = Delright
 (cs-q_ = invalid{})
 ( qq: . list_el(mesg;delleftR(qq::ok{}::[]);buf[q]_))
 (hasrank(statusq:=Inlist s;p)   hasrank(s;p)) |
| THM | hasrank_delright_delleft_rw | s:state. p:PId. q:PId?.
status-q_ = Delright
 (hasrank(statusq:=Delleft s;p)   hasrank(s;p)) |
| THM | hasrank_delleft_off_rw | s:state. p:PId. q:PId?.
status-q_ = Delleft
 cs-q_ = invalid{}
 (hasrank(statusq:=Off s;p)   hasrank(s;p)) |
| THM | hasrank_purging_inlist_rw | s:state. p:PId. q:PId?.
status-q_ = Purging
 (hasrank(statusq:=Inlist s;p)   hasrank(s;p)) |
| THM | hasrank_cs_ni_rw | s:state. p:PId. q:PId?. e:zexp.
(status-q_ = Delleft)
 (status-q_ = Delright)
 (hasrank(csq:=e s;p)   hasrank(s;p)) |
| THM | hasrank_off_diff_rw | s:state. p,r:PId.
(p = r)  (hasrank(statusp:=Off s;r)   hasrank(s;r)) |
| THM | hasrank_invalid_diff_rw | s:state. p,r:PId.
(p = r)  (hasrank(csp:=invalid{} s;r)   hasrank(s;r)) |
| THM | hasrank_delleftr_diff_rw | s:state. p,q,r:PId.
(p = r)
 (hasrank([h<-(hsend(q;p;delleftR(q::ok{}::[]))::h)] s;r)
  hasrank(s;r)) |
| THM | hasrank_hreceive_freshq_rw | s:state. p:PId.
next_mesg(m;s.h) = read_cache_freshQ(next_he(m;s.h).src::[])
 (next_he(m;s.h).src = p)
 (hasrank([h<-(hreceive(m;h)::h)] s;p)   hasrank(s;p)) |
| THM | hasrank_hreceive_goneq_rw | s:state. p:PId.
next_mesg(m;s.h) = read_cache_goneQ(next_he(m;s.h).src::[])
 (next_he(m;s.h).src = p)
 (hasrank([h<-(hreceive(m;h)::h)] s;p)   hasrank(s;p)) |
| ML | sci_pred2_simpset | map ((simpset_add `sci_pred2`) o lemma_simp)
``rank_znil_assign_rw hasrank_znil_assign_rw
rank_hsend_reject_rw hasrank_hsend_reject_rw`` ;;
map (simpset_add `sci_pred2`)
[lemma_cond_simp `rank_diff_id_rw` [DiffIdName];
lemma_cond_simp `rank_pending_rw` [BufSimpCond];
lemma_cond_simp `rank_pending_inqueue_rw` [PendingSimpCond];
lemma_cond_simp `rank_pending_inlist_rw` [PendingSimpCond];
lemma_cond_simp `rank_inqueue_inlist_rw` [InqueueSimpCond];
lemma_cond_simp `rank_inlist_purging_rw` [InlistSimpCond];
lemma_cond_simp `rank_inlist_ftod_rw` [InlistSimpCond];
lemma_cond_simp `rank_ftod_inlist_rw` [FtodSimpCond];
lemma_cond_simp `rank_inlist_delright_rw` [InlistSimpCond;IdSimpCon
d;BufSimpCond];
lemma_cond_simp `rank_inlist_delleft_rw` [InlistSimpCond;IdSimpCond
;BufSimpCond];
lemma_cond_simp `rank_delright_off_rw` [IdSimpCond];
lemma_cond_simp `rank_delright_inlist_rw` [DelrightSimpCond;IdSimpC
ond;BufSimpCond];
lemma_cond_simp `rank_delright_delleft_rw` [DelrightSimpCond];
lemma_cond_simp `rank_delleft_off_rw` [DelleftSimpCond;IdSimpCond];
lemma_cond_simp `rank_purging_inlist_rw` [PurgingSimpCond];
lemma_cond_simp `rank_cs_ni_rw` [EvalExpCond];
lemma_cond_simp `rank_hsend_fresh_rw` [IdSimpCond];
lemma_cond_simp `rank_hsend_gone_rw` [IdSimpCond];
lemma_cond_simp `rank_hsend_ni_rw` [DiffMesgTypesOrTrivial];
lemma_cond_simp `rank_hreceive_ni_rw` [DiffRecTypes];
lemma_cond_simp `rank_delleftr_reject_rw` [InstDelleftR];
lemma_cond_simp `hasrank_diff_id_rw` [DiffIdName];
lemma_cond_simp `hasrank_pending_rw` [BufSimpCond];
lemma_cond_simp `hasrank_pending_inqueue_rw` [PendingSimpCond];
lemma_cond_simp `hasrank_pending_inlist_rw` [PendingSimpCond];
lemma_cond_simp `hasrank_inqueue_inlist_rw` [InqueueSimpCond];
lemma_cond_simp `hasrank_inlist_purging_rw` [InlistSimpCond];
lemma_cond_simp `hasrank_inlist_ftod_rw` [InlistSimpCond];
lemma_cond_simp `hasrank_ftod_inlist_rw` [FtodSimpCond];
lemma_cond_simp `hasrank_inlist_delright_rw` [InlistSimpCond;IdSimp
Cond;BufSimpCond];
lemma_cond_simp `hasrank_inlist_delleft_rw` [InlistSimpCond;IdSimpC
ond;BufSimpCond];
lemma_cond_simp `hasrank_delright_off_rw` [IdSimpCond];
lemma_cond_simp `hasrank_delright_inlist_rw` [DelrightSimpCond;IdSi
mpCond;BufSimpCond];
lemma_cond_simp `hasrank_delright_delleft_rw` [DelrightSimpCond];
lemma_cond_simp `hasrank_delleft_off_rw` [DelleftSimpCond;IdSimpCon
d];
lemma_cond_simp `hasrank_purging_inlist_rw` [PurgingSimpCond];
lemma_cond_simp `hasrank_cs_ni_rw` [EvalExpCond];
lemma_cond_simp `hasrank_hsend_fresh_rw` [IdSimpCond];
lemma_cond_simp `hasrank_hsend_gone_rw` [IdSimpCond];
lemma_cond_simp `hasrank_hsend_ni_rw` [DiffMesgTypesOrTrivial];
lemma_cond_simp `hasrank_hreceive_ni_rw` [DiffRecTypes];
lemma_cond_simp `hasrank_delleftr_reject_rw` [InstDelleftR];
lemma_cond_simp `hasrank_delleftr_diff_rw` [DiffBufferPids];
lemma_cond_simp `hasrank_off_diff_rw` [DiffBufferPids];
lemma_cond_simp `hasrank_invalid_diff_rw` [DiffBufferPids];
lemma_cond_simp `hasrank_hreceive_freshq_rw` [SameRecMesg;DiffRecSr
c];
lemma_cond_simp `hasrank_hreceive_goneq_rw` [SameRecMesg;DiffRecSrc
]
];; |
| COM | sci_rank_7 | ---- Rank Rewrites for Action p15 ------------------------ |
| THM | rank_p15_invalid_rw | s:state. p,r:PId. argval,qval: .
status-p_ = Delleft
 cs-p_ = invalid{}
 next_mesg(p;s.h).type = delleftR
 rank(statusp:=Off
(csp:=invalid{}
(predp:=nil
(succp:=nil
([h<-(hreceive(p;h)::h)] ("arg"nil:=argval (q:=qval s))))));r)
= rank(s;r) |
| THM | rank_p15_delleftr_rw | s:state. p,r:PId. argval,qval: .
status-p_ = Delleft
 ( qq: . delleftR(qq::ok{}::[]) buf[p]_)
 next_mesg(p;s.h).type = delleftR
 rank(statusp:=Off
(csp:=invalid{}
(predp:=nil
(succp:=nil
([h<-(hreceive(p;h)::h)] ("arg"nil:=argval (q:=qval s))))));r)
= rank(s;r) |
| THM | hasrank_p15_invalid_rw | s:state. p,r:PId. argval,qval: .
status-p_ = Delleft
 cs-p_ = invalid{}
 next_mesg(p;s.h).type = delleftR
 (hasrank(statusp:=Off
(csp:=invalid{}
(predp:=nil
(succp:=nil
([h<-(hreceive(p;h)::h)] ("arg"nil:=argval (q:=qval s))))));r)
  hasrank(s;r)) |
| THM | hasrank_p15_delleftr_rw | s:state. p,r:PId. argval,qval: .
status-p_ = Delleft
 ( qq: . delleftR(qq::ok{}::[]) buf[p]_)
 next_mesg(p;s.h).type = delleftR
 (hasrank(statusp:=Off
(csp:=invalid{}
(predp:=nil
(succp:=nil
([h<-(hreceive(p;h)::h)] ("arg"nil:=argval (q:=qval s))))));r)
  hasrank(s;r)) |
| ML | rank_p15_simpset | % map ((simpset_add `rank_p15`) o lemma_simp) ``rank_p15_delleftr_rw``
;; %
map (simpset_add `rank_p15`)
[lemma_cond_simp `rank_p15_invalid_rw` [IdSimpCond;IdSimpCond;DiffRe
cTypes];
lemma_cond_simp `rank_p15_delleftr_rw` [IdSimpCond;InstDelleftR;Dif
fRecTypes];
lemma_cond_simp `hasrank_p15_invalid_rw` [IdSimpCond;IdSimpCond;Dif
fRecTypes];
lemma_cond_simp `hasrank_p15_delleftr_rw` [IdSimpCond;InstDelleftR;
DiffRecTypes]
] ;; |
| COM | sci_rank_8 | ---- Rank Comparison Rewrites ---------------------------- |
| THM | rank_le_off_diff_rw | s:state. p,q,r:PId.
hasrank(s;r)
 hasrank(s;q)
 (p = r)
 (p = q)
 (rank(s;r) rank(s;q)
  rank(statusp:=Off s;r) rank(statusp:=Off s;q)) |
| THM | rank_le_invalid_diff_rw | s:state. p,q,r:PId.
hasrank(s;r)
 hasrank(s;q)
 (p = r)
 (p = q)
 (rank(s;r) rank(s;q)
  rank(csp:=invalid{} s;r) rank(csp:=invalid{} s;q)) |
| THM | rank_le_delleftr_diff_rw | s:state. p,q,r,p':PId.
hasrank(s;r)
 hasrank(s;q)
 (p = r)
 (p = q)
 (rank(s;r) rank(s;q)
  rank([h<-(hsend(p';p;delleftR(p'::ok{}::[]))::h)]
s;r) rank([h<-(hsend(p';p;delleftR(p'::ok{}::[]))::h)]
s;q)) |
| THM | rank_le_query_diff_rw | s:state. q,r:PId.
hasrank(s;r)
 hasrank(s;q)
 next_mesg(m;s.h) = read_cache_freshQ(next_he(m;s.h).src::[])
next_mesg(m;s.h) = read_cache_goneQ(next_he(m;s.h).src::[])
 (next_he(m;s.h).src = q)
 (next_he(m;s.h).src = r)
 (rank(s;r) rank(s;q)
  rank([h<-(hreceive(m;h)::h)] s;r) rank([h<-(hreceive(m;h)
::h)]
s;q)) |
| COM | sci_rank_9 | ---- One-Directional Rank Comparison Lemmas--------------- |
| THM | rank_succ_off_diff | s:state. p,q,r:PId.
hasrank(s;r)
 hasrank(s;q)
 (p = r)
 (p = q)
 rank(s;r) = rank(s;q) + 1
 rank(statusp:=Off s;r) = rank(statusp:=Off s;q) + 1 |
| THM | rank_succ_invalid_diff | s:state. p,q,r:PId.
hasrank(s;r)
 hasrank(s;q)
 (p = r)
 (p = q)
 rank(s;r) = rank(s;q) + 1
 rank(csp:=invalid{} s;r) = rank(csp:=invalid{} s;q) + 1 |
| THM | rank_succ_delleftr_diff | s:state. p,q,r,p':PId.
hasrank(s;r)
 hasrank(s;q)
 (p = r)
 (p = q)
 rank(s;r) = rank(s;q) + 1
 rank([h<-(hsend(p';p;delleftR(p'::ok{}::[]))::h)] s;r)
= rank([h<-(hsend(p';p;delleftR(p'::ok{}::[]))::h)] s;q) + 1 |
| THM | rank_succ_query_diff | s:state. q,r:PId.
hasrank(s;r)
 hasrank(s;q)
 next_mesg(m;s.h) = read_cache_freshQ(next_he(m;s.h).src::[])
next_mesg(m;s.h) = read_cache_goneQ(next_he(m;s.h).src::[])
 (next_he(m;s.h).src = q)
 (next_he(m;s.h).src = r)
 rank(s;r) = rank(s;q) + 1
 rank([h<-(hreceive(m;h)::h)] s;r) = rank([h<-(hreceive(m;h)::h)]
s;q)
+ 1 |
| COM | sci_rank_10 | ---- Rank Zero Lemmas ------------------------------------ |
| THM | rank_zero_invalid_diff | s:state. p,q:PId.
(p = q)  rank(s;q) = 0  rank(csp:=invalid{} s;q) = 0 |