--- a/thys/#Re1.thy#	Wed Feb 11 11:22:53 2015 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,897 +0,0 @@
-
-theory Re1
-  imports "Main" 
-begin
-
-section {* Sequential Composition of Sets *}
-
-definition
-  Sequ :: "string set \<Rightarrow> string set \<Rightarrow> string set" ("_ ;; _" [100,100] 100)
-where 
-  "A ;; B = {s1 @ s2 | s1 s2. s1 \<in> A \<and> s2 \<in> B}"
-
-text {* Two Simple Properties about Sequential Composition *}
-
-lemma seq_empty [simp]:
-  shows "A ;; {[]} = A"
-  and   "{[]} ;; A = A"
-by (simp_all add: Sequ_def)
-
-lemma seq_null [simp]:
-  shows "A ;; {} = {}"
-  and   "{} ;; A = {}"
-by (simp_all add: Sequ_def)
-
-section {* Regular Expressions *}
-
-datatype rexp =
-  NULL
-| EMPTY
-| CHAR char
-| SEQ rexp rexp
-| ALT rexp rexp
-
-section {* Semantics of Regular Expressions *}
- 
-fun
-  L :: "rexp \<Rightarrow> string set"
-where
-  "L (NULL) = {}"
-| "L (EMPTY) = {[]}"
-| "L (CHAR c) = {[c]}"
-| "L (SEQ r1 r2) = (L r1) ;; (L r2)"
-| "L (ALT r1 r2) = (L r1) \<union> (L r2)"
-
-value "L(CHAR c)"
-value "L(SEQ(CHAR c)(CHAR b))"
-
-
-section {* Values *}
-
-datatype val = 
-  Void
-| Char char
-| Seq val val
-| Right val
-| Left val
-
-section {* Relation between values and regular expressions *}
-
-inductive Prf :: "val \<Rightarrow> rexp \<Rightarrow> bool" ("\<turnstile> _ : _" [100, 100] 100)
-where
- "\<lbrakk>\<turnstile> v1 : r1; \<turnstile> v2 : r2\<rbrakk> \<Longrightarrow> \<turnstile> Seq v1 v2 : SEQ r1 r2"
-| "\<turnstile> v1 : r1 \<Longrightarrow> \<turnstile> Left v1 : ALT r1 r2"
-| "\<turnstile> v2 : r2 \<Longrightarrow> \<turnstile> Right v2 : ALT r1 r2"
-| "\<turnstile> Void : EMPTY"
-| "\<turnstile> Char c : CHAR c"
-
-section {* The string behind a value *}
-
-fun flat :: "val \<Rightarrow> string"
-where
-  "flat(Void) = []"
-| "flat(Char c) = [c]"
-| "flat(Left v) = flat(v)"
-| "flat(Right v) = flat(v)"
-| "flat(Seq v1 v2) = flat(v1) @ flat(v2)"
-
-value "flat(Seq(Char c)(Char b))"
-value "flat(Right(Void))"
-
-fun flats :: "val \<Rightarrow> string list"
-where
-  "flats(Void) = [[]]"
-| "flats(Char c) = [[c]]"
-| "flats(Left v) = flats(v)"
-| "flats(Right v) = flats(v)"
-| "flats(Seq v1 v2) = (flats v1) @ (flats v2)"
-
-value "flats(Seq(Char c)(Char b))"
-
-lemma Prf_flat_L:
-  assumes "\<turnstile> v : r" shows "flat v \<in> L r"
-using assms
-apply(induct)
-apply(auto simp add: Sequ_def)
-done
-
-lemma L_flat_Prf:
-  "L(r) = {flat v | v. \<turnstile> v : r}"
-apply(induct r)
-apply(auto dest: Prf_flat_L simp add: Sequ_def)
-apply (metis Prf.intros(4) flat.simps(1))
-apply (metis Prf.intros(5) flat.simps(2))
-apply (metis Prf.intros(1) flat.simps(5))
-apply (metis Prf.intros(2) flat.simps(3))
-apply (metis Prf.intros(3) flat.simps(4))
-apply(erule Prf.cases)
-apply(auto)
-done
-
-definition definition prefix :: :: "string \<Rightarrow> string \<Rightarrow> bool" ("_ \<sqsubset> _" [100, 100] 100)
-where
-  "s1 \<sqsubset> s2 \<equiv> \<exists>s3. s1 @ s3 = s2"
-
-section {* Ordering of values *}
-
-inductive ValOrd :: "val \<Rightarrow> rexp \<Rightarrow> val \<Rightarrow> bool" ("_ \<succ>_ _" [100, 100, 100] 100)
-where
-  "\<lbrakk>v1 = v1'; v2 \<succ>r2 v2'\<rbrakk> \<Longrightarrow> (Seq v1 v2) \<succ>(SEQ r1 r2) (Seq v1' v2')" 
-| "v1  \<succ>r1 v1' \<Longrightarrow> (Seq v1 v2) \<succ>(SEQ r1 r2) (Seq v1' v2')" 
-| "length (flat v1) \<ge> length (flat v2) \<Longrightarrow> (Left v1) \<succ>(ALT r1 r2) (Right v2)"
-| "length (flat v2) > length (flat v1) \<Longrightarrow> (Right v2) \<succ>(ALT r1 r2) (Left v1)"
-| "v2 \<succ>r2 v2' \<Longrightarrow> (Right v2) \<succ>(ALT r1 r2) (Right v2')"
-| "v1 \<succ>r1 v1' \<Longrightarrow> (Left v1) \<succ>(ALT r1 r2) (Left v1')"
-| "Void \<succ>EMPTY Void"
-| "(Char c) \<succ>(CHAR c) (Char c)"
-
-section {* The ordering is reflexive *}
-
-lemma ValOrd_refl:
-  assumes "\<turnstile> v : r"
-  shows "v \<succ>r v"
-using assms
-apply(induct)
-apply(auto intro: ValOrd.intros)
-done
-
-lemma ValOrd_flats:
-  assumes "v1 \<succ>r v2"
-  shows "hd (flats v2) = hd (flats v1)"
-using assms
-apply(induct)
-apply(auto)
-oops
-
-
-section {* Posix definition *}
-
-definition POSIX :: "val \<Rightarrow> rexp \<Rightarrow> bool" 
-where
-  "POSIX v r \<equiv> (\<forall>v'. (\<turnstile> v' : r \<and> flat v = flat v') \<longrightarrow> v \<succ>r v')"
-
-(*
-an alternative definition: might cause problems
-with theorem mkeps_POSIX
-*)
-
-definition POSIX2 :: "val \<Rightarrow> rexp \<Rightarrow> bool" 
-where
-  "POSIX2 v r \<equiv> \<turnstile> v : r \<and> (\<forall>v'. \<turnstile> v' : r \<longrightarrow> v \<succ>r v')"
-
-definition POSIX3 :: "val \<Rightarrow> rexp \<Rightarrow> bool" 
-where
-  "POSIX3 v r \<equiv> \<turnstile> v : r \<and> (\<forall>v'. (\<turnstile> v' : r \<and> length (flat v') \<le> length(flat v)) \<longrightarrow> v \<succ>r v')"
-
-
-lemma POSIX_SEQ:
-  assumes "POSIX (Seq v1 v2) (SEQ r1 r2)" "\<turnstile> v1 : r1" "\<turnstile> v2 : r2"
-  shows "POSIX v1 r1 \<and> POSIX v2 r2"
-using assms
-unfolding POSIX_def
-apply(auto)
-apply(drule_tac x="Seq v' v2" in spec)
-apply(simp)
-apply(erule impE)
-apply(rule Prf.intros)
-apply(simp)
-apply(simp)
-apply(erule ValOrd.cases)
-apply(simp_all)
-apply(clarify)
-defer
-apply(drule_tac x="Seq v1 v'" in spec)
-apply(simp)
-apply(erule impE)
-apply(rule Prf.intros)
-apply(simp)
-apply(simp)
-apply(erule ValOrd.cases)
-apply(simp_all)
-apply(clarify)
-oops (*not true*)
-
-lemma POSIX_SEQ_I:
-  assumes "POSIX v1 r1" "POSIX v2 r2" 
-  shows "POSIX (Seq v1 v2) (SEQ r1 r2)" 
-using assms
-unfolding POSIX_def
-apply(auto)
-apply(rotate_tac 2)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[1]
-apply(rule ValOrd.intros)
-oops (* maybe also not true *)
-
-lemma POSIX3_SEQ_I:
-  assumes "POSIX3 v1 r1" "POSIX3 v2 r2" 
-  shows "POSIX3 (Seq v1 v2) (SEQ r1 r2)" 
-using assms
-unfolding POSIX3_def
-apply(auto)
-apply (metis Prf.intros(1))
-apply(rotate_tac 4)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[1]
-apply(case_tac "v1 = v1a")
-apply(auto)
-apply (metis ValOrd.intros(1))
-apply (rule ValOrd.intros(2))
-oops
-
-lemma POSIX_ALT2:
-  assumes "POSIX (Left v1) (ALT r1 r2)"
-  shows "POSIX v1 r1"
-using assms
-unfolding POSIX_def
-apply(auto)
-apply(drule_tac x="Left v'" in spec)
-apply(simp)
-apply(drule mp)
-apply(rule Prf.intros)
-apply(auto)
-apply(erule ValOrd.cases)
-apply(simp_all)
-done
-
-lemma POSIX2_ALT:
-  assumes "POSIX2 (Left v1) (ALT r1 r2)"
-  shows "POSIX2 v1 r1"
-using assms
-unfolding POSIX2_def
-apply(auto)
-oops
-
-lemma POSIX_ALT:
-  assumes "POSIX (Left v1) (ALT r1 r2)"
-  shows "POSIX v1 r1"
-using assms
-unfolding POSIX_def
-apply(auto)
-apply(drule_tac x="Left v'" in spec)
-apply(simp)
-apply(drule mp)
-apply(rule Prf.intros)
-apply(auto)
-apply(erule ValOrd.cases)
-apply(simp_all)
-done
-
-lemma POSIX2_ALT:
-  assumes "POSIX2 (Left v1) (ALT r1 r2)"
-  shows "POSIX2 v1 r1"
-using assms
-apply(simp add: POSIX2_def)
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(drule_tac x="Left v'" in spec)
-apply(drule mp)
-apply(rule Prf.intros)
-apply(auto)
-apply(erule ValOrd.cases)
-apply(simp_all)
-done
-
-
-lemma POSIX_ALT1a:
-  assumes "POSIX (Right v2) (ALT r1 r2)"
-  shows "POSIX v2 r2"
-using assms
-unfolding POSIX_def
-apply(auto)
-apply(drule_tac x="Right v'" in spec)
-apply(simp)
-apply(drule mp)
-apply(rule Prf.intros)
-apply(auto)
-apply(erule ValOrd.cases)
-apply(simp_all)
-done
-
-lemma POSIX2_ALT1a:
-  assumes "POSIX2 (Right v2) (ALT r1 r2)"
-  shows "POSIX2 v2 r2"
-using assms
-unfolding POSIX2_def
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(drule_tac x="Right v'" in spec)
-apply(drule mp)
-apply(rule Prf.intros)
-apply(auto)
-apply(erule ValOrd.cases)
-apply(simp_all)
-done
-
-
-lemma POSIX_ALT1b:
-  assumes "POSIX (Right v2) (ALT r1 r2)"
-  shows "(\<forall>v'. (\<turnstile> v' : r2 \<and> flat v' = flat v2) \<longrightarrow> v2 \<succ>r2 v')"
-using assms
-apply(drule_tac POSIX_ALT1a)
-unfolding POSIX_def
-apply(auto)
-done
-
-lemma POSIX_ALT_I1:
-  assumes "POSIX v1 r1" 
-  shows "POSIX (Left v1) (ALT r1 r2)"
-using assms
-unfolding POSIX_def
-apply(auto)
-apply(rotate_tac 3)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply(rule ValOrd.intros)
-apply(auto)
-apply(rule ValOrd.intros)
-by simp
-
-lemma POSIX2_ALT_I1:
-  assumes "POSIX2 v1 r1" 
-  shows "POSIX2 (Left v1) (ALT r1 r2)"
-using assms
-unfolding POSIX2_def
-apply(auto)
-apply(rule Prf.intros)
-apply(simp)
-apply(rotate_tac 2)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply(rule ValOrd.intros)
-apply(auto)
-apply(rule ValOrd.intros)
-oops
-
-lemma POSIX_ALT_I2:
-  assumes "POSIX v2 r2" "\<forall>v'. \<turnstile> v' : r1 \<longrightarrow> length (flat v2) > length (flat v')"
-  shows "POSIX (Right v2) (ALT r1 r2)"
-using assms
-unfolding POSIX_def
-apply(auto)
-apply(rotate_tac 3)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply(rule ValOrd.intros)
-apply metis
-done
-
-
-
-
-
-section {* The Matcher *}
-
-fun
- nullable :: "rexp \<Rightarrow> bool"
-where
-  "nullable (NULL) = False"
-| "nullable (EMPTY) = True"
-| "nullable (CHAR c) = False"
-| "nullable (ALT r1 r2) = (nullable r1 \<or> nullable r2)"
-| "nullable (SEQ r1 r2) = (nullable r1 \<and> nullable r2)"
-
-lemma nullable_correctness:
-  shows "nullable r  \<longleftrightarrow> [] \<in> (L r)"
-apply (induct r) 
-apply(auto simp add: Sequ_def) 
-done
-
-fun mkeps :: "rexp \<Rightarrow> val"
-where
-  "mkeps(EMPTY) = Void"
-| "mkeps(SEQ r1 r2) = Seq (mkeps r1) (mkeps r2)"
-| "mkeps(ALT r1 r2) = (if nullable(r1) then Left (mkeps r1) else Right (mkeps r2))"
-
-lemma mkeps_nullable:
-  assumes "nullable(r)" shows "\<turnstile> mkeps r : r"
-using assms
-apply(induct rule: nullable.induct)
-apply(auto intro: Prf.intros)
-done
-
-lemma mkeps_flat:
-  assumes "nullable(r)" shows "flat (mkeps r) = []"
-using assms
-apply(induct rule: nullable.induct)
-apply(auto)
-done
-
-text {*
-  The value mkeps returns is always the correct POSIX
-  value.
-*}
-
-lemma mkeps_POSIX2:
-  assumes "nullable r"
-  shows "POSIX2 (mkeps r) r"
-using assms
-apply(induct r)
-apply(auto)[1]
-apply(simp add: POSIX2_def)
-oops
-
-lemma mkeps_POSIX3:
-  assumes "nullable r"
-  shows "POSIX3 (mkeps r) r"
-using assms
-apply(induct r)
-apply(auto)[1]
-apply(simp add: POSIX3_def)
-apply(auto)[1]
-apply (metis Prf.intros(4))
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros)
-apply(simp add: POSIX3_def)
-apply(auto)[1]
-apply(simp add: POSIX3_def)
-apply(auto)[1]
-apply (metis mkeps.simps(2) mkeps_nullable nullable.simps(5))
-apply(rotate_tac 6)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros(2) add_leE gen_length_code(1) gen_length_def mkeps_flat)
-apply(auto)
-apply(simp add: POSIX3_def)
-apply(auto)
-apply (metis Prf.intros(2))
-apply(rotate_tac 4)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros(6))
-apply(auto)[1]
-apply (metis ValOrd.intros(3))
-apply(simp add: POSIX3_def)
-apply(auto)
-apply (metis Prf.intros(2))
-apply(rotate_tac 6)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros(6))
-apply (metis ValOrd.intros(3))
-apply(simp add: POSIX3_def)
-apply(auto)
-apply (metis Prf.intros(3))
-apply(rotate_tac 5)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis Prf_flat_L drop_0 drop_all list.size(3) mkeps_flat nullable_correctness)
-by (metis ValOrd.intros(5))
-
-
-lemma mkeps_POSIX:
-  assumes "nullable r"
-  shows "POSIX (mkeps r) r"
-using assms
-apply(induct r)
-apply(auto)[1]
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros)
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (simp add: ValOrd.intros(2) mkeps_flat)
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (simp add: ValOrd.intros(6))
-apply (simp add: ValOrd.intros(3))
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (simp add: ValOrd.intros(6))
-apply (simp add: ValOrd.intros(3))
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)
-apply (metis Prf_flat_L mkeps_flat nullable_correctness)
-by (simp add: ValOrd.intros(5))
-
-
-lemma mkeps_POSIX2:
-  assumes "nullable r"
-  shows "POSIX2 (mkeps r) r"
-using assms
-apply(induct r)
-apply(simp)
-apply(simp)
-apply(simp add: POSIX2_def)
-apply(rule conjI)
-apply(rule Prf.intros)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(rule ValOrd.intros)
-apply(simp)
-apply(simp)
-apply(simp add: POSIX2_def)
-apply(rule conjI)
-apply(rule Prf.intros)
-apply(simp add: mkeps_nullable)
-apply(simp add: mkeps_nullable)
-apply(auto)[1]
-apply(rotate_tac 6)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(rule ValOrd.intros(2))
-apply(simp)
-apply(simp only: nullable.simps)
-apply(erule disjE)
-apply(simp)
-thm POSIX2_ALT1a
-apply(rule POSIX2_ALT)
-apply(simp add: POSIX2_def)
-apply(rule conjI)
-apply(rule Prf.intros)
-apply(simp add: mkeps_nullable)
-oops
-
-
-section {* Derivatives *}
-
-fun
- der :: "char \<Rightarrow> rexp \<Rightarrow> rexp"
-where
-  "der c (NULL) = NULL"
-| "der c (EMPTY) = NULL"
-| "der c (CHAR c') = (if c = c' then EMPTY else NULL)"
-| "der c (ALT r1 r2) = ALT (der c r1) (der c r2)"
-| "der c (SEQ r1 r2) = 
-     (if nullable r1
-      then ALT (SEQ (der c r1) r2) (der c r2)
-      else SEQ (der c r1) r2)"
-
-fun 
- ders :: "string \<Rightarrow> rexp \<Rightarrow> rexp"
-where
-  "ders [] r = r"
-| "ders (c # s) r = ders s (der c r)"
-
-section {* Injection function *}
-
-fun injval :: "rexp \<Rightarrow> char \<Rightarrow> val \<Rightarrow> val"
-where
-  "injval (CHAR d) c Void = Char d"
-| "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 (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)"
-
-section {* Projection function *}
-
-fun projval :: "rexp \<Rightarrow> char \<Rightarrow> val \<Rightarrow> val"
-where
-  "projval (CHAR d) c _ = Void"
-| "projval (ALT r1 r2) c (Left v1) = Left(projval r1 c v1)"
-| "projval (ALT r1 r2) c (Right v2) = Right(projval r2 c v2)"
-| "projval (SEQ r1 r2) c (Seq v1 v2) = 
-     (if flat v1 = [] then Right(projval r2 c v2) 
-      else if nullable r1 then Left (Seq (projval r1 c v1) v2)
-                          else Seq (projval r1 c v1) v2)"
-
-text {*
-  Injection value is related to r
-*}
-
-lemma v3:
-  assumes "\<turnstile> v : der c r" shows "\<turnstile> (injval r c v) : r"
-using assms
-apply(induct arbitrary: v rule: der.induct)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(case_tac "c = c'")
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis Prf.intros(5))
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis Prf.intros(2))
-apply (metis Prf.intros(3))
-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(auto)[1]
-apply (metis Prf.intros(1))
-apply(auto)[1]
-apply (metis Prf.intros(1) mkeps_nullable)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[1]
-apply(rule Prf.intros)
-apply(auto)[2]
-done
-
-text {*
-  The string behin the injection value is an added c
-*}
-
-lemma v4:
-  assumes "\<turnstile> v : der c r" shows "flat (injval r c v) = c # (flat v)"
-using assms
-apply(induct arbitrary: v rule: der.induct)
-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 "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(auto)[1]
-apply (metis mkeps_flat)
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-done
-
-text {*
-  Injection followed by projection is the identity.
-*}
-
-lemma proj_inj_id:
-  assumes "\<turnstile> v : der c r" 
-  shows "projval r c (injval r c v) = v"
-using assms
-apply(induct r arbitrary: c v rule: rexp.induct)
-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 "c = char")
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-defer
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(simp)
-apply(case_tac "nullable rexp1")
-apply(simp)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[1]
-apply (metis list.distinct(1) v4)
-apply(auto)[1]
-apply (metis mkeps_flat)
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(auto)[1]
-apply(simp add: v4)
-done
-
-lemma "L r \<noteq> {} \<Longrightarrow> \<exists>v. POSIX3 v r"
-apply(induct r)
-apply(simp)
-apply(simp add: POSIX3_def)
-apply(rule_tac x="Void" in exI)
-apply(auto)[1]
-apply (metis Prf.intros(4))
-apply (metis POSIX3_def flat.simps(1) mkeps.simps(1) mkeps_POSIX3 nullable.simps(2) order_refl)
-apply(simp add: POSIX3_def)
-apply(rule_tac x="Char char" in exI)
-apply(auto)[1]
-apply (metis Prf.intros(5))
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply (metis ValOrd.intros(8))
-apply(simp add: Sequ_def)
-apply(auto)[1]
-apply(drule meta_mp)
-apply(auto)[2]
-apply(drule meta_mp)
-apply(auto)[2]
-apply(rule_tac x="Seq v va" in exI)
-apply(simp (no_asm) add: POSIX3_def)
-apply(auto)[1]
-apply (metis POSIX3_def Prf.intros(1))
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(clarify)
-apply(case_tac "v  \<succ>r1a v1")
-apply(rule ValOrd.intros(2))
-apply(simp)
-apply(case_tac "v = v1")
-apply(rule ValOrd.intros(1))
-apply(simp)
-apply(simp)
-apply (metis ValOrd_refl)
-apply(simp add: POSIX3_def)
-
-
-lemma "\<exists>v. POSIX v r"
-apply(induct r)
-apply(rule exI)
-apply(simp add: POSIX_def)
-apply (metis (full_types) Prf_flat_L der.simps(1) der.simps(2) der.simps(3) flat.simps(1) nullable.simps(1) nullable_correctness proj_inj_id projval.simps(1) v3 v4)
-apply(rule_tac x = "Void" in exI)
-apply(simp add: POSIX_def)
-apply (metis POSIX_def flat.simps(1) mkeps.simps(1) mkeps_POSIX nullable.simps(2))
-apply(rule_tac x = "Char char" in exI)
-apply(simp add: POSIX_def)
-apply(auto) [1]
-apply(erule Prf.cases)
-apply(simp_all) [5]
-apply (metis ValOrd.intros(8))
-defer
-apply(auto)
-apply (metis POSIX_ALT_I1)
-(* maybe it is too early to instantiate this existential quantifier *)
-(* potentially this is the wrong POSIX value *)
-apply(case_tac "r1 = NULL")
-apply(simp add: POSIX_def)
-apply(auto)[1]
-apply (metis L.simps(1) L.simps(4) Prf_flat_L mkeps_flat nullable.simps(1) nullable.simps(2) nullable_correctness seq_null(2))
-apply(case_tac "r1 = EMPTY")
-apply(rule_tac x = "Seq Void va" in exI )
-apply(simp (no_asm) add: POSIX_def)
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)
-apply(rule ValOrd.intros(2))
-apply(rule ValOrd.intros)
-apply(case_tac "\<exists>c. r1 = CHAR c")
-apply(auto)
-apply(rule_tac x = "Seq (Char c) va" in exI )
-apply(simp (no_asm) add: POSIX_def)
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)
-apply(auto)[1]
-apply(erule Prf.cases)
-apply(simp_all)
-apply(auto)[1]
-apply(rule ValOrd.intros(2))
-apply(rule ValOrd.intros)
-apply(case_tac "\<exists>r1a r1b. r1 = ALT r1a r1b")
-apply(auto)
-oops (* not sure if this can be proved by induction *)
-
-text {* 
-
-  HERE: Crucial lemma that does not go through in the sequence case. 
-
-*}
-lemma v5:
-  assumes "\<turnstile> v : der c r" "POSIX v (der c r)"
-  shows "POSIX (injval r c v) r"
-using assms
-apply(induct arbitrary: v rule: der.induct)
-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 "c = c'")
-apply(auto simp add: POSIX_def)[1]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-apply(erule Prf.cases)
-apply(simp_all)[5]
-using ValOrd.simps apply blast
-apply(auto)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-(* base cases done *)
-(* ALT case *)
-apply(erule Prf.cases)
-apply(simp_all)[5]
-using POSIX_ALT POSIX_ALT_I1 apply blast
-apply(clarify)
-apply(subgoal_tac "POSIX v2 (der c r2)")
-prefer 2
-apply(auto simp add: POSIX_def)[1]
-apply (metis POSIX_ALT1a POSIX_def flat.simps(4))
-apply(frule POSIX_ALT1a)
-apply(drule POSIX_ALT1b)
-apply(rule POSIX_ALT_I2)
-apply(rotate_tac 1)
-apply(drule_tac x="v2" in meta_spec)
-apply(simp)
-apply(subgoal_tac "\<turnstile> Right (injval r2 c v2) : (ALT r1 r2)")
-prefer 2
-apply (metis Prf.intros(3) v3)
-
-apply auto[1]
-apply(subst v4)
-apply(auto)[2]
-apply(subst (asm) (4) POSIX_def)
-apply(subst (asm) v4)
-apply(drule_tac x="v2" in meta_spec)
-apply(simp)
-
-apply(auto)[2]
-
-thm POSIX_ALT_I2
-apply(rule POSIX_ALT_I2)
-
-apply(rule ccontr)
-apply(auto simp add: POSIX_def)[1]
-
-apply(rule allI)
-apply(rule impI)
-apply(erule conjE)
-thm POSIX_ALT_I2
-apply(frule POSIX_ALT1a)
-apply(drule POSIX_ALT1b)
-apply(rule POSIX_ALT_I2)
-apply auto[1]
-apply(subst v4)
-apply(auto)[2]
-apply(rotate_tac 1)
-apply(drule_tac x="v2" in meta_spec)
-apply(simp)
-apply(subst (asm) (4) POSIX_def)
-apply(subst (asm) v4)
-apply(auto)[2]
-(* stuck in the ALT case *)