diff -r 85ef42888929 -r 7ac7782a7318 thys/Re1.thy
--- a/thys/Re1.thy	Mon Jul 06 20:44:30 2015 +0100
+++ b/thys/Re1.thy	Thu Dec 17 13:14:36 2015 +0000
@@ -3,6 +3,7 @@
   imports "Main" 
 begin
 
+
 section {* Sequential Composition of Sets *}
 
 definition
@@ -83,6 +84,11 @@
 | Left val
 
 
+fun Seqs :: "val \<Rightarrow> val list \<Rightarrow> val"
+where
+  "Seqs v [] = v"
+| "Seqs v (v'#vs) = Seqs (Seq v v') vs"
+
 section {* The string behind a value *}
 
 fun flat :: "val \<Rightarrow> string"
@@ -166,6 +172,15 @@
 apply(auto intro: Prf.intros)
 done
 
+lemma not_nullable_flat:
+  assumes "\<turnstile> v : r" "\<not>nullable r"
+  shows "flat v \<noteq> []"
+using assms
+apply(induct)
+apply(auto)
+done
+
+
 fun mkeps :: "rexp \<Rightarrow> val"
 where
   "mkeps(EMPTY) = Void"
@@ -232,8 +247,292 @@
 done
 
 
+definition prefix :: "string \<Rightarrow> string \<Rightarrow> bool" ("_ \<sqsubseteq> _" [100, 100] 100)
+where
+  "s1 \<sqsubseteq> s2 \<equiv> \<exists>s3. s1 @ s3 = s2"
 
