src/HOL/IMP/Abs_Int3.thy
changeset 80914 d97fdabd9e2b
parent 73932 fd21b4a93043
equal deleted inserted replaced
80913:46f59511b7bb 80914:d97fdabd9e2b
     5 theory Abs_Int3
     5 theory Abs_Int3
     6 imports Abs_Int2_ivl
     6 imports Abs_Int2_ivl
     7 begin
     7 begin
     8 
     8 
     9 class widen =
     9 class widen =
    10 fixes widen :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infix "\<nabla>" 65)
    10 fixes widen :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infix \<open>\<nabla>\<close> 65)
    11 
    11 
    12 class narrow =
    12 class narrow =
    13 fixes narrow :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infix "\<triangle>" 65)
    13 fixes narrow :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infix \<open>\<triangle>\<close> 65)
    14 
    14 
    15 class wn = widen + narrow + order +
    15 class wn = widen + narrow + order +
    16 assumes widen1: "x \<le> x \<nabla> y"
    16 assumes widen1: "x \<le> x \<nabla> y"
    17 assumes widen2: "y \<le> x \<nabla> y"
    17 assumes widen2: "y \<le> x \<nabla> y"
    18 assumes narrow1: "y \<le> x \<Longrightarrow> y \<le> x \<triangle> y"
    18 assumes narrow1: "y \<le> x \<Longrightarrow> y \<le> x \<triangle> y"
   396 apply(rule_tac x=p in bexI)
   396 apply(rule_tac x=p in bexI)
   397  apply (auto simp: vars_acom_def m_o_widen top_on_acom_def)
   397  apply (auto simp: vars_acom_def m_o_widen top_on_acom_def)
   398 done
   398 done
   399 
   399 
   400 
   400 
   401 definition n_s :: "'av st \<Rightarrow> vname set \<Rightarrow> nat" ("n\<^sub>s") where
   401 definition n_s :: "'av st \<Rightarrow> vname set \<Rightarrow> nat" (\<open>n\<^sub>s\<close>) where
   402 "n\<^sub>s S X = (\<Sum>x\<in>X. n(fun S x))"
   402 "n\<^sub>s S X = (\<Sum>x\<in>X. n(fun S x))"
   403 
   403 
   404 lemma n_s_narrow_rep:
   404 lemma n_s_narrow_rep:
   405 assumes "finite X"  "S1 = S2 on -X"  "\<forall>x. S2 x \<le> S1 x"  "\<forall>x. S1 x \<triangle> S2 x \<le> S1 x"
   405 assumes "finite X"  "S1 = S2 on -X"  "\<forall>x. S2 x \<le> S1 x"  "\<forall>x. S1 x \<triangle> S2 x \<le> S1 x"
   406   "S1 x \<noteq> S1 x \<triangle> S2 x"
   406   "S1 x \<noteq> S1 x \<triangle> S2 x"
   420 apply(auto simp add: less_st_def n_s_def)
   420 apply(auto simp add: less_st_def n_s_def)
   421 apply (transfer fixing: n)
   421 apply (transfer fixing: n)
   422 apply(auto simp add: less_eq_st_rep_iff eq_st_def fun_eq_iff n_s_narrow_rep)
   422 apply(auto simp add: less_eq_st_rep_iff eq_st_def fun_eq_iff n_s_narrow_rep)
   423 done
   423 done
   424 
   424 
   425 definition n_o :: "'av st option \<Rightarrow> vname set \<Rightarrow> nat" ("n\<^sub>o") where
   425 definition n_o :: "'av st option \<Rightarrow> vname set \<Rightarrow> nat" (\<open>n\<^sub>o\<close>) where
   426 "n\<^sub>o opt X = (case opt of None \<Rightarrow> 0 | Some S \<Rightarrow> n\<^sub>s S X + 1)"
   426 "n\<^sub>o opt X = (case opt of None \<Rightarrow> 0 | Some S \<Rightarrow> n\<^sub>s S X + 1)"
   427 
   427 
   428 lemma n_o_narrow:
   428 lemma n_o_narrow:
   429   "top_on_opt S1 (-X) \<Longrightarrow> top_on_opt S2 (-X) \<Longrightarrow> finite X
   429   "top_on_opt S1 (-X) \<Longrightarrow> top_on_opt S2 (-X) \<Longrightarrow> finite X
   430   \<Longrightarrow> S2 \<le> S1 \<Longrightarrow> S1 \<triangle> S2 < S1 \<Longrightarrow> n\<^sub>o (S1 \<triangle> S2) X < n\<^sub>o S1 X"
   430   \<Longrightarrow> S2 \<le> S1 \<Longrightarrow> S1 \<triangle> S2 < S1 \<Longrightarrow> n\<^sub>o (S1 \<triangle> S2) X < n\<^sub>o S1 X"
   431 apply(induction S1 S2 rule: narrow_option.induct)
   431 apply(induction S1 S2 rule: narrow_option.induct)
   432 apply(auto simp: n_o_def n_s_narrow)
   432 apply(auto simp: n_o_def n_s_narrow)
   433 done
   433 done
   434 
   434 
   435 
   435 
   436 definition n_c :: "'av st option acom \<Rightarrow> nat" ("n\<^sub>c") where
   436 definition n_c :: "'av st option acom \<Rightarrow> nat" (\<open>n\<^sub>c\<close>) where
   437 "n\<^sub>c C = sum_list (map (\<lambda>a. n\<^sub>o a (vars C)) (annos C))"
   437 "n\<^sub>c C = sum_list (map (\<lambda>a. n\<^sub>o a (vars C)) (annos C))"
   438 
   438 
   439 lemma less_annos_iff: "(C1 < C2) = (C1 \<le> C2 \<and>
   439 lemma less_annos_iff: "(C1 < C2) = (C1 \<le> C2 \<and>
   440   (\<exists>i<length (annos C1). annos C1 ! i < annos C2 ! i))"
   440   (\<exists>i<length (annos C1). annos C1 ! i < annos C2 ! i))"
   441 by(metis (opaque_lifting, no_types) less_le_not_le le_iff_le_annos size_annos_same2)
   441 by(metis (opaque_lifting, no_types) less_le_not_le le_iff_le_annos size_annos_same2)