422 value "show_acom_opt (AI_ivl' test6_ivl)" |
422 value "show_acom_opt (AI_ivl' test6_ivl)" |
423 |
423 |
424 |
424 |
425 subsubsection "Generic Termination Proof" |
425 subsubsection "Generic Termination Proof" |
426 |
426 |
|
427 text{* The assumptions for widening and narrowing differ because during |
|
428 narrowing we have the invariant @{prop"y \<le> x"} (where @{text y} is the next |
|
429 iterate), but during widening there is no such invariant, there we only have |
|
430 that not yet @{prop"y \<le> x"}. This complicates the termination proof for |
|
431 widening. *} |
|
432 |
427 locale Measure_WN = Measure1 where m=m for m :: "'av::WN \<Rightarrow> nat" + |
433 locale Measure_WN = Measure1 where m=m for m :: "'av::WN \<Rightarrow> nat" + |
428 fixes n :: "'av \<Rightarrow> nat" |
434 fixes n :: "'av \<Rightarrow> nat" |
429 assumes m_anti_mono: "x \<le> y \<Longrightarrow> m x \<ge> m y" |
435 assumes m_anti_mono: "x \<le> y \<Longrightarrow> m x \<ge> m y" |
430 assumes m_widen: "~ y \<le> x \<Longrightarrow> m(x \<nabla> y) < m x" |
436 assumes m_widen: "~ y \<le> x \<Longrightarrow> m(x \<nabla> y) < m x" |
431 assumes n_mono: "x \<le> y \<Longrightarrow> n x \<le> n y" |
437 assumes n_narrow: "y \<le> x \<Longrightarrow> x \<triangle> y < x \<Longrightarrow> n(x \<triangle> y) < n x" |
432 assumes n_narrow: "y \<le> x \<Longrightarrow> ~ x \<le> x \<triangle> y \<Longrightarrow> n(x \<triangle> y) < n x" |
|
433 |
438 |
434 begin |
439 begin |
435 |
440 |
436 lemma m_s_anti_mono: "S1 \<le> S2 \<Longrightarrow> m_s S1 \<ge> m_s S2" |
441 lemma m_s_anti_mono: "S1 \<le> S2 \<Longrightarrow> m_s S1 \<ge> m_s S2" |
437 proof(auto simp add: less_eq_st_def m_s_def) |
442 proof(auto simp add: less_eq_st_def m_s_def) |
488 |
493 |
489 |
494 |
490 definition n_s :: "'av st \<Rightarrow> nat" ("n\<^isub>s") where |
495 definition n_s :: "'av st \<Rightarrow> nat" ("n\<^isub>s") where |
491 "n\<^isub>s S = (\<Sum>x\<in>dom S. n(fun S x))" |
496 "n\<^isub>s S = (\<Sum>x\<in>dom S. n(fun S x))" |
492 |
497 |
493 lemma n_s_mono: assumes "S1 \<le> S2" shows "n\<^isub>s S1 \<le> n\<^isub>s S2" |
498 lemma less_stD: |
494 proof- |
499 "(S1 < S2) \<Longrightarrow> (S1 \<le> S2 \<and> (\<exists>x\<in>dom S1. fun S1 x < fun S2 x))" |
495 from assms have [simp]: "dom S1 = dom S2" "\<forall>x\<in>dom S1. fun S1 x \<le> fun S2 x" |
500 by (metis less_eq_st_def less_le_not_le) |
496 by(simp_all add: less_eq_st_def) |
|
497 have "(\<Sum>x\<in>dom S1. n(fun S1 x)) \<le> (\<Sum>x\<in>dom S1. n(fun S2 x))" |
|
498 by(rule setsum_mono)(simp add: less_eq_st_def n_mono) |
|
499 thus ?thesis by(simp add: n_s_def) |
|
500 qed |
|
501 |
501 |
502 lemma n_s_narrow: |
502 lemma n_s_narrow: |
503 assumes "finite(dom S1)" and "S2 \<le> S1" "\<not> S1 \<le> S1 \<triangle> S2" |
503 assumes "finite(dom S1)" and "S2 \<le> S1" "S1 \<triangle> S2 < S1" |
504 shows "n\<^isub>s (S1 \<triangle> S2) < n\<^isub>s S1" |
504 shows "n\<^isub>s (S1 \<triangle> S2) < n\<^isub>s S1" |
505 proof- |
505 proof- |
506 from `S2\<le>S1` have [simp]: "dom S1 = dom S2" "\<forall>x\<in>dom S1. fun S2 x \<le> fun S1 x" |
506 from `S2\<le>S1` |
|
507 have dom[simp]: "dom S1 = dom S2" and "\<forall>x\<in>dom S1. fun S2 x \<le> fun S1 x" |
507 by(simp_all add: less_eq_st_def) |
508 by(simp_all add: less_eq_st_def) |
508 have 1: "\<forall>x\<in>dom S1. n(fun (S1 \<triangle> S2) x) \<le> n(fun S1 x)" |
509 { fix x assume "x \<in> dom S1" |
509 by(auto simp: less_eq_st_def narrow_st_def n_mono WN_class.narrow2) |
510 hence "n(fun (S1 \<triangle> S2) x) \<le> n(fun S1 x)" |
510 have 2: "\<exists>x\<in>dom S1. n(fun (S1 \<triangle> S2) x) < n(fun S1 x)" using `\<not> S1 \<le> S1 \<triangle> S2` |
511 using less_stD[OF `S1 \<triangle> S2 < S1`] `S2 \<le> S1` dom |
511 by(force simp: less_eq_st_def narrow_st_def intro: n_narrow) |
512 apply(auto simp: less_eq_st_def narrow_st_def) |
|
513 by (metis less_le n_narrow not_less) |
|
514 } note 1 = this |
|
515 have 2: "\<exists>x\<in>dom S1. n(fun (S1 \<triangle> S2) x) < n(fun S1 x)" |
|
516 using less_stD[OF `S1 \<triangle> S2 < S1`] `S2 \<le> S1` |
|
517 by(auto simp: less_eq_st_def narrow_st_def intro: n_narrow) |
512 have "(\<Sum>x\<in>dom S1. n(fun (S1 \<triangle> S2) x)) < (\<Sum>x\<in>dom S1. n(fun S1 x))" |
518 have "(\<Sum>x\<in>dom S1. n(fun (S1 \<triangle> S2) x)) < (\<Sum>x\<in>dom S1. n(fun S1 x))" |
513 apply(rule setsum_strict_mono_ex1[OF `finite(dom S1)`]) using 1 2 by blast+ |
519 apply(rule setsum_strict_mono_ex1[OF `finite(dom S1)`]) using 1 2 by blast+ |
514 moreover have "dom (S1 \<triangle> S2) = dom S1" by(simp add: narrow_st_def) |
520 moreover have "dom (S1 \<triangle> S2) = dom S1" by(simp add: narrow_st_def) |
515 ultimately show ?thesis by(simp add: n_s_def) |
521 ultimately show ?thesis by(simp add: n_s_def) |
516 qed |
522 qed |
517 |
523 |
518 |
524 |
519 definition n_o :: "'av st option \<Rightarrow> nat" ("n\<^isub>o") where |
525 definition n_o :: "'av st option \<Rightarrow> nat" ("n\<^isub>o") where |
520 "n\<^isub>o opt = (case opt of None \<Rightarrow> 0 | Some S \<Rightarrow> n\<^isub>s S + 1)" |
526 "n\<^isub>o opt = (case opt of None \<Rightarrow> 0 | Some S \<Rightarrow> n\<^isub>s S + 1)" |
521 |
527 |
522 lemma n_o_mono: "S1 \<le> S2 \<Longrightarrow> n\<^isub>o S1 \<le> n\<^isub>o S2" |
528 (* FIXME mv *) |
523 by(induction S1 S2 rule: less_eq_option.induct)(auto simp: n_o_def n_s_mono) |
529 lemma [simp]: "(Some x < Some y) = (x < y)" |
|
530 by(auto simp: less_le) |
524 |
531 |
525 lemma n_o_narrow: |
532 lemma n_o_narrow: |
526 "S1 \<in> L X \<Longrightarrow> S2 \<in> L X \<Longrightarrow> finite X |
533 "S1 \<in> L X \<Longrightarrow> S2 \<in> L X \<Longrightarrow> finite X |
527 \<Longrightarrow> S2 \<le> S1 \<Longrightarrow> \<not> S1 \<le> S1 \<triangle> S2 \<Longrightarrow> n\<^isub>o (S1 \<triangle> S2) < n\<^isub>o S1" |
534 \<Longrightarrow> S2 \<le> S1 \<Longrightarrow> S1 \<triangle> S2 < S1 \<Longrightarrow> n\<^isub>o (S1 \<triangle> S2) < n\<^isub>o S1" |
528 apply(induction S1 S2 rule: narrow_option.induct) |
535 apply(induction S1 S2 rule: narrow_option.induct) |
529 apply(auto simp: n_o_def L_st_def n_s_narrow) |
536 apply(auto simp: n_o_def L_st_def n_s_narrow) |
530 done |
537 done |
531 |
538 |
532 |
539 |
533 definition n_c :: "'av st option acom \<Rightarrow> nat" ("n\<^isub>c") where |
540 definition n_c :: "'av st option acom \<Rightarrow> nat" ("n\<^isub>c") where |
534 "n\<^isub>c C = (let as = annos C in \<Sum>i<size as. n\<^isub>o (as!i))" |
541 "n\<^isub>c C = (let as = annos C in \<Sum>i<size as. n\<^isub>o (as!i))" |
535 |
542 |
|
543 lemma less_annos_iff: "(C1 < C2) = (C1 \<le> C2 \<and> |
|
544 (\<exists>i<length (annos C1). annos C1 ! i < annos C2 ! i))" |
|
545 by(metis (hide_lams, no_types) less_le_not_le le_iff_le_annos size_annos_same2) |
|
546 |
536 lemma n_c_narrow: "C1 \<in> Lc c \<Longrightarrow> C2 \<in> Lc c \<Longrightarrow> |
547 lemma n_c_narrow: "C1 \<in> Lc c \<Longrightarrow> C2 \<in> Lc c \<Longrightarrow> |
537 C2 \<le> C1 \<Longrightarrow> \<not> C1 \<le> C1 \<triangle> C2 \<Longrightarrow> n\<^isub>c (C1 \<triangle> C2) < n\<^isub>c C1" |
548 C2 \<le> C1 \<Longrightarrow> C1 \<triangle> C2 < C1 \<Longrightarrow> n\<^isub>c (C1 \<triangle> C2) < n\<^isub>c C1" |
538 apply(auto simp: n_c_def Let_def Lc_acom_def narrow_acom_def) |
549 apply(auto simp: n_c_def Let_def Lc_acom_def narrow_acom_def) |
539 apply(subgoal_tac "length(annos C2) = length(annos C1)") |
550 apply(subgoal_tac "length(annos C2) = length(annos C1)") |
540 prefer 2 apply (simp add: size_annos_same2) |
551 prefer 2 apply (simp add: size_annos_same2) |
541 apply (auto) |
552 apply (auto) |
|
553 apply(simp add: less_annos_iff le_iff_le_annos) |
542 apply(rule setsum_strict_mono_ex1) |
554 apply(rule setsum_strict_mono_ex1) |
543 apply simp |
555 apply auto |
544 apply (clarsimp) |
556 apply (metis n_o_narrow nth_mem finite_cvars less_imp_le le_less order_refl) |
545 apply(rule n_o_mono) |
|
546 apply(rule narrow2) |
|
547 apply(fastforce simp: le_iff_le_annos listrel_iff_nth) |
|
548 apply(auto simp: le_iff_le_annos listrel_iff_nth) |
|
549 apply(rule_tac x=i in bexI) |
557 apply(rule_tac x=i in bexI) |
550 prefer 2 apply simp |
558 prefer 2 apply simp |
551 apply(rule n_o_narrow[where X = "vars(strip C1)"]) |
559 apply(rule n_o_narrow[where X = "vars(strip C1)"]) |
552 apply (simp add: finite_cvars)+ |
560 apply (simp_all add: finite_cvars) |
553 done |
561 done |
554 |
562 |
555 end |
563 end |
556 |
564 |
557 |
565 |
572 lemma iter_narrow_termination: |
580 lemma iter_narrow_termination: |
573 fixes n :: "'a::WN_Lc \<Rightarrow> nat" |
581 fixes n :: "'a::WN_Lc \<Rightarrow> nat" |
574 assumes P_f: "\<And>C. P C \<Longrightarrow> P(f C)" |
582 assumes P_f: "\<And>C. P C \<Longrightarrow> P(f C)" |
575 and P_narrow: "\<And>C1 C2. P C1 \<Longrightarrow> P C2 \<Longrightarrow> P(C1 \<triangle> C2)" |
583 and P_narrow: "\<And>C1 C2. P C1 \<Longrightarrow> P C2 \<Longrightarrow> P(C1 \<triangle> C2)" |
576 and mono: "\<And>C1 C2. P C1 \<Longrightarrow> P C2 \<Longrightarrow> C1 \<le> C2 \<Longrightarrow> f C1 \<le> f C2" |
584 and mono: "\<And>C1 C2. P C1 \<Longrightarrow> P C2 \<Longrightarrow> C1 \<le> C2 \<Longrightarrow> f C1 \<le> f C2" |
577 and n_narrow: "\<And>C1 C2. P C1 \<Longrightarrow> P C2 \<Longrightarrow> C2 \<le> C1 \<Longrightarrow> ~ C1 \<le> C1 \<triangle> C2 \<Longrightarrow> n(C1 \<triangle> C2) < n C1" |
585 and n_narrow: "\<And>C1 C2. P C1 \<Longrightarrow> P C2 \<Longrightarrow> C2 \<le> C1 \<Longrightarrow> C1 \<triangle> C2 < C1 \<Longrightarrow> n(C1 \<triangle> C2) < n C1" |
578 and init: "P C" "f C \<le> C" shows "EX C'. iter_narrow f C = Some C'" |
586 and init: "P C" "f C \<le> C" shows "EX C'. iter_narrow f C = Some C'" |
579 proof(simp add: iter_narrow_def, |
587 proof(simp add: iter_narrow_def, |
580 rule measure_while_option_Some[where f=n and P = "%C. P C \<and> f C \<le> C"]) |
588 rule measure_while_option_Some[where f=n and P = "%C. P C \<and> f C \<le> C"]) |
581 show "P C \<and> f C \<le> C" using init by blast |
589 show "P C \<and> f C \<le> C" using init by blast |
582 next |
590 next |
583 fix C assume 1: "P C \<and> f C \<le> C" and 2: "\<not> C \<le> C \<triangle> f C" |
591 fix C assume 1: "P C \<and> f C \<le> C" and 2: "C \<triangle> f C < C" |
584 hence "P (C \<triangle> f C)" by(simp add: P_f P_narrow) |
592 hence "P (C \<triangle> f C)" by(simp add: P_f P_narrow) |
585 moreover then have "f (C \<triangle> f C) \<le> C \<triangle> f C" |
593 moreover then have "f (C \<triangle> f C) \<le> C \<triangle> f C" |
586 by (metis narrow1 narrow2 1 mono order_trans) |
594 by (metis narrow1 narrow2 1 mono order_trans) |
587 moreover have "n (C \<triangle> f C) < n C" using 1 2 by(simp add: n_narrow P_f) |
595 moreover have "n (C \<triangle> f C) < n C" using 1 2 by(simp add: n_narrow P_f) |
588 ultimately show "(P (C \<triangle> f C) \<and> f (C \<triangle> f C) \<le> C \<triangle> f C) \<and> n(C \<triangle> f C) < n C" |
596 ultimately show "(P (C \<triangle> f C) \<and> f (C \<triangle> f C) \<le> C \<triangle> f C) \<and> n(C \<triangle> f C) < n C" |
623 split: prod.split extended.splits if_splits) |
631 split: prod.split extended.splits if_splits) |
624 |
632 |
625 definition n_ivl :: "ivl \<Rightarrow> nat" where |
633 definition n_ivl :: "ivl \<Rightarrow> nat" where |
626 "n_ivl ivl = 3 - m_ivl ivl" |
634 "n_ivl ivl = 3 - m_ivl ivl" |
627 |
635 |
628 lemma n_ivl_mono: "x \<le> y \<Longrightarrow> n_ivl x \<le> n_ivl y" |
|
629 unfolding n_ivl_def by (metis diff_le_mono2 m_ivl_anti_mono) |
|
630 |
|
631 lemma n_ivl_narrow: |
636 lemma n_ivl_narrow: |
632 "~ x \<le> x \<triangle> y \<Longrightarrow> n_ivl(x \<triangle> y) < n_ivl x" |
637 "x \<triangle> y < x \<Longrightarrow> n_ivl(x \<triangle> y) < n_ivl x" |
633 unfolding n_ivl_def |
638 unfolding n_ivl_def |
634 by transfer |
639 apply(subst (asm) less_le_not_le) |
635 (auto simp add: m_rep_def narrow_rep_def is_empty_rep_def empty_rep_def \<gamma>_rep_cases le_iff_subset |
640 apply transfer |
636 split: prod.splits if_splits extended.splits) |
641 by(auto simp add: m_rep_def narrow_rep_def is_empty_rep_def empty_rep_def \<gamma>_rep_cases le_iff_subset |
|
642 split: prod.splits if_splits extended.split) |
637 |
643 |
638 |
644 |
639 interpretation Abs_Int2_measure |
645 interpretation Abs_Int2_measure |
640 where \<gamma> = \<gamma>_ivl and num' = num_ivl and plus' = "op +" |
646 where \<gamma> = \<gamma>_ivl and num' = num_ivl and plus' = "op +" |
641 and test_num' = in_ivl |
647 and test_num' = in_ivl |