-section {* Ordering of values *}
+definition sprefix :: "string \<Rightarrow> string \<Rightarrow> bool" ("_ \<sqsubset> _" [100, 100] 100)
+where
+  "s1 \<sqsubset> s2 \<equiv> (s1 \<sqsubseteq> s2 \<and> s1 \<noteq> s2)"
+
+lemma length_sprefix:
+  "s1 \<sqsubset> s2 \<Longrightarrow> length s1 < length s2"
+unfolding sprefix_def prefix_def
+by (auto)
+
+definition Prefixes :: "string \<Rightarrow> string set" where
+  "Prefixes s \<equiv> {sp. sp \<sqsubseteq> s}"
+
+definition Suffixes :: "string \<Rightarrow> string set" where
+  "Suffixes s \<equiv> rev ` (Prefixes (rev s))"
+
+lemma Suffixes_in: 
+  "\<exists>s1. s1 @ s2 = s3 \<Longrightarrow> s2 \<in> Suffixes s3"
+unfolding Suffixes_def Prefixes_def prefix_def image_def
+apply(auto)
+by (metis rev_rev_ident)
+
+lemma Prefixes_Cons:
+  "Prefixes (c # s) = {[]} \<union> {c # sp | sp. sp \<in> Prefixes s}"
+unfolding Prefixes_def prefix_def
+apply(auto simp add: append_eq_Cons_conv) 
+done
+
+lemma finite_Prefixes:
+  "finite (Prefixes s)"
+apply(induct s)
+apply(auto simp add: Prefixes_def prefix_def)[1]
+apply(simp add: Prefixes_Cons)
+done
+
+lemma finite_Suffixes:
+  "finite (Suffixes s)"
+unfolding Suffixes_def
+apply(rule finite_imageI)
+apply(rule finite_Prefixes)
+done
+
+lemma prefix_Cons:
+  "((c # s1) \<sqsubseteq> (c # s2)) = (s1 \<sqsubseteq> s2)"
+apply(auto simp add: prefix_def)
+done
+
+lemma prefix_append:
+  "((s @ s1) \<sqsubseteq> (s @ s2)) = (s1 \<sqsubseteq> s2)"
+apply(induct s)
+apply(simp)
+apply(simp add: prefix_Cons)
+done
+
+
+
+definition Values :: "rexp \<Rightarrow> string \<Rightarrow> val set" where
+  "Values r s \<equiv> {v. \<turnstile> v : r \<and> flat v \<sqsubseteq> s}"
+
+definition rest :: "val \<Rightarrow> string \<Rightarrow> string" where
+  "rest v s \<equiv> drop (length (flat v)) s"
+
+lemma rest_Suffixes:
+  "rest v s \<in> Suffixes s"
+unfolding rest_def
+by (metis Suffixes_in append_take_drop_id)
+
+
+lemma Values_recs:
+  "Values (NULL) s = {}"
+  "Values (EMPTY) s = {Void}"
+  "Values (CHAR c) s = (if [c] \<sqsubseteq> s then {Char c} else {})" 
+  "Values (ALT r1 r2) s = {Left v | v. v \<in> Values r1 s} \<union> {Right v | v. v \<in> Values r2 s}"
+  "Values (SEQ r1 r2) s = {Seq v1 v2 | v1 v2. v1 \<in> Values r1 s \<and> v2 \<in> Values r2 (rest v1 s)}"
+unfolding Values_def
+apply(auto)
+(*NULL*)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+(*EMPTY*)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rule Prf.intros)
+apply (metis append_Nil prefix_def)
+(*CHAR*)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rule Prf.intros)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+(*ALT*)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis Prf.intros(2))
+apply (metis Prf.intros(3))
+(*SEQ*)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (simp add: append_eq_conv_conj prefix_def rest_def)
+apply (metis Prf.intros(1))
+apply (simp add: append_eq_conv_conj prefix_def rest_def)
+done
+
+lemma Values_finite:
+  "finite (Values r s)"
+apply(induct r arbitrary: s)
+apply(simp_all add: Values_recs)
+thm finite_surj
+apply(rule_tac f="\<lambda>(x, y). Seq x y" and 
+               A="{(v1, v2) | v1 v2. v1 \<in> Values r1 s \<and> v2 \<in> Values r2 (rest v1 s)}" in finite_surj)
+prefer 2
+apply(auto)[1]
+apply(rule_tac B="\<Union>sp \<in> Suffixes s. {(v1, v2). v1 \<in> Values r1 s \<and> v2 \<in> Values r2 sp}" in finite_subset)
+apply(auto)[1]
+apply (metis rest_Suffixes)
+apply(rule finite_UN_I)
+apply(rule finite_Suffixes)
+apply(simp)
+done
+
+section {* Greedy Ordering according to Frisch/Cardelli *}
+
+inductive GrOrd :: "val \<Rightarrow> val \<Rightarrow> bool" ("_ \<prec> _")
+where 
+  "v1 \<prec> v1' \<Longrightarrow> (Seq v1 v2) \<prec> (Seq v1' v2')"
+| "v2 \<prec> v2' \<Longrightarrow> (Seq v1 v2) \<prec> (Seq v1 v2')"
+| "v1 \<prec> v2 \<Longrightarrow> (Left v1) \<prec> (Left v2)"
+| "v1 \<prec> v2 \<Longrightarrow> (Right v1) \<prec> (Right v2)"
+| "(Right v1) \<prec> (Left v2)"
+| "(Char c) \<prec> (Char c)"
+| "(Void) \<prec> (Void)"
+
+lemma Gr_refl:
+  assumes "\<turnstile> v : r"
+  shows "v \<prec> v"
+using assms
+apply(induct)
+apply(auto intro: GrOrd.intros)
+done
+
+lemma Gr_total:
+  assumes "\<turnstile> v1 : r" "\<turnstile> v2 : r"
+  shows "v1 \<prec> v2 \<or> v2 \<prec> v1"
+using assms
+apply(induct v1 r arbitrary: v2 rule: Prf.induct)
+apply(rotate_tac 4)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply (metis GrOrd.intros(1) GrOrd.intros(2))
+apply(rotate_tac 2)
+apply(erule Prf.cases)
+apply(simp_all)
+apply(clarify)
+apply (metis GrOrd.intros(3))
+apply(clarify)
+apply (metis GrOrd.intros(5))
+apply(rotate_tac 2)
+apply(erule Prf.cases)
+apply(simp_all)
+apply(clarify)
+apply (metis GrOrd.intros(5))
+apply(clarify)
+apply (metis GrOrd.intros(4))
+apply(erule Prf.cases)
+apply(simp_all)
+apply (metis GrOrd.intros(7))
+apply(erule Prf.cases)
+apply(simp_all)
+apply (metis GrOrd.intros(6))
+done
+
+lemma Gr_trans: 
+  assumes "v1 \<prec> v2" "v2 \<prec> v3" "\<turnstile> v1 : r" "\<turnstile> v2 : r" "\<turnstile> v3 : r"
+  shows "v1 \<prec> v3"
+using assms
+apply(induct r arbitrary: v1 v2 v3)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+defer
+(* ALT case *)
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(clarify)
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply (metis GrOrd.intros(3))
+apply(clarify)
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(clarify)
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(clarify)
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(clarify)
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply (metis GrOrd.intros(5))
+apply(clarify)
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(clarify)
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply (metis GrOrd.intros(5))
+apply(clarify)
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply (metis GrOrd.intros(4))
+(* seq case *)
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(clarify)
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply(clarify)
+apply (metis GrOrd.intros(1))
+apply (metis GrOrd.intros(1))
+apply(erule GrOrd.cases)
+apply(simp_all (no_asm_use))[7]
+apply (metis GrOrd.intros(1))
+by (metis GrOrd.intros(1) Gr_refl)
+
+definition
+  GrMaxM :: "val set => val" where
+  "GrMaxM S == SOME v.  v \<in> S \<and> (\<forall>v' \<in> S. v' \<prec> v)"
+
+definition
+  "GrMax r s \<equiv> GrMaxM {v. \<turnstile> v : r \<and> flat v = s}"
+
+inductive ValOrd3 :: "val \<Rightarrow> val \<Rightarrow> bool" ("_ 3\<succ> _" [100, 100] 100)
+where
+  "v2 3\<succ> v2' \<Longrightarrow> (Seq v1 v2) 3\<succ> (Seq v1 v2')" 
+| "v1 3\<succ> v1' \<Longrightarrow> (Seq v1 v2) 3\<succ> (Seq v1' v2')" 
+| "length (flat v1) \<ge> length (flat v2) \<Longrightarrow> (Left v1) 3\<succ> (Right v2)"
+| "length (flat v2) > length (flat v1) \<Longrightarrow> (Right v2) 3\<succ> (Left v1)"
+| "v2 3\<succ> v2' \<Longrightarrow> (Right v2) 3\<succ> (Right v2')"
+| "v1 3\<succ> v1' \<Longrightarrow> (Left v1) 3\<succ> (Left v1')"
+| "Void 3\<succ> Void"
+| "(Char c) 3\<succ> (Char c)"
+
+
+section {* Sulzmann's Ordering of values *}
 
 inductive ValOrd :: "val \<Rightarrow> rexp \<Rightarrow> val \<Rightarrow> bool" ("_ \<succ>_ _" [100, 100, 100] 100)
 where
@@ -246,6 +545,16 @@
 | "Void \<succ>EMPTY Void"
 | "(Char c) \<succ>(CHAR c) (Char c)"
 
+inductive ValOrdStr :: "string \<Rightarrow> val \<Rightarrow> val \<Rightarrow> bool" ("_ \<turnstile> _ \<succ>_" [100, 100, 100] 100)
+where
+  "\<lbrakk>s \<turnstile> v1 \<succ> v1'; rest v1 s \<turnstile> v2 \<succ> v2'\<rbrakk> \<Longrightarrow> s \<turnstile> (Seq v1 v2) \<succ> (Seq v1' v2')" 
+| "\<lbrakk>flat v2 \<sqsubseteq> flat v1; flat v1 \<sqsubseteq> s\<rbrakk> \<Longrightarrow> s \<turnstile> (Left v1) \<succ> (Right v2)"
+| "\<lbrakk>flat v1 \<sqsubset> flat v2; flat v2 \<sqsubseteq> s\<rbrakk> \<Longrightarrow> s \<turnstile> (Right v2) \<succ> (Left v1)"
+| "s \<turnstile> v2 \<succ> v2' \<Longrightarrow> s \<turnstile> (Right v2) \<succ> (Right v2')"
+| "s \<turnstile> v1 \<succ> v1' \<Longrightarrow> s \<turnstile> (Left v1) \<succ> (Left v1')"
+| "s \<turnstile> Void \<succ> Void"
+| "(c#s) \<turnstile> (Char c) \<succ> (Char c)"
+
 inductive ValOrd2 :: "val \<Rightarrow> val \<Rightarrow> bool" ("_ 2\<succ> _" [100, 100] 100)
 where
   "v2 2\<succ> v2' \<Longrightarrow> (Seq v1 v2) 2\<succ> (Seq v1 v2')" 
@@ -388,179 +697,15 @@
 apply(simp_all)[8]
 done
 
-definition prefix :: "string \<Rightarrow> string \<Rightarrow> bool" ("_ \<sqsubseteq> _" [100, 100] 100)
-where
-  "s1 \<sqsubseteq> s2 \<equiv> \<exists>s3. s1 @ s3 = s2"
-
+lemma refl_on_ValOrd:
+  "refl_on (Values r s) {(v1, v2). v1 \<succ>r v2 \<and> v1 \<in> Values r s \<and> v2 \<in> Values r s}"
+unfolding refl_on_def
+apply(auto)
+apply(rule ValOrd_refl)
+apply(simp add: Values_def)
+done
 
-lemma
-  "L r \<noteq> {} \<longrightarrow> (\<exists>vmax \<in> {v. \<turnstile> v : r}. \<forall>v \<in> {v. \<turnstile> v : r \<and> flat v \<sqsubseteq> flat vmax}. vmax 2\<succ> v)"
-apply(induct r)
-apply(simp)
-apply(rule impI)
-apply(simp)
-apply(rule_tac x="Void" in exI)
-apply(simp)
-apply(rule conjI)
-apply (metis Prf.intros(4))
-apply(rule allI)
-apply(rule impI)
-apply(erule conjE)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd2.intros(7))
-apply(simp)
-apply(rule_tac x="Char char" in exI)
-apply(simp)
-apply(rule conjI)
-apply (metis Prf.intros)
-apply(rule allI)
-apply(rule impI)
-apply(erule conjE)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd2.intros(8))
-apply(simp)
-apply(rule impI)
-apply(simp add: Sequ_def)[1]
-apply(erule exE)+
-apply(erule conjE)+
-apply(clarify)
-defer
-apply(rule impI)
-apply(drule L_ALT_cases)
-apply(erule disjE)
-apply(simp)
-apply(erule exE)
-apply(clarify)
-apply(rule_tac x="Left vmax" in exI)
-apply(rule conjI)
-apply (metis Prf.intros(2))
-apply(simp)
-apply(rule allI)
-apply(rule impI)
-apply(erule conjE)
-apply(rotate_tac 4)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd2.intros(6))
-apply(clarify)
-apply (metis ValOrd2.intros(3) length_append ordered_cancel_comm_monoid_diff_class.le_iff_add prefix_def)
-apply(simp)
-apply(clarify)
-apply(rule_tac x="Right vmax" in exI)
-apply(rule conjI)
-apply (metis Prf.intros(3))
-apply(rule allI)
-apply(rule impI)
-apply(erule conjE)+
-apply(simp)
-apply(rotate_tac 4)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis Prf_flat_L empty_iff)
-apply (metis ValOrd2.intros(5))
-apply(drule mp)
-apply (metis empty_iff)
-apply(drule mp)
-apply (metis empty_iff)
-apply(erule exE)+
-apply(erule conjE)+
-apply(rule_tac x="Seq vmax vmaxa" in exI)
-apply(rule conjI)
-apply (metis Prf.intros(1))
-apply(rule allI)
-apply(rule impI)
-apply(erule conjE)+
-apply(simp)
-apply(rotate_tac 6)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply(case_tac "vmax = v1")
-apply(simp)
-apply (simp add: ValOrd2.intros(1) prefix_def)
-
-lemma
-  "s \<in> L r \<longrightarrow> (\<exists>vmax \<in> {v. \<turnstile> v : r \<and> flat v = s}. \<forall>v \<in> {v. \<turnstile> v : r \<and> flat v = s}. vmax 2\<succ> v)"
-apply(induct s arbitrary: r rule: length_induct)
-apply(induct_tac r rule: rexp.induct)
-apply(rule impI)
-apply(simp)
-apply(simp)
-apply(rule impI)
-apply(simp)
-apply(rule_tac x="Void" in exI)
-apply(simp)
-apply(rule conjI)
-apply (metis Prf.intros(4))
-apply(rule allI)
-apply(rule impI)
-apply(erule conjE)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd2.intros(7))
-apply(simp)
-apply(rule impI)
-apply(rule_tac x="Char char" in exI)
-apply(simp)
-apply(rule conjI)
-apply (metis Prf.intros)
-apply(rule allI)
-apply(rule impI)
-apply(erule conjE)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd2.intros(8))
-apply(simp)
-apply(rule impI)
-apply(simp add: Sequ_def)[1]
-apply(erule exE)+
-apply(erule conjE)+
-apply(clarify)
-defer
-apply(simp)
-apply(rule conjI)
-apply(rule impI)
-apply(simp)
-apply(erule exE)
-apply(clarify)
-apply(rule_tac x="Left vmax" in exI)
-apply(rule conjI)
-apply (metis Prf.intros(2))
-apply(simp)
-apply(rule allI)
-apply(rule impI)
-apply(erule conjE)
-apply(rotate_tac 5)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd2.intros(6))
-apply(clarify)
-apply (metis ValOrd2.intros(3) order_refl)
-apply(rule impI)
-apply(simp)
-apply(erule exE)
-apply(clarify)
-apply(rule_tac x="Right vmax" in exI)
-apply(simp)
-apply(rule conjI)
-apply (metis Prf.intros(3))
-apply(rule allI)
-apply(rule impI)
-apply(erule conjE)+
-apply(rotate_tac 5)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd2.intros(8))
-apply(simp)
-apply(rule impI)
-apply(simp add: Sequ_def)[1]
-apply(erule exE)+
-apply(erule conjE)+
-apply(clarify)
-
-
+(*
 inductive ValOrd3 :: "val \<Rightarrow> rexp \<Rightarrow> val \<Rightarrow> bool" ("_ 3\<succ>_ _" [100, 100, 100] 100)
 where
   "\<lbrakk>v2 3\<succ>r2 v2'; \<turnstile> v1 : r1\<rbrakk> \<Longrightarrow> (Seq v1 v2) 3\<succ>(SEQ r1 r2) (Seq v1 v2')" 
@@ -572,147 +717,7 @@
 | "v1 3\<succ>r1 v1' \<Longrightarrow> (Left v1) 3\<succ>(ALT r1 r2) (Left v1')"
 | "Void 3\<succ>EMPTY Void"
 | "(Char c) 3\<succ>(CHAR c) (Char c)"
-
-
-lemma "v1 3\<succ>r v2 \<Longrightarrow> v1 \<succ>r v2 \<and> \<turnstile> v1 : r \<and> \<turnstile> v2 : r \<and> flat v1 = flat v2"
-apply(induct rule: ValOrd3.induct)
-prefer 8
-apply(simp)
-apply (metis Prf.intros(5) ValOrd.intros(8))
-prefer 7
-apply(simp)
-apply (metis Prf.intros(4) ValOrd.intros(7))
-apply(simp)
-apply (metis Prf.intros(1) ValOrd.intros(1))
-apply(simp)
-
-
-
-
-lemma ValOrd_trans:
-  assumes "v1 \<succ>r v2" "v2 \<succ>r v3" "\<turnstile> v1 : r" "\<turnstile> v2 : r" "\<turnstile> v3 : r" 
-     "flat v1 = flat v2" "flat v2 = flat v3"
-  shows "v1 \<succ>r v3"
-using assms
-apply(induct r arbitrary: v1 v2 v3 s1 s2 s3)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(clarify)
-apply (metis ValOrd.intros(1))
-apply(clarify)
-apply (metis ValOrd.intros(2))
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply (metis ValOrd.intros(2))
-apply(clarify)
-apply(case_tac "v1d = v1'a")
-apply(simp)
-apply (metis ValOrd_anti)
-apply (rule ValOrd.intros(2))
-prefer 2
-apply(auto)[1]
-apply metis
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply (metis Ord1 Ord3 Prf.intros(2) ValOrd2.intros(6))
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply (rule ValOrd.intros)
-apply(clarify)
-oops
-
-
-lemma ValOrd_max:
-  shows "L r \<noteq> {} \<Longrightarrow> \<exists>v. \<turnstile> v : r \<and> (\<forall>v'. (\<turnstile> v' : r \<longrightarrow> v' \<succ>r v \<longrightarrow> v = v'))" 
-using assms
-apply(induct r)
-apply(auto)[3]
-apply(rule_tac x="Void" in exI)
-apply(rule conjI)
-apply (metis Prf.intros(4))
-apply(rule allI)
-apply(rule impI)+
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(rule_tac x="Char char" in exI)
-apply(rule conjI)
-apply (metis Prf.intros(5))
-apply(rule allI)
-apply(rule impI)+
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(simp add: L.simps)
-apply(auto simp: Sequ_def)[1]
-apply(drule meta_mp)
-apply (metis empty_iff)
-apply(drule meta_mp)
-apply (metis empty_iff)
-apply(erule exE)+
-apply(rule_tac x="Seq v va" in exI)
-apply(rule conjI)
-apply (metis Prf.intros(1))
-apply(rule allI)
-apply(rule impI)+
-apply(rotate_tac 4)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply metis
-apply(simp only: L.simps Lattices.bounded_lattice_bot_class.sup_eq_bot_iff HOL.de_Morgan_conj)
-apply(erule disjE)
-apply(drule meta_mp)
-apply (metis empty_iff)
-apply(erule exE)+
-apply(rule exI)
-apply(rule conjI)
-apply(rule Prf.intros)
-apply(erule conjE)+
-apply(assumption)
-apply(rule allI)
-apply(rule impI)+
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(clarify)
-apply(drule meta_mp)
-apply (metis Prf_flat_L empty_iff)
-apply(auto)[1]
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(clarify)
-oops
+*)
 
 section {* Posix definition *}
 
