src/HOLCF/IOA/meta_theory/ShortExecutions.ML
changeset 3457 a8ab7c64817c
parent 3433 2de17c994071
child 3847 d5905b98291f
equal deleted inserted replaced
3456:fdb1768ebd3e 3457:a8ab7c64817c
    45 qed"oraclebuild_nil";
    45 qed"oraclebuild_nil";
    46 
    46 
    47 goal thy "oraclebuild P`s`(x>>t) = \
    47 goal thy "oraclebuild P`s`(x>>t) = \
    48 \         (Takewhile (%a.~ P a)`s)   \
    48 \         (Takewhile (%a.~ P a)`s)   \
    49 \          @@ (x>>(oraclebuild P`(TL`(Dropwhile (%a.~ P a)`s))`t))";     
    49 \          @@ (x>>(oraclebuild P`(TL`(Dropwhile (%a.~ P a)`s))`t))";     
    50 br trans 1;
    50 by (rtac trans 1);
    51 by (stac oraclebuild_unfold 1);
    51 by (stac oraclebuild_unfold 1);
    52 by (asm_full_simp_tac (!simpset addsimps [Cons_def]) 1);
    52 by (asm_full_simp_tac (!simpset addsimps [Cons_def]) 1);
    53 by (simp_tac (!simpset addsimps [Cons_def]) 1);
    53 by (simp_tac (!simpset addsimps [Cons_def]) 1);
    54 qed"oraclebuild_cons";
    54 qed"oraclebuild_cons";
    55 
    55 
    63 goalw thy [Cut_def]
    63 goalw thy [Cut_def]
    64 "!! s. [| Forall (%a.~ P a) s; Finite s|] \
    64 "!! s. [| Forall (%a.~ P a) s; Finite s|] \
    65 \           ==> Cut P s =nil";
    65 \           ==> Cut P s =nil";
    66 by (subgoal_tac "Filter P`s = nil" 1);
    66 by (subgoal_tac "Filter P`s = nil" 1);
    67 by (asm_simp_tac (!simpset addsimps [oraclebuild_nil]) 1);
    67 by (asm_simp_tac (!simpset addsimps [oraclebuild_nil]) 1);
    68 br ForallQFilterPnil 1;
    68 by (rtac ForallQFilterPnil 1);
    69 by (REPEAT (atac 1));
    69 by (REPEAT (atac 1));
    70 qed"Cut_nil";
    70 qed"Cut_nil";
    71 
    71 
    72 goalw thy [Cut_def]
    72 goalw thy [Cut_def]
    73 "!! s. [| Forall (%a.~ P a) s; ~Finite s|] \
    73 "!! s. [| Forall (%a.~ P a) s; ~Finite s|] \
    74 \           ==> Cut P s =UU";
    74 \           ==> Cut P s =UU";
    75 by (subgoal_tac "Filter P`s= UU" 1);
    75 by (subgoal_tac "Filter P`s= UU" 1);
    76 by (asm_simp_tac (!simpset addsimps [oraclebuild_UU]) 1);
    76 by (asm_simp_tac (!simpset addsimps [oraclebuild_UU]) 1);
    77 br ForallQFilterPUU 1;
    77 by (rtac ForallQFilterPUU 1);
    78 by (REPEAT (atac 1));
    78 by (REPEAT (atac 1));
    79 qed"Cut_UU";
    79 qed"Cut_UU";
    80 
    80 
    81 goalw thy [Cut_def]
    81 goalw thy [Cut_def]
    82 "!! s. [| P t;  Forall (%x.~ P x) ss; Finite ss|] \
    82 "!! s. [| P t;  Forall (%x.~ P x) ss; Finite ss|] \
   104              ForallQFilterPnil]) 1);
   104              ForallQFilterPnil]) 1);
   105 by (asm_full_simp_tac (!simpset addsimps [Cut_UU,
   105 by (asm_full_simp_tac (!simpset addsimps [Cut_UU,
   106              ForallQFilterPUU]) 1);
   106              ForallQFilterPUU]) 1);
   107 (* main case *)
   107 (* main case *)
   108 by (asm_full_simp_tac (!simpset addsimps [Cut_Cons,ForallQFilterPnil]) 1);
   108 by (asm_full_simp_tac (!simpset addsimps [Cut_Cons,ForallQFilterPnil]) 1);
   109 auto();
   109 by (Auto_tac());
   110 qed"FilterCut";
   110 qed"FilterCut";
   111 
   111 
   112 
   112 
   113 goal thy "Cut P (Cut P s) = (Cut P s)";
   113 goal thy "Cut P (Cut P s) = (Cut P s)";
   114 
   114 
   121              ForallQFilterPnil]) 1);
   121              ForallQFilterPnil]) 1);
   122 by (asm_full_simp_tac (!simpset addsimps [Cut_UU,
   122 by (asm_full_simp_tac (!simpset addsimps [Cut_UU,
   123              ForallQFilterPUU]) 1);
   123              ForallQFilterPUU]) 1);
   124 (* main case *)
   124 (* main case *)
   125 by (asm_full_simp_tac (!simpset addsimps [Cut_Cons,ForallQFilterPnil]) 1);
   125 by (asm_full_simp_tac (!simpset addsimps [Cut_Cons,ForallQFilterPnil]) 1);
   126 br take_reduction 1;
   126 by (rtac take_reduction 1);
   127 auto();
   127 by (Auto_tac());
   128 qed"Cut_idemp";
   128 qed"Cut_idemp";
   129 
   129 
   130 
   130 
   131 goal thy "Map f`(Cut (P o f) s) = Cut P (Map f`s)";
   131 goal thy "Map f`(Cut (P o f) s) = Cut P (Map f`s)";
   132 
   132 
   134                  ,("Q1","%x.~ P (f x)"), ("x1","s")]
   134                  ,("Q1","%x.~ P (f x)"), ("x1","s")]
   135                  (take_lemma_less_induct RS mp) 1);
   135                  (take_lemma_less_induct RS mp) 1);
   136 by (Fast_tac 3);
   136 by (Fast_tac 3);
   137 by (case_tac "Finite s" 1);
   137 by (case_tac "Finite s" 1);
   138 by (asm_full_simp_tac (!simpset addsimps [Cut_nil]) 1); 
   138 by (asm_full_simp_tac (!simpset addsimps [Cut_nil]) 1); 
   139 br (Cut_nil RS sym) 1;
   139 by (rtac (Cut_nil RS sym) 1);
   140 by (asm_full_simp_tac (!simpset addsimps [ForallMap,o_def]) 1); 
   140 by (asm_full_simp_tac (!simpset addsimps [ForallMap,o_def]) 1); 
   141 by (asm_full_simp_tac (!simpset addsimps [Map2Finite]) 1);
   141 by (asm_full_simp_tac (!simpset addsimps [Map2Finite]) 1);
   142 (* csae ~ Finite s *)
   142 (* csae ~ Finite s *)
   143 by (asm_full_simp_tac (!simpset addsimps [Cut_UU]) 1);
   143 by (asm_full_simp_tac (!simpset addsimps [Cut_UU]) 1);
   144 br (Cut_UU RS sym) 1;
   144 by (rtac (Cut_UU RS sym) 1);
   145 by (asm_full_simp_tac (!simpset addsimps [ForallMap,o_def]) 1); 
   145 by (asm_full_simp_tac (!simpset addsimps [ForallMap,o_def]) 1); 
   146 by (asm_full_simp_tac (!simpset addsimps [Map2Finite]) 1);
   146 by (asm_full_simp_tac (!simpset addsimps [Map2Finite]) 1);
   147 (* main case *)
   147 (* main case *)
   148 by (asm_full_simp_tac (!simpset addsimps [Cut_Cons,MapConc,
   148 by (asm_full_simp_tac (!simpset addsimps [Cut_Cons,MapConc,
   149           ForallMap,FiniteMap1,o_def]) 1);
   149           ForallMap,FiniteMap1,o_def]) 1);
   150 br take_reduction 1;
   150 by (rtac take_reduction 1);
   151 auto();
   151 by (Auto_tac());
   152 qed"MapCut";
   152 qed"MapCut";
   153 
   153 
   154 
   154 
   155 goal thy "~Finite s --> Cut P s << s";
   155 goal thy "~Finite s --> Cut P s << s";
   156 by (strip_tac 1);
   156 by (strip_tac 1);
   157 br (take_lemma_less RS iffD1) 1;
   157 by (rtac (take_lemma_less RS iffD1) 1);
   158 by (strip_tac 1);
   158 by (strip_tac 1);
   159 br mp 1;
   159 by (rtac mp 1);
   160 ba 2;
   160 by (assume_tac 2);
   161 by (thin_tac' 1 1);
   161 by (thin_tac' 1 1);
   162 by (res_inst_tac [("x","s")] spec 1);
   162 by (res_inst_tac [("x","s")] spec 1);
   163 br less_induct 1;
   163 by (rtac less_induct 1);
   164 by (strip_tac 1);
   164 by (strip_tac 1);
   165 ren "na n s" 1;
   165 ren "na n s" 1;
   166 by (case_tac "Forall (%x. ~ P x) s" 1);
   166 by (case_tac "Forall (%x. ~ P x) s" 1);
   167 br (take_lemma_less RS iffD2 RS spec) 1;
   167 by (rtac (take_lemma_less RS iffD2 RS spec) 1);
   168 by (asm_full_simp_tac (!simpset addsimps [Cut_UU]) 1);
   168 by (asm_full_simp_tac (!simpset addsimps [Cut_UU]) 1);
   169 (* main case *)
   169 (* main case *)
   170 bd divide_Seq3 1;
   170 by (dtac divide_Seq3 1);
   171 by (REPEAT (etac exE 1));
   171 by (REPEAT (etac exE 1));
   172 by (REPEAT (etac conjE 1));
   172 by (REPEAT (etac conjE 1));
   173 by (hyp_subst_tac 1);
   173 by (hyp_subst_tac 1);
   174 by (asm_full_simp_tac (!simpset addsimps [Cut_Cons]) 1);
   174 by (asm_full_simp_tac (!simpset addsimps [Cut_Cons]) 1);
   175 br take_reduction_less 1;
   175 by (rtac take_reduction_less 1);
   176 (* auto makes also reasoning about Finiteness of parts of s ! *)
   176 (* auto makes also reasoning about Finiteness of parts of s ! *)
   177 auto();
   177 by (Auto_tac());
   178 qed_spec_mp"Cut_prefixcl_nFinite";
   178 qed_spec_mp"Cut_prefixcl_nFinite";
   179 
   179 
   180 
   180 
   181 
   181 
   182 (*
   182 (*
   183 
   183 
   184 goal thy "Finite s --> (? y. s = Cut P s @@ y)";
   184 goal thy "Finite s --> (? y. s = Cut P s @@ y)";
   185 by (strip_tac 1);
   185 by (strip_tac 1);
   186 by (rtac exI 1);
   186 by (rtac exI 1);
   187 br seq.take_lemma 1;
   187 by (rtac seq.take_lemma 1);
   188 br mp 1;
   188 by (rtac mp 1);
   189 ba 2;
   189 by (assume_tac 2);
   190 by (thin_tac' 1 1);
   190 by (thin_tac' 1 1);
   191 by (res_inst_tac [("x","s")] spec 1);
   191 by (res_inst_tac [("x","s")] spec 1);
   192 br less_induct 1;
   192 by (rtac less_induct 1);
   193 by (strip_tac 1);
   193 by (strip_tac 1);
   194 ren "na n s" 1;
   194 ren "na n s" 1;
   195 by (case_tac "Forall (%x. ~ P x) s" 1);
   195 by (case_tac "Forall (%x. ~ P x) s" 1);
   196 br (seq_take_lemma RS iffD2 RS spec) 1;
   196 by (rtac (seq_take_lemma RS iffD2 RS spec) 1);
   197 by (asm_full_simp_tac (!simpset addsimps [Cut_nil]) 1);
   197 by (asm_full_simp_tac (!simpset addsimps [Cut_nil]) 1);
   198 (* main case *)
   198 (* main case *)
   199 bd divide_Seq3 1;
   199 by (dtac divide_Seq3 1);
   200 by (REPEAT (etac exE 1));
   200 by (REPEAT (etac exE 1));
   201 by (REPEAT (etac conjE 1));
   201 by (REPEAT (etac conjE 1));
   202 by (hyp_subst_tac 1);
   202 by (hyp_subst_tac 1);
   203 by (asm_full_simp_tac (!simpset addsimps [Cut_Cons,Conc_assoc]) 1);
   203 by (asm_full_simp_tac (!simpset addsimps [Cut_Cons,Conc_assoc]) 1);
   204 br take_reduction 1;
   204 by (rtac take_reduction 1);
   205 
   205 
   206 qed_spec_mp"Cut_prefixcl_Finite";
   206 qed_spec_mp"Cut_prefixcl_Finite";
   207 
   207 
   208 *)
   208 *)
   209 
   209 
   210 
   210 
   211 
   211 
   212 goal thy "!!ex .is_exec_frag A (s,ex) ==> is_exec_frag A (s,Cut P ex)";
   212 goal thy "!!ex .is_exec_frag A (s,ex) ==> is_exec_frag A (s,Cut P ex)";
   213 by (case_tac "Finite ex" 1);
   213 by (case_tac "Finite ex" 1);
   214 by (cut_inst_tac [("s","ex"),("P","P")] Cut_prefixcl_Finite 1);
   214 by (cut_inst_tac [("s","ex"),("P","P")] Cut_prefixcl_Finite 1);
   215 ba 1;
   215 by (assume_tac 1);
   216 be exE 1;
   216 by (etac exE 1);
   217 br exec_prefix2closed 1;
   217 by (rtac exec_prefix2closed 1);
   218 by (eres_inst_tac [("s","ex"),("t","Cut P ex @@ y")] subst 1);
   218 by (eres_inst_tac [("s","ex"),("t","Cut P ex @@ y")] subst 1);
   219 ba 1;
   219 by (assume_tac 1);
   220 be exec_prefixclosed 1;
   220 by (etac exec_prefixclosed 1);
   221 be Cut_prefixcl_nFinite 1;
   221 by (etac Cut_prefixcl_nFinite 1);
   222 qed"execThruCut";
   222 qed"execThruCut";
   223 
   223 
   224 
   224 
   225 
   225 
   226 (* ---------------------------------------------------------------- *)
   226 (* ---------------------------------------------------------------- *)
   249 
   249 
   250 (* Subgoal 2:  Lemma:  Filter P s = Filter P (Cut P s) *)
   250 (* Subgoal 2:  Lemma:  Filter P s = Filter P (Cut P s) *)
   251 
   251 
   252 by (simp_tac (!simpset addsimps [filter_act_def]) 1);
   252 by (simp_tac (!simpset addsimps [filter_act_def]) 1);
   253 by (subgoal_tac "Map fst`(Cut (%a.fst a: ext A) y)= Cut (%a.a:ext A) (Map fst`y)" 1);
   253 by (subgoal_tac "Map fst`(Cut (%a.fst a: ext A) y)= Cut (%a.a:ext A) (Map fst`y)" 1);
   254 br (rewrite_rule [o_def] MapCut) 2;
   254 by (rtac (rewrite_rule [o_def] MapCut) 2);
   255 by (asm_full_simp_tac (!simpset addsimps [FilterCut RS sym]) 1);
   255 by (asm_full_simp_tac (!simpset addsimps [FilterCut RS sym]) 1);
   256 
   256 
   257 (* Subgoal 3: Lemma: Cut idempotent  *)
   257 (* Subgoal 3: Lemma: Cut idempotent  *)
   258 
   258 
   259 by (simp_tac (!simpset addsimps [LastActExtsch_def,filter_act_def]) 1);
   259 by (simp_tac (!simpset addsimps [LastActExtsch_def,filter_act_def]) 1);
   260 by (subgoal_tac "Map fst`(Cut (%a.fst a: ext A) y)= Cut (%a.a:ext A) (Map fst`y)" 1);
   260 by (subgoal_tac "Map fst`(Cut (%a.fst a: ext A) y)= Cut (%a.a:ext A) (Map fst`y)" 1);
   261 br (rewrite_rule [o_def] MapCut) 2;
   261 by (rtac (rewrite_rule [o_def] MapCut) 2);
   262 by (asm_full_simp_tac (!simpset addsimps [Cut_idemp]) 1);
   262 by (asm_full_simp_tac (!simpset addsimps [Cut_idemp]) 1);
   263 qed"exists_LastActExtsch";
   263 qed"exists_LastActExtsch";
   264 
   264 
   265 
   265 
   266 (* ---------------------------------------------------------------- *)
   266 (* ---------------------------------------------------------------- *)
   268 (* ---------------------------------------------------------------- *)
   268 (* ---------------------------------------------------------------- *)
   269 
   269 
   270 goalw  thy [LastActExtsch_def]
   270 goalw  thy [LastActExtsch_def]
   271   "!! A. [| LastActExtsch A sch; Filter (%x.x:ext A)`sch = nil |] \
   271   "!! A. [| LastActExtsch A sch; Filter (%x.x:ext A)`sch = nil |] \
   272 \   ==> sch=nil";
   272 \   ==> sch=nil";
   273 bd FilternPnilForallP 1;
   273 by (dtac FilternPnilForallP 1);
   274 be conjE 1;
   274 by (etac conjE 1);
   275 bd Cut_nil 1;
   275 by (dtac Cut_nil 1);
   276 ba 1;
   276 by (assume_tac 1);
   277 by (Asm_full_simp_tac 1);
   277 by (Asm_full_simp_tac 1);
   278 qed"LastActExtimplnil";
   278 qed"LastActExtimplnil";
   279 
   279 
   280 goalw  thy [LastActExtsch_def]
   280 goalw  thy [LastActExtsch_def]
   281   "!! A. [| LastActExtsch A sch; Filter (%x.x:ext A)`sch = UU |] \
   281   "!! A. [| LastActExtsch A sch; Filter (%x.x:ext A)`sch = UU |] \
   282 \   ==> sch=UU";
   282 \   ==> sch=UU";
   283 bd FilternPUUForallP 1;
   283 by (dtac FilternPUUForallP 1);
   284 be conjE 1;
   284 by (etac conjE 1);
   285 bd Cut_UU 1;
   285 by (dtac Cut_UU 1);
   286 ba 1;
   286 by (assume_tac 1);
   287 by (Asm_full_simp_tac 1);
   287 by (Asm_full_simp_tac 1);
   288 qed"LastActExtimplUU";
   288 qed"LastActExtimplUU";