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) |