@@ -761,43 +766,6 @@
 apply (metis Prf_Prfs)
 by (metis Prfs_Prf Prfs_flat)
 
-lemma 
-  assumes "POSIX v1 r1" "\<turnstile> v1' : r1"
-  shows "Seq v1 v2 \<succ>(SEQ r1 r2) Seq v1' v2'"
-using assms
-apply(rule_tac ValOrd.intros)
-apply(simp add: POSIX_def)
-oops
-
-lemma
-"L r \<noteq> {} \<Longrightarrow> \<exists>v. POSIXs v r (flat v)"
-apply(induct r arbitrary: )
-apply(simp)
-apply(rule_tac x="Void" in exI)
-apply(simp add: POSIXs_def)
-apply(rule conjI)
-apply (metis Prfs.intros(4))
-apply(auto)[1]
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply (metis ValOrd2.intros(7))
-apply(simp)
-apply(rule_tac x="Char char" in exI)
-apply(simp add: POSIXs_def)
-apply(rule conjI)
-apply (metis Prfs.intros(5))
-apply(auto)[1]
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply (metis ValOrd2.intros)
-apply(auto simp add: Sequ_def)
-apply(drule meta_mp)
-apply (metis empty_iff)
-apply(drule meta_mp)
-apply (metis empty_iff)
-apply(auto)
-oops
-
 section {* POSIX for some constructors *}
 
 lemma POSIX_SEQ1:
@@ -1098,7 +1066,6 @@
 apply metis
 done
 
-
 lemma 
   "\<lbrakk>POSIX (mkeps r2) r2; nullable r2; \<not> nullable r1\<rbrakk>
    \<Longrightarrow> POSIX (Right (mkeps r2)) (ALT r1 r2)" 
@@ -1191,13 +1158,67 @@
   "ders [] r = r"
 | "ders (c # s) r = ders s (der c r)"
 
