# HG changeset patch # User Christian Urban # Date 1498642625 -3600 # Node ID 222ed43892ea1e71f6e511ae70d188c871c0c0ba # Parent 7c89d3f6923e83ee1ceeac02fdfacb2d5e61b080 updated diff -r 7c89d3f6923e -r 222ed43892ea thys/Positions.thy --- a/thys/Positions.thy Tue Jun 27 13:15:55 2017 +0100 +++ b/thys/Positions.thy Wed Jun 28 10:37:05 2017 +0100 @@ -46,7 +46,7 @@ "intlen [] = 0" | "intlen (x#xs) = 1 + intlen xs" -lemma inlen_bigger: +lemma intlen_bigger: shows "0 \ intlen xs" by (induct xs)(auto) @@ -62,9 +62,19 @@ apply(auto) apply(case_tac ys) apply(simp_all) -apply (smt inlen_bigger) +apply (smt intlen_bigger) by (smt Suc_lessE intlen.simps(2) length_Suc_conv) +lemma length_intlen: + assumes "intlen xs < intlen ys" + shows "length xs < length ys" +using assms +apply(induct xs arbitrary: ys) +apply(auto) +apply(case_tac ys) +apply(simp_all) +by (smt intlen_bigger) + definition pflat_len :: "val \ nat list => int" where @@ -179,6 +189,21 @@ where "v1 :\val v2 \ v1 :\val v2 \ v1 = v2" +lemma val_ord_shorterE: + assumes "v1 :\val v2" + shows "length (flat v2) \ length (flat v1)" +using assms +apply(auto simp add: val_ord_ex_def val_ord_def) +apply(case_tac p) +apply(simp add: pflat_len_simps) +apply(drule length_intlen) +apply(simp) +apply(drule_tac x="[]" in bspec) +apply(simp add: Pos_empty) +apply(simp add: pflat_len_simps) +by (metis intlen_length le_less less_irrefl linear) + + lemma val_ord_shorterI: assumes "length (flat v') < length (flat v)" shows "v :\val v'" @@ -474,7 +499,7 @@ apply (metis (no_types, hide_lams) lex_trans outside_lemma) apply(simp add: val_ord_def) apply(auto)[1] -by (smt inlen_bigger lex_trans outside_lemma pflat_len_def) +by (smt intlen_bigger lex_trans outside_lemma pflat_len_def) section {* CPT and CPTpre *} @@ -816,7 +841,7 @@ apply(simp add: Pos_empty) apply(rule conjI) apply(simp add: pflat_len_simps) -apply (smt inlen_bigger) +apply (smt intlen_bigger) apply(simp) apply(rule conjI) apply(simp add: pflat_len_simps) @@ -1093,7 +1118,7 @@ apply(drule_tac x="[0]" in spec) apply(simp add: pflat_len_simps Pos_empty) apply(drule mp) -apply (smt inlen_bigger) +apply (smt intlen_bigger) apply(erule disjE) apply blast apply auto[1] diff -r 7c89d3f6923e -r 222ed43892ea thys/Sulzmann.thy --- a/thys/Sulzmann.thy Tue Jun 27 13:15:55 2017 +0100 +++ b/thys/Sulzmann.thy Wed Jun 28 10:37:05 2017 +0100 @@ -6,6 +6,20 @@ section {* Sulzmann's "Ordering" of Values *} +inductive ValOrd :: "val \ val \ bool" ("_ \ _" [100, 100] 100) +where + MY0: "length (flat v2) < length (flat v1) \ v1 \ v2" +| C2: "\v1 \ v1'; flat (Seq v1 v2) = flat (Seq v1' v2')\ \ (Seq v1 v2) \ (Seq v1' v2')" +| C1: "\v2 \ v2'; flat v2 = flat v2'\ \ (Seq v1 v2) \ (Seq v1 v2')" +| A2: "flat v1 = flat v2 \ (Left v1) \ (Right v2)" +| A3: "\v2 \ v2'; flat v2 = flat v2'\ \ (Right v2) \ (Right v2')" +| A4: "\v1 \ v1'; flat v1 = flat v1'\ \ (Left v1) \ (Left v1')" +| K1: "flat (Stars (v#vs)) = [] \ (Stars []) \ (Stars (v#vs))" +| K3: "\v1 \ v2; flat (Stars (v1#vs1)) = flat (Stars (v2#vs2))\ \ (Stars (v1#vs1)) \ (Stars (v2#vs2))" +| K4: "\(Stars vs1) \ (Stars vs2); flat (Stars vs1) = flat (Stars vs2)\ \ (Stars (v#vs1)) \ (Stars (v#vs2))" + + +(* inductive ValOrd :: "val \ rexp \ val \ bool" ("_ \_ _" [100, 100, 100] 100) where C2: "v1 \r1 v1' \ (Seq v1 v2) \(SEQ r1 r2) (Seq v1' v2')" @@ -18,6 +32,7 @@ | K2: "flat (Stars (v # vs)) \ [] \ (Stars (v # vs)) \(STAR r) (Stars [])" | K3: "v1 \r v2 \ (Stars (v1 # vs1)) \(STAR r) (Stars (v2 # vs2))" | K4: "(Stars vs1) \(STAR r) (Stars vs2) \ (Stars (v # vs1)) \(STAR r) (Stars (v # vs2))" +*) (*| MY1: "Void \ONE Void" | MY2: "(Char c) \(CHAR c) (Char c)" | MY3: "(Stars []) \(STAR r) (Stars [])" @@ -44,7 +59,7 @@ *) lemma ValOrd_irrefl: - assumes "\ v : r" "v \r v" + assumes "\ v : r" "v \ v" shows "False" using assms apply(induct v r rule: Prf.induct) @@ -72,25 +87,105 @@ lemma Posix_CPT2: - assumes "v1 \r v2" "flat v2 \pre s" "flat v1 \pre s" + assumes "v1 \ v2" shows "v1 :\val v2" using assms -apply(induct v1 r v2 arbitrary: s rule: ValOrd.induct) -prefer 3 -apply(simp) +apply(induct v1 v2 arbitrary: rule: ValOrd.induct) apply(rule val_ord_shorterI) apply(simp) -apply(subst (asm) (3) prefix_list_def) -apply(subst (asm) (3) prefix_list_def) -apply(clarify) -apply(simp) -apply(simp add: append_eq_append_conv2) -apply(auto)[1] -apply(drule_tac x="flat v1' @ flat v2' @ usa" in meta_spec) -apply(simp add: prefix_list_def) apply(rule val_ord_SeqI1) apply(simp) apply(simp) +apply(rule val_ord_SeqI2) +apply(simp) +apply(simp) +apply(simp add: val_ord_ex_def) +apply(rule_tac x="[0]" in exI) +apply(auto simp add: val_ord_def Pos_empty pflat_len_simps)[1] +apply(smt inlen_bigger) +apply(rule val_ord_RightI) +apply(simp) +apply(simp) +apply(rule val_ord_LeftI) +apply(simp) +apply(simp) +defer +apply(rule val_ord_StarsI) +apply(simp) +apply(simp) +apply(rule val_ord_StarsI2) +apply(simp) +apply(simp) +oops + +lemma Posix_CPT2: + assumes "v1 :\val v2" "v1 \ CPTpre r s" "v2 \ CPTpre r s" + shows "v1 \ v2" +using assms +apply(induct r arbitrary: v1 v2 s) +apply(auto simp add: CPTpre_def)[1] +apply(erule CPrf.cases) +apply(simp_all)[7] +apply(auto simp add: CPTpre_def)[1] +apply(erule CPrf.cases) +apply(simp_all)[7] +apply(auto simp add: CPTpre_def)[1] +apply(erule CPrf.cases) +apply(simp_all)[7] +apply(simp add: val_ord_ex_def) +apply(auto simp add: val_ord_def)[1] +apply(auto simp add: CPTpre_def)[1] +apply(erule CPrf.cases) +apply(simp_all)[7] +apply(erule CPrf.cases) +apply(simp_all)[7] +apply(auto simp add: val_ord_ex_def val_ord_def)[1] +(* SEQ case *) +apply(subst (asm) (5) CPTpre_def) +apply(subst (asm) (5) CPTpre_def) +apply(auto)[1] +apply(erule CPrf.cases) +apply(simp_all)[7] +apply(erule CPrf.cases) +apply(simp_all)[7] +apply(clarify) +apply(drule val_ord_SeqE) +apply(erule disjE) +apply(drule_tac x="v1a" in meta_spec) +apply(rotate_tac 7) +apply(drule_tac x="v1b" in meta_spec) +apply(drule_tac x="flat v1a @ flat v2a @ s'" in meta_spec) +apply(simp) +apply(drule meta_mp) +apply(auto simp add: CPTpre_def)[1] +apply(drule meta_mp) +apply(auto simp add: CPTpre_def)[1] +apply(rule ValOrd.intros) +apply(subst (asm) (3) CPTpre_def) +apply(subst (asm) (3) CPTpre_def) +apply(auto)[1] +apply(drule_tac meta_mp) +apply(auto simp add: CPTpre_def)[1] +apply(erule CPrf.cases) +apply(simp_all)[7] +apply(erule CPrf.cases) +apply(simp_all)[7] +apply(clarify) +apply(drule val_ord_SeqE) +apply(erule disjE) +apply(simp add: append_eq_append_conv2) +apply(auto) +prefer 2 +apply(rule ValOrd.intros(2)) +prefer 2 +apply(simp) +thm ValOrd.intros +apply(case_tac "flat v1b = flat v1a") +apply(rule ValOrd.intros) +apply(simp) +apply(simp) + + lemma Posix_CPT: