Nuprl Theory sci_misc

(only non hidden objects are presented)

COMsci_misc_01---- Objects that would be in above theories, but were
COMsci_misc_02 created after these theories were declared done. ----
COMsci_misc_base_0---- sci_base: Basic List lemmas -------------------------
THMfilter_mt'a:S. l:'a List. P:'a . mt(filter(P;filter(x.(P x);l)))
THMlist_el_1_filtery:. l: List. list_el(;y;l) ||filter(x.(x = y);l)|| 1
COMsci_misc_pred_12---- sci_pred: Staying Rewrites --------------------------
THMstaying_cs_ni_rws:state. p:PId. q:PId?. e:zexp. (status-q_ = Delleft) (status-q_ = Delright) (staying(csq:=es;p) staying(s;p))
THMstaying_inlist_rws:state. p:PId. staying(statusp:=Inlists;p) list_el(mesg;read_cache_freshQ(p::[]);buf[m]_) list_el(mesg;read_cache_goneQ(p::[]);buf[m]_) (qq:. list_el(mesg;delrightR(qq::ok{}::[]);buf[p]_))
THMstaying_inqueue_rws:state. p:PId. staying(statusp:=Inqueues;p) False
THMstaying_hsend_ni_rws:state. p:PId. q:. r:PId. T:. args: List. (T = read_cache_freshQ) (T = read_cache_goneQ) (T = delleftR) (T = delrightR) (staying([h<-(hsend(r;q;T(args))::h)]s;p) staying(s;p))
THMstaying_hreceive_ni_rws: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 = delrightR) (next_mesg(q;s.h).type = 0) (staying([h<-(hreceive(q;h)::h)]s;p) staying(s;p))
THMstaying_hreceive_diff_rws:state. p:PId. q:. (q = p) (q = m) (next_mesg(q;s.h).type = 0) (staying([h<-(hreceive(q;h)::h)]s;p) staying(s;p))
THMstaying_znil_rws:state. p:PId. x:Atom. e:zexp. staying(xnil:=es;p) staying(s;p)
MLsci_staying_simpsetmap ((simpset_add `sci_staying`) o lemma_simp) ``staying_inlist_rw staying_inqueue_rw staying_znil_rw`` ;; map (simpset_add `sci_staying`) [lemma_cond_simp `staying_cs_ni_rw` [IdSimpCond]; lemma_cond_simp `staying_diff_id_rw` [DiffIds ORELSE (Unab ``mk_id` ` THEN DiffId)]; lemma_cond_simp `staying_hsend_ni_rw` [DiffMesgTypesOrTrivial]; lemma_cond_simp `staying_hreceive_diff_rw` [DiffBufferPids;ProcNotM em;DiffRecTypes] ];;
COMsci_misc_rank_1---- sci_rank: General Definitions and Theorems ----------
THMrank_fn_nilx:. rank_fn(x;[]) = -1
THMrank_fn_zero_snocx:. l: List. list_el(;x;l) rank_fn(x;snoc(x;l)) = 0
THMranked_consx,y:. l: List. ranked(x;y::l) x = y ranked(x;l)
COMsci_misc_rank_2---- sci_rank: Pid versions of theorems needed(?) for rank
THMrank_0_snoc_pidx:PId. l:PId List. rank_fn(x;l) = 0 (l':PId List. l = snoc(x;l'))
THMrank_1_snoc_pidx:PId. l:PId List. rank_fn(x;l) = 1 (y:PId. l':PId List. l = snoc(y;snoc(x;l')))
THMrank_filter_hd_pidp,q:PId. l:PId List. ranked(q;l) rank_fn(p;l) = ||l|| - 1 rank_fn(q;l) = ||l|| - 2 rank_fn(q;filter(x.(x = p);l)) = ||filter(x.(x = p);l)|| - 1
THMrank_fn_two_filter_pidp,q,r:PId. l:PId List. ranked(q;l) (p = r) (p = q) rank_fn(p;l) = rank_fn(q;l) + 1 rank_fn(r;l) = rank_fn(p;l) + 1 rank_fn(r;filter(x.(x = p);l)) = rank_fn(q;filter(x.(x = p);l)) + 1
THMfirst_occ_1_filter_pidy:PId. l:PId List. ||filter(x.(x = y);first_occurrences(l))|| 1
MLrank_simpset1map ((simpset_add `rank`) o lemma_simp) ``rank_fn_nil ranked_cons``;;
COMsci_misc_rank_6---- sci_rank: hasrank Rewrites --------------------------
THMhasrank_hreceive_freshq_same_rws:state. p:PId. next_mesg(m;s.h) = read_cache_freshQ(p::[]) status-p_ = Pending list_el(mesg;read_cache_freshQ(p::[]);but_last_el(buf[m]_)) list_el(mesg;read_cache_goneQ(p::[]);buf[m]_) next_he(m;s.h).src = p (hasrank([h<-(hreceive(m;h)::h)]s;p) True)
THMhasrank_hreceive_goneq_same_rws:state. p:PId. next_mesg(m;s.h) = read_cache_goneQ(p::[]) status-p_ = Pending list_el(mesg;read_cache_goneQ(p::[]);but_last_el(buf[m]_)) list_el(mesg;read_cache_freshQ(p::[]);buf[m]_) next_he(m;s.h).src = p (hasrank([h<-(hreceive(m;h)::h)]s;p) True)
COMsci_misc_rank_9---- sci_rank: One-Directional Rank Comparison Lemmas-----
THMrank_succ_two_invalids:state. p,q,r:PId. status-q_ = Delright status-q_ = Delleft hasrank(s;r) rank(s;p) = rank(s;q) + 1 rank(s;q) = rank(s;r) + 1 rank(csq:=invalid{}s;p) = rank(csq:=invalid{}s;r) + 1
THMrank_succ_two_offs:state. p,q,r:PId. hasrank(s;r) rank(s;p) = rank(s;q) + 1 rank(s;q) = rank(s;r) + 1 rank(statusq:=Offs;p) = rank(statusq:=Offs;r) + 1
COMsci_misc_rank_10---- sci_rank: Rank Zero Lemmas --------------------------
THMrank_zero_off_diffs:state. p,q:PId. hasrank(s;q) (p = q) rank(s;q) = 0 rank(statusp:=Offs;q) = 0
THMrank_zero_delleftr_diffs:state. p,q,p':PId. hasrank(s;q) (p = q) rank(s;q) = 0 rank([h<-(hsend(p';p;delleftR(p'::ok{}::[]))::h)]s;q) = 0
THMrank_zero_query_diffs:state. q:PId. 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) rank(s;q) = 0 rank([h<-(hreceive(m;h)::h)]s;q) = 0
THMrank_zero_one_delleftrs:state. p,q,p':PId. status-p_ = Delleft rank(s;p) = 0 rank(s;q) = 1 rank([h<-(hsend(p';p;delleftR(p'::ok{}::[]))::h)]s;q) = 0
THMrank_zero_one_invalids:state. p,q:PId. status-p_ = Delleft rank(s;p) = 0 rank(s;q) = 1 rank(csp:=invalid{}s;q) = 0
THMrank_zero_one_invalid_dels:state. p,q:PId. status-p_ = Delright status-p_ = Delleft rank(s;p) = 0 rank(s;q) = 1 rank(csp:=invalid{}s;q) = 0
THMrank_zero_one_offs:state. p,q:PId. rank(s;p) = 0 rank(s;q) = 1 rank(statusp:=Offs;q) = 0
COMsci_misc_rank_11---- Maxrank Lemmas --------------------------------------
THMmaxrank_hreceive_freshq_rwn:. s:state. p:PId. next_mesg(m;s.h) = read_cache_freshQ(p::[]) status-p_ = Pending list_el(mesg;read_cache_freshQ(p::[]);but_last_el(buf[m]_)) list_el(mesg;read_cache_goneQ(p::[]);buf[m]_) next_he(m;s.h).src = p (maxrank(n;[h<-(hreceive(m;h)::h)]s;p) True)
THMmaxrank_hreceive_goneq_rwn:. s:state. p:PId. next_mesg(m;s.h) = read_cache_goneQ(p::[]) status-p_ = Pending list_el(mesg;read_cache_goneQ(p::[]);but_last_el(buf[m]_)) list_el(mesg;read_cache_freshQ(p::[]);buf[m]_) next_he(m;s.h).src = p (maxrank(n;[h<-(hreceive(m;h)::h)]s;p) True)
COMsci_misc_inv9b_5---- sci_inv9b: Some consequences introduced by Amy ------
THMnext_mesg_only_responsen: inv{}(sci_program{}(n); s.(p,msgR:. args,args': List. response(msgR) next_mesg(p;s.h) = msgR(args) list_el(mesg;msgR(args');but_last_el(buf[p]_))))
COMsci_misc_inv_rw_12---- sci_inv_rw: NonInterference Theorems for Staying ----
THMstaying_ni_m1n:. s:state. in_exec{}(sci_program{}(n); s) (q:P. staying(action_m1{}s;q) staying(s;q))
THMstaying_ni_m2n:. s:state. in_exec{}(sci_program{}(n); s) (q:P. staying(action_m2{}s;q) staying(s;q))
THMstaying_ni_m3n:. s:state. in_exec{}(sci_program{}(n); s) (q:P. staying(action_m3{}s;q) staying(s;q))
THMstaying_ni_m4n:. s:state. in_exec{}(sci_program{}(n); s) (q:P. staying(action_m4{}s;q) staying(s;q))
THMstaying_ni_p1n:. s:state. in_exec{}(sci_program{}(n); s) (p,q:P. staying(action_p1{}(p)s;q) staying(s;q))
THMstaying_ni_p2n:. s:state. in_exec{}(sci_program{}(n); s) (p,q:P. staying(action_p2{}(p)s;q) staying(s;q))
THMstaying_ni_p3n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. (p = q) (staying(action_p3{}(p)s;q) staying(s;q)))
THMstaying_ni_p4n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. (p = q) (staying(action_p4{}(p)s;q) staying(s;q)))
THMstaying_ni_p5n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. staying(action_p5{}(p)s;q) staying(s;q))
THMstaying_ni_p6n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. (p = q) (staying(action_p6{}(p)s;q) staying(s;q)))
THMstaying_ni_p7n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. staying(action_p7{}(p)s;q) staying(s;q))
THMstaying_ni_p8n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. staying(action_p8{}(p)s;q) staying(s;q))
THMstaying_ni_p9n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. staying(action_p9{}(p)s;q) staying(s;q))
THMstaying_ni_p13n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. staying(action_p13{}(p)s;q) staying(s;q))
THMstaying_ni_p14n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. staying(action_p14{}(p)s;q) staying(s;q))
THMstaying_ni_p15n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. staying(action_p15{}(p)s;q) staying(s;q))
THMstaying_ni_p16n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. (p = q) (staying(action_p16{}(p)s;q) staying(s;q)))
THMstaying_ni_p17n:. s:state. in_exec{}(sci_program{}(n); s) (p:P. q:PId. staying(action_p17{}(p)s;q) staying(s;q))
MLsci_staying_ni_simpsetmap ((simpset_add `sci_staying_ni`) o lemma_simp) ``staying_ni_m1 staying_ni_m2 staying_ni_m3 staying_ni_m4 staying_ni_p1 staying_ni_p2 staying_ni_p5 staying_ni_p7 staying_ni_p8 staying_ni_p9 staying_ni_p13 staying_ni_p14 staying_ni_p15 staying_ni_p17`` ;; map (simpset_add `sci_visiting_ni`) [lemma_cond_simp `staying_ni_p3` [Trivial ORELSE DiffBufferPids]; lemma_cond_simp `staying_ni_p4` [Trivial ORELSE DiffBufferPids]; lemma_cond_simp `staying_ni_p6` [Trivial ORELSE DiffBufferPids]; lemma_cond_simp `visiting_ni_p16` [Trivial ORELSE DiffBufferPids] ] ;;

the other theories