+fun
+ red :: "char \<Rightarrow> rexp \<Rightarrow> rexp"
+where
+  "red c (NULL) = NULL"
+| "red c (EMPTY) = CHAR c"
+| "red c (CHAR c') = SEQ (CHAR c) (CHAR c')"
+| "red c (ALT r1 r2) = ALT (red c r1) (red c r2)"
+| "red c (SEQ r1 r2) = 
+     (if nullable r1
+      then ALT (SEQ (red c r1) r2) (red c r2)
+      else SEQ (red c r1) r2)"
+
+lemma L_der:
+  shows "L (der c r) = {s. c#s \<in> L r}"
+apply(induct r)
+apply(simp_all)
+apply(simp add: Sequ_def)
+apply(auto)[1]
+apply (metis append_Cons)
+apply (metis append_Nil nullable_correctness)
+apply (metis append_eq_Cons_conv)
+apply (metis append_Cons)
+apply (metis Cons_eq_append_conv nullable_correctness)
+apply(auto)
+done
+
+lemma L_red:
+  shows "L (red c r) = {c#s | s. s \<in> L r}"
+apply(induct r)
+apply(simp_all)
+apply(simp add: Sequ_def)
+apply(simp add: Sequ_def)
+apply(auto)[1]
+apply (metis append_Nil nullable_correctness)
+apply (metis append_Cons)
+apply (metis append_Cons)
+apply(auto)
+done
+
+lemma L_red_der:
+  "L(red c (der c r)) = {c#s | s. c#s \<in> L r}"
+apply(simp add: L_red)
+apply(simp add: L_der)
+done
+
+lemma L_der_red:
+  "L(der c (red c r)) = L r"
+apply(simp add: L_der)
+apply(simp add: L_red)
+done
+
 section {* Injection function *}
 
 fun injval :: "rexp \<Rightarrow> char \<Rightarrow> val \<Rightarrow> val"
 where
-  "injval (CHAR d) c Void = Char d"
+  "injval (EMPTY) c Void = Char c"
+| "injval (CHAR d) c Void = Char d"
+| "injval (CHAR d) c (Char c') = Seq (Char d) (Char c')"
 | "injval (ALT r1 r2) c (Left v1) = Left(injval r1 c v1)"
 | "injval (ALT r1 r2) c (Right v2) = Right(injval r2 c v2)"
+| "injval (SEQ r1 r2) c (Char c') = Seq (Char c) (Char c')"
 | "injval (SEQ r1 r2) c (Seq v1 v2) = Seq (injval r1 c v1) v2"
 | "injval (SEQ r1 r2) c (Left (Seq v1 v2)) = Seq (injval r1 c v1) v2"
 | "injval (SEQ r1 r2) c (Right v2) = Seq (mkeps r1) (injval r2 c v2)"
@@ -1262,6 +1283,31 @@
 apply(auto)[2]
 done
 
+lemma v3_red:
+  assumes "\<turnstile> v : r" shows "\<turnstile> (injval (red c r) c v) : (red c r)"
+using assms
+apply(induct c r arbitrary: v rule: red.induct)
+apply(simp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(simp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis Prf.intros(5))
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis Prf.intros(1) Prf.intros(5))
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis Prf.intros(2))
+apply (metis Prf.intros(3))
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(auto)
+prefer 2
+apply (metis Prf.intros(1))
+oops
+
 lemma v3s:
   assumes "\<Turnstile>s v : der c r" shows "\<Turnstile>(c#s) (injval r c v) : r"
 using assms
@@ -1489,71 +1535,6 @@
 apply(simp_all)[5]
 done
 
-lemma v4_flats:
-  assumes "\<turnstile> v : der c r" "\<not>nullable r" shows "hd (flats (injval r c v)) \<noteq> []"
-using assms
-apply(induct arbitrary: v rule: der.induct)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(case_tac "c = c'")
-apply(simp)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(case_tac "nullable r1")
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-oops
-
-lemma v4_flat_left:
-  assumes "\<turnstile> v : der c r" "\<not>(nullable_left r)" shows "flat_left (injval r c v) = c # (flat_left v)"
-using assms
-apply(induct arbitrary: v rule: der.induct)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(case_tac "c = c'")
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(case_tac "nullable r1")
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all (no_asm_use))[5]
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(simp only: injval.simps)
-apply (metis nullable_left)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-done
-
-
 lemma v4_proj:
   assumes "\<turnstile> v : r" and "\<exists>s. (flat v) = c # s"
   shows "c # flat (projval r c v) = flat v"
@@ -1627,6 +1608,281 @@
 apply(simp_all)[5]
 done
 
