src/HOL/HOLCF/IOA/Abstraction.thy
changeset 62195 799a5306e2ed
parent 62193 0826f6b6ba09
child 62441 e5e38e1f2dd4
equal deleted inserted replaced
62194:0aabc5931361 62195:799a5306e2ed
    86 
    86 
    87 lemma exec_frag_abstraction [rule_format]:
    87 lemma exec_frag_abstraction [rule_format]:
    88   "is_abstraction h C A \<Longrightarrow>
    88   "is_abstraction h C A \<Longrightarrow>
    89     \<forall>s. reachable C s \<and> is_exec_frag C (s, xs) \<longrightarrow> is_exec_frag A (cex_abs h (s, xs))"
    89     \<forall>s. reachable C s \<and> is_exec_frag C (s, xs) \<longrightarrow> is_exec_frag A (cex_abs h (s, xs))"
    90   apply (simp add: cex_abs_def)
    90   apply (simp add: cex_abs_def)
    91   apply (tactic \<open>pair_induct_tac @{context} "xs" [@{thm is_exec_frag_def}] 1\<close>)
    91   apply (pair_induct xs simp: is_exec_frag_def)
    92   txt \<open>main case\<close>
    92   txt \<open>main case\<close>
    93   apply (auto dest: reachable.reachable_n simp add: is_abstraction_def)
    93   apply (auto dest: reachable.reachable_n simp add: is_abstraction_def)
    94   done
    94   done
    95 
    95 
    96 lemma abs_is_weakening: "is_abstraction h C A \<Longrightarrow> weakeningIOA A C h"
    96 lemma abs_is_weakening: "is_abstraction h C A \<Longrightarrow> weakeningIOA A C h"
   162 \<close>
   162 \<close>
   163 lemma traces_coincide_abs:
   163 lemma traces_coincide_abs:
   164   "ext C = ext A \<Longrightarrow> mk_trace C $ xs = mk_trace A $ (snd (cex_abs f (s, xs)))"
   164   "ext C = ext A \<Longrightarrow> mk_trace C $ xs = mk_trace A $ (snd (cex_abs f (s, xs)))"
   165   apply (unfold cex_abs_def mk_trace_def filter_act_def)
   165   apply (unfold cex_abs_def mk_trace_def filter_act_def)
   166   apply simp
   166   apply simp
   167   apply (tactic \<open>pair_induct_tac @{context} "xs" [] 1\<close>)
   167   apply (pair_induct xs)
   168   done
   168   done
   169 
   169 
   170 
   170 
   171 text \<open>
   171 text \<open>
   172   Does not work with \<open>abstraction_is_ref_map\<close> as proof of \<open>abs_safety\<close>, because
   172   Does not work with \<open>abstraction_is_ref_map\<close> as proof of \<open>abs_safety\<close>, because
   180   apply (simp add: is_live_abstraction_def live_implements_def livetraces_def liveexecutions_def)
   180   apply (simp add: is_live_abstraction_def live_implements_def livetraces_def liveexecutions_def)
   181   apply auto
   181   apply auto
   182   apply (rule_tac x = "cex_abs h ex" in exI)
   182   apply (rule_tac x = "cex_abs h ex" in exI)
   183   apply auto
   183   apply auto
   184   text \<open>Traces coincide\<close>
   184   text \<open>Traces coincide\<close>
   185   apply (tactic \<open>pair_tac @{context} "ex" 1\<close>)
   185   apply (pair ex)
   186   apply (rule traces_coincide_abs)
   186   apply (rule traces_coincide_abs)
   187   apply (simp (no_asm) add: externals_def)
   187   apply (simp (no_asm) add: externals_def)
   188   apply (auto)[1]
   188   apply (auto)[1]
   189 
   189 
   190   text \<open>\<open>cex_abs\<close> is execution\<close>
   190   text \<open>\<open>cex_abs\<close> is execution\<close>
   191   apply (tactic \<open>pair_tac @{context} "ex" 1\<close>)
   191   apply (pair ex)
   192   apply (simp add: executions_def)
   192   apply (simp add: executions_def)
   193   text \<open>start state\<close>
   193   text \<open>start state\<close>
   194   apply (rule conjI)
   194   apply (rule conjI)
   195   apply (simp add: is_abstraction_def cex_abs_def)
   195   apply (simp add: is_abstraction_def cex_abs_def)
   196   text \<open>\<open>is_execution_fragment\<close>\<close>
   196   text \<open>\<open>is_execution_fragment\<close>\<close>
   197   apply (erule exec_frag_abstraction)
   197   apply (erule exec_frag_abstraction)
   198   apply (simp add: reachable.reachable_0)
   198   apply (simp add: reachable.reachable_0)
   199 
   199 
   200   text \<open>Liveness\<close>
   200   text \<open>Liveness\<close>
   201   apply (simp add: temp_weakening_def2)
   201   apply (simp add: temp_weakening_def2)
   202    apply (tactic \<open>pair_tac @{context} "ex" 1\<close>)
   202    apply (pair ex)
   203   done
   203   done
   204 
   204 
   205 
   205 
   206 subsection \<open>Abstraction Rules for Automata\<close>
   206 subsection \<open>Abstraction Rules for Automata\<close>
   207 
   207 
   277 
   277 
   278 subsubsection \<open>Box\<close>
   278 subsubsection \<open>Box\<close>
   279 
   279 
   280 (* FIXME: should be same as nil_is_Conc2 when all nils are turned to right side! *)
   280 (* FIXME: should be same as nil_is_Conc2 when all nils are turned to right side! *)
   281 lemma UU_is_Conc: "(UU = x @@ y) = (((x::'a Seq)= UU) | (x = nil \<and> y = UU))"
   281 lemma UU_is_Conc: "(UU = x @@ y) = (((x::'a Seq)= UU) | (x = nil \<and> y = UU))"
   282   by (tactic \<open>Seq_case_simp_tac @{context} "x" 1\<close>)
   282   by (Seq_case_simp x)
   283 
   283 
   284 lemma ex2seqConc [rule_format]:
   284 lemma ex2seqConc [rule_format]:
   285   "Finite s1 \<longrightarrow> (\<forall>ex. (s \<noteq> nil \<and> s \<noteq> UU \<and> ex2seq ex = s1 @@ s) \<longrightarrow> (\<exists>ex'. s = ex2seq ex'))"
   285   "Finite s1 \<longrightarrow> (\<forall>ex. (s \<noteq> nil \<and> s \<noteq> UU \<and> ex2seq ex = s1 @@ s) \<longrightarrow> (\<exists>ex'. s = ex2seq ex'))"
   286   apply (rule impI)
   286   apply (rule impI)
   287   apply (tactic \<open>Seq_Finite_induct_tac @{context} 1\<close>)
   287   apply Seq_Finite_induct
   288   apply blast
   288   apply blast
   289   text \<open>main case\<close>
   289   text \<open>main case\<close>
   290   apply clarify
   290   apply clarify
   291   apply (tactic \<open>pair_tac @{context} "ex" 1\<close>)
   291   apply (pair ex)
   292   apply (tactic \<open>Seq_case_simp_tac @{context} "x2" 1\<close>)
   292   apply (Seq_case_simp x2)
   293   text \<open>\<open>UU\<close> case\<close>
   293   text \<open>\<open>UU\<close> case\<close>
   294   apply (simp add: nil_is_Conc)
   294   apply (simp add: nil_is_Conc)
   295   text \<open>\<open>nil\<close> case\<close>
   295   text \<open>\<open>nil\<close> case\<close>
   296   apply (simp add: nil_is_Conc)
   296   apply (simp add: nil_is_Conc)
   297   text \<open>cons case\<close>
   297   text \<open>cons case\<close>
   298   apply (tactic \<open>pair_tac @{context} "aa" 1\<close>)
   298   apply (pair aa)
   299   apply auto
   299   apply auto
   300   done
   300   done
   301 
   301 
   302 (* important property of ex2seq: can be shiftet, as defined "pointwise" *)
   302 (* important property of ex2seq: can be shiftet, as defined "pointwise" *)
   303 lemma ex2seq_tsuffix: "tsuffix s (ex2seq ex) \<Longrightarrow> \<exists>ex'. s = (ex2seq ex')"
   303 lemma ex2seq_tsuffix: "tsuffix s (ex2seq ex) \<Longrightarrow> \<exists>ex'. s = (ex2seq ex')"
   335 lemma strength_Init:
   335 lemma strength_Init:
   336   "state_strengthening P Q h \<Longrightarrow> temp_strengthening (Init P) (Init Q) h"
   336   "state_strengthening P Q h \<Longrightarrow> temp_strengthening (Init P) (Init Q) h"
   337   apply (unfold temp_strengthening_def state_strengthening_def
   337   apply (unfold temp_strengthening_def state_strengthening_def
   338     temp_sat_def satisfies_def Init_def unlift_def)
   338     temp_sat_def satisfies_def Init_def unlift_def)
   339   apply auto
   339   apply auto
   340   apply (tactic \<open>pair_tac @{context} "ex" 1\<close>)
   340   apply (pair ex)
   341   apply (tactic \<open>Seq_case_simp_tac @{context} "x2" 1\<close>)
   341   apply (Seq_case_simp x2)
   342   apply (tactic \<open>pair_tac @{context} "a" 1\<close>)
   342   apply (pair a)
   343   done
   343   done
   344 
   344 
   345 
   345 
   346 subsubsection \<open>Next\<close>
   346 subsubsection \<open>Next\<close>
   347 
   347 
   348 lemma TL_ex2seq_UU: "TL $ (ex2seq (cex_abs h ex)) = UU \<longleftrightarrow> TL $ (ex2seq ex) = UU"
   348 lemma TL_ex2seq_UU: "TL $ (ex2seq (cex_abs h ex)) = UU \<longleftrightarrow> TL $ (ex2seq ex) = UU"
   349   apply (tactic \<open>pair_tac @{context} "ex" 1\<close>)
   349   apply (pair ex)
   350   apply (tactic \<open>Seq_case_simp_tac @{context} "x2" 1\<close>)
   350   apply (Seq_case_simp x2)
   351   apply (tactic \<open>pair_tac @{context} "a" 1\<close>)
   351   apply (pair a)
   352   apply (tactic \<open>Seq_case_simp_tac @{context} "s" 1\<close>)
   352   apply (Seq_case_simp s)
   353   apply (tactic \<open>pair_tac @{context} "a" 1\<close>)
   353   apply (pair a)
   354   done
   354   done
   355 
   355 
   356 lemma TL_ex2seq_nil: "TL $ (ex2seq (cex_abs h ex)) = nil \<longleftrightarrow> TL $ (ex2seq ex) = nil"
   356 lemma TL_ex2seq_nil: "TL $ (ex2seq (cex_abs h ex)) = nil \<longleftrightarrow> TL $ (ex2seq ex) = nil"
   357   apply (tactic \<open>pair_tac @{context} "ex" 1\<close>)
   357   apply (pair ex)
   358   apply (tactic \<open>Seq_case_simp_tac @{context} "x2" 1\<close>)
   358   apply (Seq_case_simp x2)
   359   apply (tactic \<open>pair_tac @{context} "a" 1\<close>)
   359   apply (pair a)
   360   apply (tactic \<open>Seq_case_simp_tac @{context} "s" 1\<close>)
   360   apply (Seq_case_simp s)
   361   apply (tactic \<open>pair_tac @{context} "a" 1\<close>)
   361   apply (pair a)
   362   done
   362   done
   363 
   363 
   364 (*important property of cex_absSeq: As it is a 1to1 correspondence,
   364 (*important property of cex_absSeq: As it is a 1to1 correspondence,
   365   properties carry over*)
   365   properties carry over*)
   366 lemma cex_absSeq_TL: "cex_absSeq h (TL $ s) = TL $ (cex_absSeq h s)"
   366 lemma cex_absSeq_TL: "cex_absSeq h (TL $ s) = TL $ (cex_absSeq h s)"
   367   by (simp add: MapTL cex_absSeq_def)
   367   by (simp add: MapTL cex_absSeq_def)
   368 
   368 
   369 (* important property of ex2seq: can be shiftet, as defined "pointwise" *)
   369 (* important property of ex2seq: can be shiftet, as defined "pointwise" *)
   370 lemma TLex2seq: "snd ex \<noteq> UU \<Longrightarrow> snd ex \<noteq> nil \<Longrightarrow> \<exists>ex'. TL$(ex2seq ex) = ex2seq ex'"
   370 lemma TLex2seq: "snd ex \<noteq> UU \<Longrightarrow> snd ex \<noteq> nil \<Longrightarrow> \<exists>ex'. TL$(ex2seq ex) = ex2seq ex'"
   371   apply (tactic \<open>pair_tac @{context} "ex" 1\<close>)
   371   apply (pair ex)
   372   apply (tactic \<open>Seq_case_simp_tac @{context} "x2" 1\<close>)
   372   apply (Seq_case_simp x2)
   373   apply (tactic \<open>pair_tac @{context} "a" 1\<close>)
   373   apply (pair a)
   374   apply auto
   374   apply auto
   375   done
   375   done
   376 
   376 
   377 lemma ex2seqnilTL: "TL $ (ex2seq ex) \<noteq> nil \<longleftrightarrow> snd ex \<noteq> nil \<and> snd ex \<noteq> UU"
   377 lemma ex2seqnilTL: "TL $ (ex2seq ex) \<noteq> nil \<longleftrightarrow> snd ex \<noteq> nil \<and> snd ex \<noteq> UU"
   378   apply (tactic \<open>pair_tac @{context} "ex" 1\<close>)
   378   apply (pair ex)
   379   apply (tactic \<open>Seq_case_simp_tac @{context} "x2" 1\<close>)
   379   apply (Seq_case_simp x2)
   380   apply (tactic \<open>pair_tac @{context} "a" 1\<close>)
   380   apply (pair a)
   381   apply (tactic \<open>Seq_case_simp_tac @{context} "s" 1\<close>)
   381   apply (Seq_case_simp s)
   382   apply (tactic \<open>pair_tac @{context} "a" 1\<close>)
   382   apply (pair a)
   383   done
   383   done
   384 
   384 
   385 lemma strength_Next: "temp_strengthening P Q h \<Longrightarrow> temp_strengthening (Next P) (Next Q) h"
   385 lemma strength_Next: "temp_strengthening P Q h \<Longrightarrow> temp_strengthening (Next P) (Next Q) h"
   386   apply (unfold temp_strengthening_def state_strengthening_def temp_sat_def satisfies_def Next_def)
   386   apply (unfold temp_strengthening_def state_strengthening_def temp_sat_def satisfies_def Next_def)
   387   apply simp
   387   apply simp
   403 
   403 
   404 lemma weak_Init: "state_weakening P Q h \<Longrightarrow> temp_weakening (Init P) (Init Q) h"
   404 lemma weak_Init: "state_weakening P Q h \<Longrightarrow> temp_weakening (Init P) (Init Q) h"
   405   apply (simp add: temp_weakening_def2 state_weakening_def2
   405   apply (simp add: temp_weakening_def2 state_weakening_def2
   406     temp_sat_def satisfies_def Init_def unlift_def)
   406     temp_sat_def satisfies_def Init_def unlift_def)
   407   apply auto
   407   apply auto
   408   apply (tactic \<open>pair_tac @{context} "ex" 1\<close>)
   408   apply (pair ex)
   409   apply (tactic \<open>Seq_case_simp_tac @{context} "x2" 1\<close>)
   409   apply (Seq_case_simp x2)
   410   apply (tactic \<open>pair_tac @{context} "a" 1\<close>)
   410   apply (pair a)
   411   done
   411   done
   412 
   412 
   413 
   413 
   414 text \<open>Localizing Temproal Strengthenings - 3\<close>
   414 text \<open>Localizing Temproal Strengthenings - 3\<close>
   415 
   415