src/HOL/MicroJava/BV/Kildall.thy
changeset 23467 d1b97708d5eb
parent 23281 e26ec695c9b3
child 27611 2c01c0bdb385
equal deleted inserted replaced
23466:886655a150f6 23467:d1b97708d5eb
    56   fix ss p' ps'
    56   fix ss p' ps'
    57   assume ss: "ss \<in> list n A"
    57   assume ss: "ss \<in> list n A"
    58   assume l:  "p < length ss"
    58   assume l:  "p < length ss"
    59   assume "?steptype (p'#ps')"
    59   assume "?steptype (p'#ps')"
    60   then obtain a b where
    60   then obtain a b where
    61     p': "p'=(a,b)" and ab: "a<n" "b\<in>A" and "?steptype ps'"
    61     p': "p'=(a,b)" and ab: "a<n" "b\<in>A" and ps': "?steptype ps'"
    62     by (cases p', auto)
    62     by (cases p') auto
    63   assume "\<And>ss. p< length ss \<Longrightarrow> ss \<in> list n A \<Longrightarrow> ?steptype ps' \<Longrightarrow> ?P ss ps'"
    63   assume "\<And>ss. p< length ss \<Longrightarrow> ss \<in> list n A \<Longrightarrow> ?steptype ps' \<Longrightarrow> ?P ss ps'"
    64   hence IH: "\<And>ss. ss \<in> list n A \<Longrightarrow> p < length ss \<Longrightarrow> ?P ss ps'" .
    64   from this [OF _ _ ps'] have IH: "\<And>ss. ss \<in> list n A \<Longrightarrow> p < length ss \<Longrightarrow> ?P ss ps'" .
    65 
    65 
    66   from ss ab
    66   from ss ab
    67   have "ss[a := b +_f ss!a] \<in> list n A" by (simp add: closedD)
    67   have "ss[a := b +_f ss!a] \<in> list n A" by (simp add: closedD)
    68   moreover
    68   moreover
    69   from calculation
    69   from calculation l
    70   have "p < length (ss[a := b +_f ss!a])" by simp
    70   have "p < length (ss[a := b +_f ss!a])" by simp
    71   ultimately
    71   ultimately
    72   have "?P (ss[a := b +_f ss!a]) ps'" by (rule IH)
    72   have "?P (ss[a := b +_f ss!a]) ps'" by (rule IH)
    73   with p' l
    73   with p' l
    74   show "?P ss (p'#ps')" by simp
    74   show "?P ss (p'#ps')" by simp
   252 
   252 
   253  apply (simp add: plusplus_empty)
   253  apply (simp add: plusplus_empty)
   254  apply (cases "q \<in> w")
   254  apply (cases "q \<in> w")
   255   apply simp
   255   apply simp
   256   apply (rule ub1')
   256   apply (rule ub1')
   257      apply assumption
   257      apply (rule semilat)
   258     apply clarify
   258     apply clarify
   259     apply (rule pres_typeD)
   259     apply (rule pres_typeD)
   260        apply assumption
   260        apply assumption
   261       prefer 3 apply assumption
   261       prefer 3 apply assumption
   262      apply (blast intro: listE_nth_in dest: boundedD)
   262      apply (blast intro: listE_nth_in dest: boundedD)
   445                  kildall r f step ss0 <=[r] ts)"
   445                  kildall r f step ss0 <=[r] ts)"
   446 apply (unfold kildall_def)
   446 apply (unfold kildall_def)
   447 apply(case_tac "iter f step ss0 (unstables r step ss0)")
   447 apply(case_tac "iter f step ss0 (unstables r step ss0)")
   448 apply(simp)
   448 apply(simp)
   449 apply (rule iter_properties)
   449 apply (rule iter_properties)
   450 by (simp_all add: unstables_def stable_def)
   450 apply (simp_all add: unstables_def stable_def)
       
   451 apply (rule semilat)
       
   452 done
   451 
   453 
   452 
   454 
   453 lemma is_bcv_kildall: includes semilat
   455 lemma is_bcv_kildall: includes semilat
   454 shows "\<lbrakk> acc r; top r T; pres_type step n A; bounded step n; mono r step n A \<rbrakk>
   456 shows "\<lbrakk> acc r; top r T; pres_type step n A; bounded step n; mono r step n A \<rbrakk>
   455   \<Longrightarrow> is_bcv r T step n A (kildall r f step)"
   457   \<Longrightarrow> is_bcv r T step n A (kildall r f step)"