+lemma Values_nullable:
+  assumes "nullable r1"
+  shows "mkeps r1 \<in> Values r1 s"
+using assms
+apply(induct r1 arbitrary: s)
+apply(simp_all)
+apply(simp add: Values_recs)
+apply(simp add: Values_recs)
+apply(simp add: Values_recs)
+apply(auto)[1]
+done
+
+lemma Values_injval:
+  assumes "v \<in> Values (der c r) s"
+  shows "injval r c v \<in> Values r (c#s)"
+using assms
+apply(induct c r arbitrary: v s rule: der.induct)
+apply(simp add: Values_recs)
+apply(simp add: Values_recs)
+apply(case_tac "c = c'")
+apply(simp)
+apply(simp add: Values_recs)
+apply(simp add: prefix_def)
+apply(simp)
+apply(simp add: Values_recs)
+apply(simp)
+apply(simp add: Values_recs)
+apply(auto)[1]
+apply(case_tac "nullable r1")
+apply(simp)
+apply(simp add: Values_recs)
+apply(auto)[1]
+apply(simp add: rest_def)
+apply(subst v4)
+apply(simp add: Values_def)
+apply(simp add: Values_def)
+apply(rule Values_nullable)
+apply(assumption)
+apply(simp add: rest_def)
+apply(subst mkeps_flat)
+apply(assumption)
+apply(simp)
+apply(simp)
+apply(simp add: Values_recs)
+apply(auto)[1]
+apply(simp add: rest_def)
+apply(subst v4)
+apply(simp add: Values_def)
+apply(simp add: Values_def)
+done
+
+lemma Values_projval:
+  assumes "v \<in> Values r (c#s)" "\<exists>s. flat v = c # s"
+  shows "projval r c v \<in> Values (der c r) s"
+using assms
+apply(induct r arbitrary: v s c rule: rexp.induct)
+apply(simp add: Values_recs)
+apply(simp add: Values_recs)
+apply(case_tac "c = x")
+apply(simp)
+apply(simp add: Values_recs)
+apply(simp)
+apply(simp add: Values_recs)
+apply(simp add: prefix_def)
+apply(case_tac "nullable x1")
+apply(simp)
+apply(simp add: Values_recs)
+apply(auto)[1]
+apply(simp add: rest_def)
+apply (metis hd_Cons_tl hd_append2 list.sel(1))
+apply(simp add: rest_def)
+apply(simp add: append_eq_Cons_conv)
+apply(auto)[1]
+apply(subst v4_proj2)
+apply(simp add: Values_def)
+apply(assumption)
+apply(simp)
+apply(simp)
+apply(simp add: Values_recs)
+apply(auto)[1]
+apply(auto simp add: Values_def not_nullable_flat)[1]
+apply(simp add: append_eq_Cons_conv)
+apply(auto)[1]
+apply(simp add: append_eq_Cons_conv)
+apply(auto)[1]
+apply(simp add: rest_def)
+apply(subst v4_proj2)
+apply(simp add: Values_def)
+apply(assumption)
+apply(simp)
+apply(simp add: Values_recs)
+apply(auto)[1]
+done
+
+
+definition "MValue v r s \<equiv> (v \<in> Values r s \<and> (\<forall>v' \<in> Values r s. v 2\<succ> v'))"
+
+lemma 
+  assumes "MValue v1 r1 s"
+  shows "MValue (Seq v1 v2) (SEQ r1 r2) s
+
+
+lemma MValue_SEQE:
+  assumes "MValue v (SEQ r1 r2) s"
+  shows "(\<exists>v1 v2. MValue v1 r1 s \<and> MValue v2 r2 (rest v1 s) \<and> v = Seq v1 v2)"
+using assms
+apply(simp add: MValue_def)
+apply(simp add: Values_recs)
+apply(erule conjE)
+apply(erule exE)+
+apply(erule conjE)+
+apply(simp)
+apply(auto)
+apply(drule_tac x="Seq x v2" in spec)
+apply(drule mp)
+apply(rule_tac x="x" in exI)
+apply(rule_tac x="v2" in exI)
+apply(simp)
+oops
+
+
+lemma MValue_ALTE:
+  assumes "MValue v (ALT r1 r2) s"
+  shows "(\<exists>vl. v = Left vl \<and> MValue vl r1 s \<and> (\<forall>vr \<in> Values r2 s. length (flat vr) \<le> length (flat vl))) \<or> 
+         (\<exists>vr. v = Right vr \<and> MValue vr r2 s \<and> (\<forall>vl \<in> Values r1 s. length (flat vl) < length (flat vr)))"
+using assms
+apply(simp add: MValue_def)
+apply(simp add: Values_recs)
+apply(auto)
+apply(drule_tac x="Left x" in bspec)
+apply(simp)
+apply(erule ValOrd2.cases)
+apply(simp_all)
+apply(drule_tac x="Right vr" in bspec)
+apply(simp)
+apply(erule ValOrd2.cases)
+apply(simp_all)
+apply(drule_tac x="Right x" in bspec)
+apply(simp)
+apply(erule ValOrd2.cases)
+apply(simp_all)
+apply(drule_tac x="Left vl" in bspec)
+apply(simp)
+apply(erule ValOrd2.cases)
+apply(simp_all)
+done
+
+lemma MValue_ALTI1:
+  assumes "MValue vl r1 s"  "\<forall>vr \<in> Values r2 s. length (flat vr) \<le> length (flat vl)"
+  shows "MValue (Left vl) (ALT r1 r2) s"
+using assms
+apply(simp add: MValue_def)
+apply(simp add: Values_recs)
+apply(auto)
+apply(rule ValOrd2.intros)
+apply metis
+apply(rule ValOrd2.intros)
+apply metis
+done
+
+lemma MValue_ALTI2:
+  assumes "MValue vr r2 s"  "\<forall>vl \<in> Values r1 s. length (flat vl) < length (flat vr)"
+  shows "MValue (Right vr) (ALT r1 r2) s"
+using assms
+apply(simp add: MValue_def)
+apply(simp add: Values_recs)
+apply(auto)
+apply(rule ValOrd2.intros)
+apply metis
+apply(rule ValOrd2.intros)
+apply metis
+done
+
+lemma MValue_injval:
+  assumes "MValue v (der c r) s"
+  shows "MValue (injval r c v) r (c#s)"
+using assms
+apply(induct c r arbitrary: v s rule: der.induct)
+apply(simp add: MValue_def)
+apply(simp add: Values_recs)
+apply(simp add: MValue_def)
+apply(simp add: Values_recs)
+apply(case_tac "c = c'")
+apply(simp)
+apply(simp add: MValue_def)
+apply(simp add: Values_recs)
+apply(simp add: prefix_def)
+apply(rule ValOrd2.intros)
+apply(simp)
+apply(simp add: MValue_def)
+apply(simp add: Values_recs)
+apply(simp)
+apply(drule MValue_ALTE)
+apply(erule disjE)
+apply(auto)[1]
+apply(rule MValue_ALTI1)
+apply(simp)
+apply(subst v4)
+apply(simp add: MValue_def Values_def)
+apply(rule ballI)
+apply(simp)
+apply(case_tac "flat vr = []")
+apply(simp)
+apply(drule_tac x="projval r2 c vr" in bspec)
+apply(rule Values_projval)
+apply(simp)
+apply(simp add: Values_def prefix_def)
+apply(auto)[1]
+apply(simp add: append_eq_Cons_conv)
+apply(auto)[1]
+apply(simp add: Values_def prefix_def)
+apply(auto)[1]
+apply(simp add: append_eq_Cons_conv)
+apply(auto)[1]
+apply(subst (asm) v4_proj2)
+apply(assumption)
+apply(assumption)
+apply(simp)
+apply(auto)[1]
+apply(rule MValue_ALTI2)
+apply(simp)
+apply(subst v4)
+apply(simp add: MValue_def Values_def)
+apply(rule ballI)
+apply(simp)
+apply(case_tac "flat vl = []")
+apply(simp)
+apply(drule_tac x="projval r1 c vl" in bspec)
+apply(rule Values_projval)
+apply(simp)
+apply(simp add: Values_def prefix_def)
+apply(auto)[1]
+apply(simp add: append_eq_Cons_conv)
+apply(auto)[1]
+apply(simp add: Values_def prefix_def)
+apply(auto)[1]
+apply(simp add: append_eq_Cons_conv)
+apply(auto)[1]
+apply(subst (asm) v4_proj2)
+apply(simp add: MValue_def Values_def)
+apply(assumption)
+apply(assumption)
+apply(case_tac "nullable r1")
+defer
+apply(simp)
+apply(frule MValue_SEQE)
+apply(auto)[1]
+
+
+apply(simp add: MValue_def)
+apply(simp add: Values_recs)
+
+lemma nullable_red:
+  "\<not>nullable (red c r)"
+apply(induct r)
+apply(auto)
+done
+
+lemma twq:
+  assumes "\<turnstile> v : r" 
+  shows "\<turnstile> injval r c v : red c r"
+using assms
+apply(induct)
+apply(auto)
+oops
+
+lemma injval_inj_red: "inj_on (injval (red c r) c) {v. \<turnstile> v : r}"
+using injval_inj
+apply(auto simp add: inj_on_def)
+apply(drule_tac x="red c r" in meta_spec)
+apply(drule_tac x="c" in meta_spec)
+apply(drule_tac x="x" in spec)
+apply(drule mp)
+oops
+
 lemma 
   assumes "POSIXs v (der c r) s" 
   shows "POSIXs (injval r c v) r (c # s)"
@@ -1677,8 +1933,6 @@
 lemma t2: "(xs = ys) \<Longrightarrow> (c#xs) = (c#ys)"
 by (metis)
 
-
-
 lemma "\<not>(nullable r) \<Longrightarrow> \<not>(\<exists>v. \<turnstile> v : r \<and> flat v = [])"
 by (metis Prf_flat_L nullable_correctness)
 
@@ -1771,6 +2025,133 @@
 using assms
 by (metis Prf_flat_L nullable_correctness)
 
+section {* TESTTEST *}
+
+inductive ValOrdA :: "val \<Rightarrow> rexp \<Rightarrow> val \<Rightarrow> bool" ("_ A\<succ>_ _" [100, 100, 100] 100)
+where
+  "v2 A\<succ>r2 v2' \<Longrightarrow> (Seq v1 v2) A\<succ>(SEQ r1 r2) (Seq v1 v2')" 
+| "v1 A\<succ>r1 v1' \<Longrightarrow> (Seq v1 v2) A\<succ>(SEQ r1 r2) (Seq v1' v2')" 
+| "length (flat v1) \<ge> length (flat v2) \<Longrightarrow> (Left v1) A\<succ>(ALT r1 r2) (Right v2)"
+| "length (flat v2) > length (flat v1) \<Longrightarrow> (Right v2) A\<succ>(ALT r1 r2) (Left v1)"
+| "v2 A\<succ>r2 v2' \<Longrightarrow> (Right v2) A\<succ>(ALT r1 r2) (Right v2')"
+| "v1 A\<succ>r1 v1' \<Longrightarrow> (Left v1) A\<succ>(ALT r1 r2) (Left v1')"
+| "Void A\<succ>EMPTY Void"
+| "(Char c) A\<succ>(CHAR c) (Char c)"
+
+inductive ValOrd4 :: "val \<Rightarrow> rexp \<Rightarrow> val \<Rightarrow> bool" ("_ 4\<succ> _ _" [100, 100] 100)
+where
+  (*"v1 4\<succ>(der c r) v1' \<Longrightarrow> (injval r c v1) 4\<succ>r (injval r c v1')" 
+| "\<lbrakk>v1 4\<succ>r v2; v2 4\<succ>r v3\<rbrakk> \<Longrightarrow> v1 4\<succ>r v3" 
+|*) 
+  "\<lbrakk>v1 4\<succ>r1 v1'; flat v2 = flat v2'; \<turnstile> v2 : r2; \<turnstile> v2' : r2\<rbrakk> \<Longrightarrow> (Seq v1 v2) 4\<succ>(SEQ r1 r2)  (Seq v1' v2')"
+| "\<lbrakk>v2 4\<succ>r2 v2'; \<turnstile> v1 : r1\<rbrakk> \<Longrightarrow> (Seq v1 v2) 4\<succ>(SEQ r1 r2)  (Seq v1 v2')"
+| "\<lbrakk>flat v1 = flat v2; \<turnstile> v1 : r1; \<turnstile> v2 : r2\<rbrakk> \<Longrightarrow> (Left v1) 4\<succ>(ALT r1 r2) (Right v2)"
+| "v2 4\<succ>r2 v2' \<Longrightarrow> (Right v2) 4\<succ>(ALT r1 r2) (Right v2')"
+| "v1 4\<succ>r1 v1' \<Longrightarrow> (Left v1) 4\<succ>(ALT r1 r2) (Left v1')"
+| "Void 4\<succ>(EMPTY) Void"
+| "(Char c) 4\<succ>(CHAR c) (Char c)"
+
+lemma ValOrd4_Prf:
+  assumes "v1 4\<succ>r v2"
+  shows "\<turnstile> v1 : r \<and> \<turnstile> v2 : r"
+using assms
+apply(induct v1 r v2)
+apply(auto intro: Prf.intros)
+done
+
+lemma ValOrd4_flat:
+  assumes "v1 4\<succ>r v2"
+  shows "flat v1 = flat v2"
+using assms
+apply(induct v1 r v2)
+apply(simp_all)
+done
+
+lemma ValOrd4_refl:
+  assumes "\<turnstile> v : r"
+  shows "v 4\<succ>r v"
+using assms
+apply(induct v r)
+apply(auto intro: ValOrd4.intros)
+done
+
+lemma 
+  assumes "v1 4\<succ>r v2" "v2 4\<succ>r v3" 
+  shows "v1 A\<succ>r v3"
+using assms
+apply(induct v1 r v2 arbitrary: v3)
+apply(rotate_tac 5)
+apply(erule ValOrd4.cases)
+apply(simp_all)
+apply(clarify)
+apply (metis ValOrdA.intros(2))
+apply(clarify)
+apply (metis ValOrd4_refl ValOrdA.intros(2))
+apply(rotate_tac 3)
+apply(erule ValOrd4.cases)
+apply(simp_all)
+apply(clarify)
+
+apply (metis ValOrdA.intros(2))
+apply (metis ValOrdA.intros(1))
+apply (metis ValOrdA.intros(3) order_refl)
+apply (auto intro: ValOrdA.intros)
+done
+
+lemma 
+  assumes "v1 4\<succ>r v2"
+  shows "v1 A\<succ>r v2"
+using assms
+apply(induct v1 r v2 arbitrary:)
+apply (metis ValOrdA.intros(2))
+apply (metis ValOrdA.intros(1))
+apply (metis ValOrdA.intros(3) order_refl)
+apply (auto intro: ValOrdA.intros)
+done
+
+lemma 
+  assumes "v1 \<succ>r v2" "\<turnstile> v1 : r" "\<turnstile> v2 : r" "flat v1 = flat v2"
+  shows "v1 4\<succ>r v2"
+using assms
+apply(induct v1 r v2 arbitrary:)
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(clarify)
+apply (metis ValOrd4.intros(4) ValOrd4_flat ValOrd4_refl)
+apply(simp)
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(clarify)
+
+lemma 
+  assumes "v1 \<succ>r v2" "\<turnstile> v1 : r" "\<turnstile> v2 : r" "flat v1 = flat v2"
+  shows "v1 4\<succ>r v2"
+using assms
+apply(induct v1 r v2 arbitrary:)
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(clarify)
+apply (metis ValOrd4.intros(4) ValOrd4_flat ValOrd4_refl)
+apply(simp)
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(erule Prf.cases)
+apply(simp_all (no_asm_use))[5]
+apply(clarify)
+
+
+apply(simp)
+apply(erule Prf.cases)
+
+
+
+
 lemma rr2: "hd (flats v) \<noteq> [] \<Longrightarrow> flats v \<noteq> []"
 apply(induct v)
 apply(auto)
@@ -1798,637 +2179,433 @@
 apply(drule v3s_proj)
 oops
 
+term Values
+(* HERE *)
+
 lemma Prf_inj_test:
-  assumes "v1 2\<succ> v2" "\<turnstile> v1 : der c r" "\<turnstile> v2 : der c r" 
-  "length (flat v1) = length (flat v2)"
+  assumes "v1 \<succ>(der c r) v2" 
+          "v1 \<in> Values (der c r) s"
+          "v2 \<in> Values (der c r) s"
+          "injval r c v1 \<in> Values r (c#s)"
+          "injval r c v2 \<in> Values r (c#s)"
   shows "(injval r c v1) 2\<succ>  (injval r c v2)"
 using assms
-apply(induct c r arbitrary: v1 v2 rule: der.induct)
+apply(induct c r arbitrary: v1 v2 s rule: der.induct)
 (* NULL case *)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply(simp add: Values_recs)
 (* EMPTY case *)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply(simp add: Values_recs)
 (* CHAR case *)
 apply(case_tac "c = c'")
 apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(rule ValOrd2.intros)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply(simp add: Values_recs)
+apply (metis ValOrd2.intros(8))
+apply(simp add: Values_recs)
 (* ALT case *)
 apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[2]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[2]
-apply(erule ValOrd2.cases)
+apply(simp add: Values_recs)
+apply(auto)[1]
+apply(erule ValOrd.cases)
 apply(simp_all)[8]
-apply(rule ValOrd2.intros)
-apply(auto)[1]
-apply(erule ValOrd2.cases)
+apply (metis ValOrd2.intros(6))
+apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(rule ValOrd2.intros)
 apply(subst v4)
-apply metis
+apply(simp add: Values_def)
 apply(subst v4)
-apply (metis)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[2]
-apply(erule ValOrd2.cases)
+apply(simp add: Values_def)
+apply(simp)
+apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(rule ValOrd2.intros)
-apply(erule ValOrd2.cases)
+apply(subst v4)
+apply(simp add: Values_def)
+apply(subst v4)
+apply(simp add: Values_def)
+apply(simp)
+apply(erule ValOrd.cases)
 apply(simp_all)[8]
+apply (metis ValOrd2.intros(5))
 (* SEQ case*)
 apply(simp)
 apply(case_tac "nullable r1")
 apply(simp)
 defer
 apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule ValOrd2.cases)
+apply(simp add: Values_recs)
+apply(auto)[1]
+apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
 apply(rule ValOrd2.intros)
 apply(simp)
-apply(rule ValOrd2.intros)
-apply(auto)[1]
-
-using injval_inj
-apply(simp add: inj_on_def)
-apply metis
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(clarify)
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(clarify)
-apply (metis ValOrd2.intros(1))
-apply(rule ValOrd2.intros)
-apply metis
-using injval_inj
-apply(simp add: inj_on_def)
-apply metis
-apply(clarify)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply (metis Ord1)
 apply(clarify)
 apply(rule ValOrd2.intros)
-apply(rule Ord1)
-apply(rule h)
-apply(simp)
-apply(simp)
-apply (metis list.distinct(1) mkeps_flat v4)
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(rotate_tac 7)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-defer
-apply(clarify)
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(clarify)
-apply (metis ValOrd2.intros(1))
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(clarify)
-apply(simp)
-apply (rule_tac ValOrd2.intros(2))
-prefer 2
-apply (metis list.distinct(1) mkeps_flat v4)
-
-
-lemma Prf_inj_test:
-  assumes "v1 2\<succ> v2" "\<Turnstile>s1 v1 : der c r" "\<Turnstile>s2 v2 : der c r"  
-  shows "(injval r c v1) 2\<succ>  (injval r c v2)"
-using assms
-apply(induct c r arbitrary: s1 s2 v1 v2 rule: der.induct)
-(* NULL case *)
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-(* EMPTY case *)
-apply(simp)
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-(* CHAR case *)
-apply(case_tac "c = c'")
-apply(simp)
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(rule ValOrd2.intros)
-apply(simp)
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-(* ALT case *)
-apply(simp)
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(auto)[2]
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(auto)[2]
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(rule ValOrd2.intros)
-apply(auto)[1]
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(rule ValOrd2.intros)
-apply(subst v4)
-apply (metis Prfs_Prf)
-apply(subst v4)
-apply (metis Prfs_Prf)
-apply(simp)
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(auto)[2]
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(rule ValOrd2.intros)
-apply(subst v4)
-apply (metis Prfs_Prf)
-apply(subst v4)
-apply (metis Prfs_Prf)
-apply(simp)
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(rule ValOrd2.intros)
-apply metis
-(* SEQ case*)
-apply(simp)
-apply(case_tac "nullable r1")
-apply(simp)
-defer
-apply(simp)
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(clarify)
-apply(rule ValOrd2.intros)
-apply(simp)
-apply(rule ValOrd2.intros)
-apply(auto)[1]
-defer
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(clarify)
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(clarify)
-apply (metis ValOrd2.intros(1))
-apply(rule ValOrd2.intros)
-apply metis
-defer
-apply(clarify)
-apply(simp)
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(rule ValOrd2.intros)
-apply(rule Ord1)
-apply(rule h)
-apply(simp)
-apply(simp)
-apply (metis Prfs_Prf)
-defer
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(rotate_tac 6)
-apply(erule Prfs.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(clarify)
+apply(subgoal_tac "rest v1 (flat v1 @ flat v2) = flat v2")
+apply(simp)
+apply(subgoal_tac "rest (injval r1 c v1) (c # flat v1 @ flat v2) = flat v2")
 apply(simp)
 
-apply(erule ValOrd2.cases)
-apply(simp_all)[8]
-apply(simp)
 apply metis
 using injval_inj
-apply(simp add: inj_on_def)
+apply(simp add: Values_def inj_on_def)
 apply metis
-(* SEQ nullable case *)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
+apply(simp add: Values_recs)
+apply(auto)[1]
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
-apply(rule ValOrd.intros(1))
-apply(simp)
-apply(rule ValOrd.intros(2))
+apply (metis Ord1 ValOrd2.intros(1))
+apply(clarify)
+apply(rule ValOrd2.intros(2))
 apply metis
 using injval_inj
-apply(simp add: inj_on_def)
+apply(simp add: Values_def inj_on_def)
 apply metis
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(rule ValOrd2.intros(2))
+thm h
+apply(rule Ord1)
+apply(rule h)
+apply(simp)
+apply(simp add: Values_def)
+apply(simp add: Values_def)
+apply (metis list.distinct(1) mkeps_flat v4)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
 apply(clarify)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
+apply(simp add: Values_def)
+defer
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
-apply(simp)
-apply(rule ValOrd.intros(2))
-apply (metis h)
-apply (metis list.distinct(1) mkeps_flat v4)
-(* last case *)
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(rotate_tac 6)
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply(rule ValOrd2.intros(1))
+apply(rotate_tac 1)
+apply(drule_tac x="v2" in meta_spec)
+apply(rotate_tac 8)
+apply(drule_tac x="v2'" in meta_spec)
+apply(rotate_tac 8)
+apply(drule_tac x="s" in meta_spec)
+apply(simp)
+apply(drule_tac meta_mp)
+apply(simp add: rest_def mkeps_flat)
+apply(drule_tac meta_mp)
+apply(simp add: rest_def mkeps_flat)
+apply(simp)
+apply(simp add: rest_def mkeps_flat)
+apply(subst (asm) (5) v4)
+apply(simp)
+apply(subst (asm) (5) v4)
+apply(simp)
+apply(subst (asm) (5) v4)
+apply(simp)
+apply(simp)
 apply(clarify)
+apply(simp add: prefix_Cons)
+apply(subgoal_tac "((flat v1c) @ (flat v2b)) \<sqsubseteq> (flat v2)")
 prefer 2
-apply(clarify)
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(clarify)
-apply(rule ValOrd.intros(1))
-apply(metis)
-apply(rule ValOrd.intros(2))
-prefer 2
-thm mkeps_flat v4
-apply (metis list.distinct(1) mkeps_flat v4)
-oops
+apply(simp add: prefix_def)
+apply(auto)[1]
+(* HEREHERE *)
 
 
 lemma Prf_inj_test:
-  assumes "v1 \<succ>(der c r) v2" "\<turnstile> v1 : der c r" "\<turnstile> v2 : der c r"  
-          "flat v1 = flat v2"
-  shows "(injval r c v1) \<succ>r  (injval r c v2)"
+  assumes "v1 \<succ>r v2" 
+          "v1 \<in> Values r s"
+          "v2 \<in> Values r s"
+          "injval r c v1 \<in> Values (red c r) (c#s)"
+          "injval r c v2 \<in> Values (red c r) (c#s)"
+  shows "(injval r c v1) \<succ>(red c r)  (injval r c v2)"
 using assms
-apply(induct v1 arbitrary: r v2 taking: "length o flat" rule: measure_induct_rule)
-apply(case_tac r)
-(* NULL case *)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply(induct v1 r v2 arbitrary: s rule: ValOrd.induct)
+apply(simp add: Values_recs)
+apply (metis ValOrd.intros(1))
+apply(simp add: Values_recs)
+apply(rule ValOrd.intros(2))
+apply(metis)
+defer
+apply(simp add: Values_recs)
+apply(rule ValOrd.intros)
+apply(subst v4)
+apply(simp add: Values_def)
+apply(subst v4)
+apply(simp add: Values_def)
+using injval_inj_red
+apply(simp add: Values_def inj_on_def)
+apply(rule notI)
+apply(drule_tac x="r1" in meta_spec)
+apply(drule_tac x="c" in meta_spec)
+apply(drule_tac x="injval r1 c v1" in spec)
+apply(simp)
+
+apply(drule_tac x="c" in meta_spec)
+
+apply metis
+apply (metis ValOrd.intros(1))
+
+
+
+done
 (* EMPTY case *)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply(simp add: Values_recs)
 (* CHAR case *)
-apply(case_tac "c = char")
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros(8))
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply(case_tac "c = c'")
+apply(simp)
+apply(simp add: Values_recs)
+apply (metis ValOrd2.intros(8))
+apply(simp add: Values_recs)
 (* ALT case *)
-prefer 2
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
+apply(simp)
+apply(simp add: Values_recs)
+apply(auto)[1]
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
-apply(clarify)
-apply (rule ValOrd.intros(6))
-apply(drule_tac x="v1b" in meta_spec)
-apply(drule_tac x="rexp1" in meta_spec)
-apply(drule_tac x="v1'" in meta_spec)
-apply(drule_tac meta_mp)
-apply(assumption)
-apply(drule_tac meta_mp)
-apply(assumption)
-apply(drule_tac meta_mp)
-
-apply(clarify)
+apply (metis ValOrd2.intros(6))
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(rule ValOrd2.intros)
+apply(subst v4)
+apply(simp add: Values_def)
+apply(subst v4)
+apply(simp add: Values_def)
+apply(simp)
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
-apply(clarify)
-apply (metis ValOrd.intros(3) monoid_add_class.add.right_neutral order_refl v4)
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply (metis RightLeft der.simps(4) injval.simps(2) injval.simps(3))
-apply(clarify)
+apply(rule ValOrd2.intros)
+apply(subst v4)
+apply(simp add: Values_def)
+apply(subst v4)
+apply(simp add: Values_def)
+apply(simp)
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
-apply(clarify)
-apply (metis ValOrd.intros(5))
-(* SEQ case *)
+apply (metis ValOrd2.intros(5))
+(* SEQ case*)
 apply(simp)
 apply(case_tac "nullable r1")
 apply(simp)
 defer
 apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
+apply(simp add: Values_recs)
+apply(auto)[1]
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
-apply(rule ValOrd.intros)
-apply(simp)
+apply(rule ValOrd2.intros)
+apply(simp)
+apply (metis Ord1)
 apply(clarify)
-apply(rule ValOrd.intros(2))
-apply(rotate_tac 2)
-apply(drule_tac x="v1c" in meta_spec)
-apply(rotate_tac 9)
-apply(drule_tac x="v1'" in meta_spec)
-apply(drule_tac meta_mp)
-apply(assumption)
-apply(drule_tac meta_mp)
-apply(assumption)
-apply(drule_tac meta_mp)
-apply(assumption)
-apply(drule_tac meta_mp)
-apply(simp)
-apply (metis POSIX_SEQ1)
-apply(simp)
-apply (metis proj_inj_id)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(rotate_tac 6)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
+apply(rule ValOrd2.intros)
+apply metis
+using injval_inj
+apply(simp add: Values_def inj_on_def)
+apply metis
+apply(simp add: Values_recs)
+apply(auto)[1]
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
-apply(rule ValOrd.intros(1))
-apply(simp)
-apply(clarify)
-apply (metis POSIX_ALT2 POSIX_SEQ1 ValOrd.intros(2) proj_inj_id)
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply (metis Ord1 ValOrd2.intros(1))
 apply(clarify)
-apply (metis Prf.intros(1) Prf.intros(2) ValOrd.intros(2) der.simps(5) h injval.simps(5) mkeps_flat proj_inj_id projval.simps(4) val.distinct(19))
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(rotate_tac 7)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
+apply(rule ValOrd2.intros(2))
+apply metis
+using injval_inj
+apply(simp add: Values_def inj_on_def)
+apply metis
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(rule ValOrd2.intros(2))
+thm h
+apply(rule Ord1)
+apply(rule h)
+apply(simp)
+apply(simp add: Values_def)
+apply(simp add: Values_def)
+apply (metis list.distinct(1) mkeps_flat v4)
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
-apply(simp)
-apply(drule POSIX_ALT1a)
-apply(rule ValOrd.intros(2))
+apply(simp add: Values_def)
 defer
-apply (metis list.distinct(1) mkeps_flat v4)
-apply(rule ValOrd.intros(1))
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply (metis POSIX_ALT1a)
-
-apply(clarify)
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
-apply(rule ValOrd.intros(1))
-apply(simp)
-
-apply(subgoal_tac "flats v1c \<noteq> []")
+apply(rule ValOrd2.intros(1))
+apply(rotate_tac 1)
+apply(drule_tac x="v2" in meta_spec)
+apply(rotate_tac 8)
+apply(drule_tac x="v2'" in meta_spec)
+apply(rotate_tac 8)
+apply(drule_tac x="s" in meta_spec)
+apply(simp)
+apply(drule_tac meta_mp)
+apply(simp add: rest_def mkeps_flat)
+apply(drule_tac meta_mp)
+apply(simp add: rest_def mkeps_flat)
+apply(simp)
+apply(simp add: rest_def mkeps_flat)
+apply(subst (asm) (5) v4)
+apply(simp)
+apply(subst (asm) (5) v4)
+apply(simp)
+apply(subst (asm) (5) v4)
+apply(simp)
+apply(simp)
+apply(clarify)
+apply(simp add: prefix_Cons)
+apply(subgoal_tac "((flat v1c) @ (flat v2b)) \<sqsubseteq> (flat v2)")
+prefer 2
+apply(simp add: prefix_def)
+apply(auto)[1]
+(* HEREHERE *)
 
-apply(simp)
-apply(subst v4)
-apply(simp)
-apply(subst (asm) v4)
-apply(simp)
-apply(simp)
-apply(simp add: prefix_def)
-oops
-
-lemma Prf_inj:
-  assumes "v1 \<succ>(der c r) v2" "\<turnstile> v1 : der c r" "\<turnstile> v2 : der c r" (*"flat v1 = flat v2"*)
-  shows "(injval r c v1) \<succ>r (injval r c v2)"
+lemma Prf_inj_test:
+  assumes "v1 \<succ>(der c r) v2" 
+          "v1 \<in> Values (der c r) s"
+          "v2 \<in> Values (der c r) s"
+          "injval r c v1 \<in> Values r (c#s)"
+          "injval r c v2 \<in> Values r (c#s)"
+  shows "(injval r c v1) 2\<succ>  (injval r c v2)"
 using assms
-apply(induct c r arbitrary: v1 v2 rule: der.induct)
+apply(induct c r arbitrary: v1 v2 s rule: der.induct)
 (* NULL case *)
-apply(simp)
+apply(simp add: Values_recs)
+(* EMPTY case *)
+apply(simp add: Values_recs)
+(* CHAR case *)
+apply(case_tac "c = c'")
+apply(simp)
+apply(simp add: Values_recs)
+apply (metis ValOrd2.intros(8))
+apply(simp add: Values_recs)
+(* ALT case *)
+apply(simp)
+apply(simp add: Values_recs)
+apply(auto)[1]
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
-(* EMPTY case *)
-apply(simp)
+apply (metis ValOrd2.intros(6))
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
-(* CHAR case *)
-apply(case_tac "c = c'")
-apply(simp)
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(rule ValOrd.intros)
+apply(rule ValOrd2.intros)
+apply(subst v4)
+apply(simp add: Values_def)
+apply(subst v4)
+apply(simp add: Values_def)
 apply(simp)
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
-(* ALT case *)
+apply(rule ValOrd2.intros)
+apply(subst v4)
+apply(simp add: Values_def)
+apply(subst v4)
+apply(simp add: Values_def)
 apply(simp)
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
-apply(rule ValOrd.intros)
-apply(subst v4)
-apply(clarify)
-apply(rotate_tac 3)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(subst v4)
-apply(clarify)
-apply(rotate_tac 2)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(rule ValOrd.intros)
-apply(clarify)
-apply(rotate_tac 3)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(subst v4)
-apply(simp)
-apply(subst v4)
-apply(simp)
-apply(simp)
-apply(rule ValOrd.intros)
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(rule ValOrd.intros)
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply (metis ValOrd2.intros(5))
 (* SEQ case*)
 apply(simp)
 apply(case_tac "nullable r1")
 apply(simp)
 defer
 apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
+apply(simp add: Values_recs)
+apply(auto)[1]
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
-apply(rule ValOrd.intros)
-apply(simp)
+apply(rule ValOrd2.intros)
+apply(simp)
+apply (metis Ord1)
 apply(clarify)
-apply(rule ValOrd.intros(2))
+apply(rule ValOrd2.intros)
 apply metis
 using injval_inj
-apply(simp add: inj_on_def)
+apply(simp add: Values_def inj_on_def)
 apply metis
-(* SEQ nullable case *)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
+apply(simp add: Values_recs)
+apply(auto)[1]
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
-apply(rule ValOrd.intros(1))
-apply(simp)
-apply(rule ValOrd.intros(2))
+apply (metis Ord1 ValOrd2.intros(1))
+apply(clarify)
+apply(rule ValOrd2.intros(2))
 apply metis
 using injval_inj
-apply(simp add: inj_on_def)
+apply(simp add: Values_def inj_on_def)
 apply metis
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(rule ValOrd2.intros(2))
+thm h
+apply(rule Ord1)
+apply(rule h)
+apply(simp)
+apply(simp add: Values_def)
+apply(simp add: Values_def)
+apply (metis list.distinct(1) mkeps_flat v4)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
 apply(clarify)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
+apply(simp add: Values_def)
+defer
 apply(erule ValOrd.cases)
 apply(simp_all)[8]
 apply(clarify)
-apply(simp)
-apply(rule ValOrd.intros(2))
-apply (metis h)
-apply (metis list.distinct(1) mkeps_flat v4)
-(* last case *)
-apply(clarify)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(rotate_tac 6)
-apply(erule Prf.cases)
-apply(simp_all)[5]
+apply(rule ValOrd2.intros(1))
+apply(rotate_tac 1)
+apply(drule_tac x="v2" in meta_spec)
+apply(rotate_tac 8)
+apply(drule_tac x="v2'" in meta_spec)
+apply(rotate_tac 8)
+apply(drule_tac x="s" in meta_spec)
+apply(simp)
+apply(drule_tac meta_mp)
+apply(simp add: rest_def mkeps_flat)
+apply(drule_tac meta_mp)
+apply(simp add: rest_def mkeps_flat)
+apply(simp)
+apply(simp add: rest_def mkeps_flat)
+apply(subst (asm) (5) v4)
+apply(simp)
+apply(subst (asm) (5) v4)
+apply(simp)
+apply(subst (asm) (5) v4)
+apply(simp)
+apply(simp)
 apply(clarify)
+apply(simp add: prefix_Cons)
+apply(subgoal_tac "((flat v1c) @ (flat v2b)) \<sqsubseteq> (flat v2)")
 prefer 2
-apply(clarify)
-apply(erule ValOrd.cases)
-apply(simp_all)[8]
-apply(clarify)
-apply(rule ValOrd.intros(1))
-apply(metis)
-apply(rule ValOrd.intros(2))
-prefer 2
-thm mkeps_flat v4
-apply (metis list.distinct(1) mkeps_flat v4)
-oops
+apply(simp add: prefix_def)
+apply(auto)[1]
+(* HEREHERE *)
+
+apply(subst (asm) (7) v4)
+apply(simp)
 
 
+(* HEREHERE *)
+
+apply(simp add: Values_def)
+apply(simp add: Values_recs)
+apply(simp add: Values_recs)
+done
+
 lemma POSIX_der:
   assumes "POSIX v (der c r)" "\<turnstile> v : der c r"
   shows "POSIX (injval r c v) r"
@@ -2457,6 +2634,8 @@
 apply(rule_tac x="flat v" in exI)
 apply(simp)
 apply(simp)
+thm  Prf_inj_test
+apply(drule_tac r="r" in Prf_inj_test)
 oops
 
 lemma POSIX_der: