# HG changeset patch
# User fahad
# Date 1424954515 0
# Node ID d86d685273ceba29999e1240effaea959b0043f8
# Parent  eb97e8361211a5dd363716f8641120f566d42c7d# Parent  26b71a36f55f5f7840bcf22c7a44ac9639969992
merged

diff -r 26b71a36f55f -r d86d685273ce progs/scala/re.scala
--- a/progs/scala/re.scala	Mon Feb 09 00:46:25 2015 +0000
+++ b/progs/scala/re.scala	Thu Feb 26 12:41:55 2015 +0000
@@ -43,6 +43,27 @@
   def $ (r: Rexp) = RECD(s, r)
 }
 
+def pretty(r: Rexp) : String = r match {
+  case NULL => "0"
+  case EMPTY => "e"
+  case CHAR(c) => c.toString 
+  case ALT(r1, r2) => "(" ++ pretty(r1) ++ " | " + pretty(r2) ++ ")"
+  case SEQ(r1, r2) => pretty(r1) ++ pretty(r2)
+  case STAR(r) => "(" ++ pretty(r) ++ ")*"
+  case RECD(x, r) => "(" ++ x ++ " : " ++ pretty(r) ++ ")"
+}
+
+def vpretty(v: Val) : String = v match {
+  case Void => "()"
+  case Chr(c) => c.toString
+  case Left(v) => "Left(" ++ vpretty(v) ++ ")"
+  case Right(v) => "Right(" ++ vpretty(v) ++ ")"
+  case Sequ(v1, v2) => vpretty(v1) ++ " ~ " ++ vpretty(v2)
+  case Stars(vs) => vs.flatMap(vpretty).mkString("[", ",", "]")
+  case Rec(x, v) => "(" ++ x ++ ":" ++ vpretty(v) ++ ")"
+}
+
+
 // size of a regular expressions - for testing purposes 
 def size(r: Rexp) : Int = r match {
   case NULL => 1
@@ -59,7 +80,8 @@
   case NULL => Set()
   case EMPTY => Set(Void)
   case CHAR(c) => Set(Chr(c))
-  case ALT(r1, r2) => values(r1) ++ values(r2)
+  case ALT(r1, r2) => (for (v1 <- values(r1)) yield Left(v1)) ++ 
+                      (for (v2 <- values(r2)) yield Right(v2))
   case SEQ(r1, r2) => for (v1 <- values(r1); v2 <- values(r2)) yield Sequ(v1, v2)
   case STAR(r) => Set(Void) ++ values(r)   // to do more would cause the set to be infinite
   case RECD(_, r) => values(r)
@@ -271,6 +293,29 @@
 println(values(r2).mkString("\n"))
 println(values(r2).toList.map(flatten).mkString("\n"))
 
+//Some experiments
+//================
+
+val f0 = ("ab" | "b" | "cb")
+val f1 = der('a', f0)
+val f2 = der('b', f1)
+val g2 = mkeps(f2)
+val g1 = inj(f1, 'b', g2)
+val g0 = inj(f0, 'a', g1)
+
+lex((("" | "a") ~ ("ab" | "b")), "ab".toList)
+lex((("" | "a") ~ ("b" | "ab")), "ab".toList)
+lex((("" | "a") ~ ("c" | "ab")), "ab".toList)
+
+val reg0 = ("" | "a") ~ ("ab" | "b")
+val reg1 = der('a', reg0)
+val reg2 = der('b', reg1)
+println(List(reg0, reg1, reg2).map(pretty).mkString("\n"))
+println(lexing(reg0, "ab"))
+
+val val0 = values(reg0)
+val val1 = values(reg1)
+val val2 = values(reg2)
 
 
 // Two Simple Tests
diff -r 26b71a36f55f -r d86d685273ce thys/#Re1.thy#
--- a/thys/#Re1.thy#	Mon Feb 09 00:46:25 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 *)
diff -r 26b71a36f55f -r d86d685273ce thys/Chap03.thy
--- a/thys/Chap03.thy	Mon Feb 09 00:46:25 2015 +0000
+++ b/thys/Chap03.thy	Thu Feb 26 12:41:55 2015 +0000
@@ -1,8 +1,77 @@
-(* test *)
 theory Chap03
 imports Main
 begin
 
+(* 2.5.6 Case Study: Boolean Expressions *)
+
+datatype boolex = Const bool | Var nat | Neg boolex
+| And boolex boolex
+
+primrec "value2" :: "boolex \<Rightarrow> (nat \<Rightarrow> bool) \<Rightarrow> bool" where
+"value2 (Const b)  env = b" |
+"value2 (Var x)    env = env x" |
+"value2 (Neg b)    env = (\<not> value2 b env)" |
+"value2 (And b c)  env = (value2 b env \<and> value2 c env)"
+
+value "Const true"
+value "Var (Suc(0))"
+value "value2 (Const False) (\<lambda>x. False)"
+value "value2 (Var 11) (\<lambda>x. if (x = 10 | x = 11) then True else False)"
+value "value2 (Var 11) (\<lambda>x. True )"
+
+definition
+  "en1 \<equiv>  (\<lambda>x. if x = 10 | x = 11 then True else False)"
+  
+abbreviation
+  "en2 \<equiv>  (\<lambda>x. if x = 10 | x = 11 then True else False)"
+  
+value "value2 (And (Var 10) (Var 11)) en2"
+
+lemma "value2 (And (Var 10) (Var 11)) en2 = True"
+apply(simp)
+done
+
+datatype ifex = 
+  CIF bool 
+| VIF nat 
+| IF ifex ifex ifex
+
+primrec valif :: "ifex \<Rightarrow> (nat \<Rightarrow> bool) \<Rightarrow> bool" where
+"valif (CIF b)    env = b" |
+"valif (VIF x)    env = env x" |
+"valif (IF b t e) env = (if valif b env then valif t env else valif e env)"
+
+abbreviation "vif1 \<equiv> valif (CIF False) (\<lambda>x. False)"
+abbreviation "vif2 \<equiv> valif (VIF 11) (\<lambda>x. False)"
+abbreviation "vif3 \<equiv> valif (VIF 13) (\<lambda>x. True)"
+
+value "valif (CIF False) (\<lambda>x. False)"
+value "valif (VIF 11) (\<lambda>x. True)"
+value "valif (IF (CIF False) (CIF True) (CIF True))"
+
+primrec bool2if :: "boolex \<Rightarrow> ifex" where
+"bool2if (Const b)  = CIF b" |
+"bool2if (Var x)    = VIF x" |
+"bool2if (Neg b)    = IF (bool2if b) (CIF False) (CIF True)" |
+"bool2if (And b c)  = IF (bool2if b) (bool2if c) (CIF False)"
+
+lemma "valif (bool2if b) env = value2 b env"
+apply(induct_tac b)
+apply(auto)
+done
+
+primrec normif :: "ifex \<Rightarrow> ifex \<Rightarrow> ifex \<Rightarrow> ifex" where
+"normif (CIF b)     t e = IF (CIF b) t e" |
+"normif (VIF x)     t e = IF (VIF x) t e" |
+"normif (IF b t e)  u f = normif b (normif t u f) (normif e u f)"
+
+primrec norm :: "ifex \<Rightarrow> ifex" where
+"norm (CIF b)     = CIF b" |
+"norm (VIF x)     = VIF x" |
+"norm (IF b t e)  = normif b (norm t) (norm e)"  
+
+(***************   CHAPTER-3   ********************************)
+
 lemma "\<lbrakk> xs @ zs = ys @ xs; [] @ xs = [] @ [] \<rbrakk> \<Longrightarrow> ys = zs"
 apply simp
 done
@@ -125,7 +194,9 @@
 apply(simp add: abc3)
 done
 
-(* added test *)
+find_theorems "_ \<and> _ "
+
+(* added anottest *)
 
 lemma abc5: "add2 m n = m + n"
 apply(induction n)
@@ -147,6 +218,8 @@
 "value (Vex a) env = env a" |
 "value (Bex f e1 e2) env = f (value e1 env) (value e2 env)"
 
+value "value (Cex a) (\<lambda>x. True)"
+
 datatype ('a,'v)instr = 
   Const 'v
 | Load 'a
@@ -182,34 +255,41 @@
 apply(simp split: instr.split)
 done
 
-(* 2.5.6 Case Study: Boolean Expressions *)
-
-datatype boolex = Const bool | Var nat | Neg boolex
-| And boolex boolex
+(* 3.4 Advanced Datatypes  *)
 
-primrec "value2" :: "boolex \<Rightarrow> (nat \<Rightarrow> bool) \<Rightarrow> bool" where
-"value2 (Const b)  env = b" |
-"value2 (Var x)    env = env x" |
-"value2 (Neg b)    env = (\<not> value2 b env)" |
-"value2 (And b c)  env = (value2 b env \<and> value2 c env)"
+datatype 'a aexp = IF "'a bexp" "'a aexp" "'a aexp" 
+                | Sum "'a aexp" "'a aexp"
+                | Diff "'a aexp" "'a aexp"
+                | Var 'a
+                | Num nat
+and      'a bexp = Less "'a aexp" "'a aexp"
+                | And "'a bexp" "'a bexp"
+                | Neg "'a bexp"
+                
+(*  Total Recursive Functions: Fun  *)
+(*  3.5.1 Definition    *)
 
-value "Const true"
-value "Var (Suc(0))"
-
-
+fun fib :: "nat \<Rightarrow> nat" where
+"fib 0 = 0" |
+"fib (Suc 0) = 1" |
+"fib (Suc(Suc x)) = fib x + fib (Suc x)"
 
-value "value2 (Const False) (\<lambda>x. False)"
-value "value2 (Var 11) (\<lambda>x. if (x = 10 | x = 11) then True else False)"
+value "fib (Suc(Suc(Suc(Suc(Suc 0)))))"
+
+fun sep :: "'a \<Rightarrow> 'a list \<Rightarrow> 'a list" where
+"sep a [] = []" |
+"sep a [x] = [x]" |
+"sep a (x#y#zs) = x # a # sep a (y#zs)"
 
-definition
-  "en1 \<equiv>  (\<lambda>x. if x = 10 | x = 11 then True else False)"
-  
-abbreviation
-  "en2 \<equiv>  (\<lambda>x. if x = 10 | x = 11 then True else False)"
-  
-value "value2 (And (Var 10) (Var 11)) en2"
+fun last :: "'a list \<Rightarrow> 'a" where
+"last [x] = x" |
+"last (_#y#zs) = last (y#zs)"
 
-lemma "value2 (And (Var 10) (Var 11)) en2 = True"
-apply(simp)
-done
+fun sep1 :: "'a \<Rightarrow> 'a list \<Rightarrow> 'a list" where
+"sep1 a (x#y#zs) = x # a # sep1 a (y#zs)" |
+"sep1 _ xs = xs"
 
+fun swap12:: "'a list \<Rightarrow> 'a list" where
+"swap12 (x#y#zs) = y#x#zs" |
+"swap12 zs = zs"
+
diff -r 26b71a36f55f -r d86d685273ce thys/Re1.thy
--- a/thys/Re1.thy	Mon Feb 09 00:46:25 2015 +0000
+++ b/thys/Re1.thy	Thu Feb 26 12:41:55 2015 +0000
@@ -42,6 +42,20 @@
 | "L (SEQ r1 r2) = (L r1) ;; (L r2)"
 | "L (ALT r1 r2) = (L r1) \<union> (L r2)"
 
+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
 
 section {* Values *}
 
@@ -52,6 +66,33 @@
 | Right val
 | Left val
 
+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)"
+
+fun head :: "val \<Rightarrow> string"
+where
+  "head(Void) = []"
+| "head(Char c) = [c]"
+| "head(Left v) = head(v)"
+| "head(Right v) = head(v)"
+| "head(Seq v1 v2) = head v1"
+
+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)"
+
+
 section {* Relation between values and regular expressions *}
 
 inductive Prf :: "val \<Rightarrow> rexp \<Rightarrow> bool" ("\<turnstile> _ : _" [100, 100] 100)
@@ -62,23 +103,32 @@
 | "\<turnstile> Void : EMPTY"
 | "\<turnstile> Char c : CHAR c"
 
-section {* The string behind a value *}
-
-fun flat :: "val \<Rightarrow> string"
+fun mkeps :: "rexp \<Rightarrow> val"
 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)"
+  "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
+
 
-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)"
+
+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 Prf_flat_L:
   assumes "\<turnstile> v : r" shows "flat v \<in> L r"
@@ -108,8 +158,8 @@
 
 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')" 
+  "v2 \<succ>r2 v2' \<Longrightarrow> (Seq v1 v2) \<succ>(SEQ r1 r2) (Seq v1 v2')" 
+| "\<lbrakk>v1 \<succ>r1 v1'; v1 \<noteq> v1'\<rbrakk> \<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')"
@@ -128,38 +178,32 @@
 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')"
+  "POSIX v r \<equiv> (\<turnstile> v : r \<and> (\<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:
+lemma POSIX_SEQ1:
   assumes "POSIX (Seq v1 v2) (SEQ r1 r2)" "\<turnstile> v1 : r1" "\<turnstile> v2 : r2"
-  shows "POSIX v1 r1 \<and> POSIX v2 r2"
+  shows "POSIX v1 r1"
 using assms
 unfolding POSIX_def
 apply(auto)
@@ -172,7 +216,14 @@
 apply(erule ValOrd.cases)
 apply(simp_all)
 apply(clarify)
-defer
+by (metis ValOrd_refl)
+
+lemma POSIX_SEQ2:
+  assumes "POSIX (Seq v1 v2) (SEQ r1 r2)" "\<turnstile> v1 : r1" "\<turnstile> v2 : r2" 
+  shows "POSIX v2 r2"
+using assms
+unfolding POSIX_def
+apply(auto)
 apply(drule_tac x="Seq v1 v'" in spec)
 apply(simp)
 apply(erule impE)
@@ -181,38 +232,7 @@
 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
+done
 
 lemma POSIX_ALT2:
   assumes "POSIX (Left v1) (ALT r1 r2)"
@@ -220,6 +240,8 @@
 using assms
 unfolding POSIX_def
 apply(auto)
+apply(erule Prf.cases)
+apply(simp_all)[5]
 apply(drule_tac x="Left v'" in spec)
 apply(simp)
 apply(drule mp)
@@ -229,52 +251,14 @@
 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(erule Prf.cases)
+apply(simp_all)[5]
 apply(drule_tac x="Right v'" in spec)
 apply(simp)
 apply(drule mp)
@@ -284,23 +268,6 @@
 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')"
@@ -316,7 +283,8 @@
 using assms
 unfolding POSIX_def
 apply(auto)
-apply(rotate_tac 3)
+apply (metis Prf.intros(2))
+apply(rotate_tac 2)
 apply(erule Prf.cases)
 apply(simp_all)[5]
 apply(auto)
@@ -325,22 +293,6 @@
 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')"
@@ -348,6 +300,7 @@
 using assms
 unfolding POSIX_def
 apply(auto)
+apply (metis Prf.intros)
 apply(rotate_tac 3)
 apply(erule Prf.cases)
 apply(simp_all)[5]
@@ -356,108 +309,6 @@
 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"
@@ -466,77 +317,42 @@
 apply(auto)[1]
 apply(simp add: POSIX_def)
 apply(auto)[1]
+apply (metis Prf.intros(4))
 apply(erule Prf.cases)
 apply(simp_all)[5]
 apply (metis ValOrd.intros)
-apply(simp add: POSIX_def)
+apply(simp)
 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 (metis mkeps.simps(2) mkeps_nullable nullable.simps(5))
 apply(rotate_tac 6)
 apply(erule Prf.cases)
 apply(simp_all)[5]
-apply(rule ValOrd.intros(2))
+apply (simp add: mkeps_flat)
+apply(case_tac "mkeps r1a = v1")
 apply(simp)
-apply(simp only: nullable.simps)
+apply (metis ValOrd.intros(1))
+apply (rule ValOrd.intros(2))
+apply metis
+apply(simp)
+apply(simp)
 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
+apply (metis POSIX_ALT_I1)
+apply(auto)
+apply (metis POSIX_ALT_I1)
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply (metis Prf.intros(3))
+apply(rotate_tac 5)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(simp add: mkeps_flat)
+apply(auto)[1]
+apply (metis Prf_flat_L nullable_correctness)
+apply(rule ValOrd.intros)
+by metis
 
 
 section {* Derivatives *}
@@ -570,6 +386,7 @@
 | "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"
@@ -721,11 +538,170 @@
 using assms
 by (metis list.inject v4_proj)
 
+lemma injval_inj: "inj_on (injval r c) {v. \<turnstile> v : der c r}"
+apply(induct c r rule: der.induct)
+unfolding inj_on_def
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(auto)[1]
+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(auto)[1]
+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(auto)[1]
+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 Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply (metis list.distinct(1) mkeps_flat v4)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(rotate_tac 6)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis list.distinct(1) mkeps_flat v4)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+done
+
 lemma t: "(c#xs = c#ys) \<Longrightarrow> xs = ys"
 by (metis list.sel(3))
 
+lemma t2: "(xs = ys) \<Longrightarrow> (c#xs) = (c#ys)"
+by (metis)
+
+fun zeroable where
+  "zeroable NULL = True"
+| "zeroable EMPTY = False"
+| "zeroable (CHAR c) = False"
+| "zeroable (ALT r1 r2) = (zeroable r1 \<and> zeroable r2)"
+| "zeroable (SEQ r1 r2) = (zeroable r1 \<or> zeroable r2)"
+
+lemma "\<not>(nullable r) \<Longrightarrow> \<not>(\<exists>v. \<turnstile> v : r \<and> flat v = [])"
+by (metis Prf_flat_L nullable_correctness)
+
+lemma proj_inj_id:
+  assumes "\<turnstile> v : der c r" 
+  shows "projval r c (injval r c v) = v"
+using assms
+apply(induct c r 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(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 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 
+ assumes "\<turnstile> v : der c r" "flat v \<noteq> []"
+ shows "injval r c v \<succ>r mkeps r"
+using assms
+apply(induct c r arbitrary: v rule: der.induct)
+apply(simp_all)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+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(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply (metis ValOrd.intros(6))
+apply(clarify)
+apply (metis ValOrd.intros(4) drop_0 drop_all le_add2 list.distinct(1) list.size(3) mkeps_flat monoid_add_class.add.right_neutral nat_less_le v4)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(rule ValOrd.intros)
+apply(simp)
+defer
+apply(rule ValOrd.intros)
+apply metis
+apply(case_tac "nullable r1")
+apply(simp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+defer
+apply(clarify)
+apply(rule ValOrd.intros)
+apply metis
+apply(simp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+defer
+apply(subst mkeps_flat)
+oops
+*)
+
 lemma Prf_inj:
-  assumes "v1 \<succ>(der c r) v2" "\<turnstile> v1 : der c r" "\<turnstile> v2 : der c r"
+  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)"
 using assms
 apply(induct arbitrary: v1 v2 rule: der.induct)
@@ -762,6 +738,656 @@
 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]
+(* 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 ValOrd.cases)
+apply(simp_all)[8]
+apply(clarify)
+apply(rule ValOrd.intros)
+apply(simp)
+apply(clarify)
+apply(rule ValOrd.intros(2))
+apply metis
+using injval_inj
+apply(simp add: 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(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
+using injval_inj
+apply(simp add: inj_on_def)
+apply metis
+apply(clarify)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(clarify)
+apply(simp)
+apply(rule ValOrd.intros(2))
+prefer 2
+apply (metis list.distinct(1) mkeps_flat v4)
+defer
+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(clarify)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(clarify)
+apply(simp)
+apply(rule ValOrd.intros(2))
+prefer 2
+apply (metis list.distinct(1) mkeps_flat v4)
+defer
+apply(clarify)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(clarify)
+apply(rule ValOrd.intros(1))
+apply(metis)
+apply(drule_tac x="v1" in meta_spec)
+apply(rotate_tac 7)
+apply(drule_tac x="projval r1 c (mkeps r1)" in meta_spec)
+apply(drule meta_mp)
+
+defer
+apply(erule ValOrd.cases)
+apply(simp_all del: injval.simps)[8]
+apply(simp)
+apply(clarify)
+apply(simp)
+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(clarify)
+apply(rule ValOrd.intros(2))
+
+
+lemma POSIX_ex: "\<turnstile> v : r \<Longrightarrow> \<exists>v. POSIX v r"
+apply(induct r arbitrary: v)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rule_tac x="Void" in exI)
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply (metis Prf.intros(4))
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis ValOrd.intros(7))
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rule_tac x="Char c" in exI)
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply (metis Prf.intros(5))
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis ValOrd.intros(8))
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(auto)[1]
+apply(drule_tac x="v1" in meta_spec)
+apply(drule_tac x="v2" in meta_spec)
+apply(auto)[1]
+defer
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(auto)[1]
+apply (metis POSIX_ALT_I1)
+apply (metis POSIX_ALT_I1 POSIX_ALT_I2)
+apply(case_tac "nullable r1a")
+apply(rule_tac x="Seq (mkeps r1a) va" in exI)
+apply(auto simp add: POSIX_def)[1]
+apply (metis Prf.intros(1) mkeps_nullable)
+apply(simp add: mkeps_flat)
+apply(rotate_tac 7)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(case_tac "mkeps r1 = v1a")
+apply(simp)
+apply (rule ValOrd.intros(1))
+apply (metis append_Nil mkeps_flat)
+apply (rule ValOrd.intros(2))
+apply(drule mkeps_POSIX)
+apply(simp add: POSIX_def)
+
+apply metis
+apply(simp)
+apply(simp)
+apply(erule disjE)
+apply(simp)
+
+apply(drule_tac x="v2" in spec)
+
+lemma POSIX_ex2: "\<turnstile> v : r \<Longrightarrow> \<exists>v. POSIX v r \<and> \<turnstile> v : r"
+apply(induct r arbitrary: v)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rule_tac x="Void" in exI)
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis ValOrd.intros(7))
+apply (metis Prf.intros(4))
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rule_tac x="Char c" in exI)
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis ValOrd.intros(8))
+apply (metis Prf.intros(5))
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(auto)[1]
+apply(drule_tac x="v1" in meta_spec)
+apply(drule_tac x="v2" in meta_spec)
+apply(auto)[1]
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply(rule ccontr)
+apply(simp)
+apply(drule_tac x="Seq v va" in spec)
+apply(drule mp)
+defer
+apply (metis Prf.intros(1))
+
+
+oops
+
+lemma POSIX_ALT_cases:
+  assumes "\<turnstile> v : (ALT r1 r2)" "POSIX v (ALT r1 r2)"
+  shows "(\<exists>v1. v = Left v1 \<and> POSIX v1 r1) \<or> (\<exists>v2. v = Right v2 \<and> POSIX v2 r2)"
+using assms
+apply(erule_tac Prf.cases)
+apply(simp_all)
+unfolding POSIX_def
+apply(auto)
+apply (metis POSIX_ALT2 POSIX_def assms(2))
+by (metis POSIX_ALT1b assms(2))
+
+lemma POSIX_ALT_cases2:
+  assumes "POSIX v (ALT r1 r2)" "\<turnstile> v : (ALT r1 r2)" 
+  shows "(\<exists>v1. v = Left v1 \<and> POSIX v1 r1) \<or> (\<exists>v2. v = Right v2 \<and> POSIX v2 r2)"
+using assms POSIX_ALT_cases by auto
+
+lemma Prf_flat_empty:
+  assumes "\<turnstile> v : r" "flat v = []"
+  shows "nullable r"
+using assms
+apply(induct)
+apply(auto)
+done
+
+lemma POSIX_proj:
+  assumes "POSIX v r" "\<turnstile> v : r" "\<exists>s. flat v = c#s"
+  shows "POSIX (projval r c v) (der c r)"
+using assms
+apply(induct r c v arbitrary: rule: projval.induct)
+defer
+defer
+defer
+defer
+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(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis ValOrd.intros(7))
+apply(erule_tac [!] exE)
+prefer 3
+apply(frule POSIX_SEQ1)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(case_tac "flat v1 = []")
+apply(subgoal_tac "nullable r1")
+apply(simp)
+prefer 2
+apply(rule_tac v="v1" in Prf_flat_empty)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(simp)
+apply(frule POSIX_SEQ2)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(simp)
+apply(drule meta_mp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rule ccontr)
+apply(subgoal_tac "\<turnstile> val.Right (projval r2 c v2) : (ALT (SEQ (der c r1) r2) (der c r2))")
+apply(rotate_tac 11)
+apply(frule POSIX_ex)
+apply(erule exE)
+apply(drule POSIX_ALT_cases2)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(drule v3_proj)
+apply(simp)
+apply(simp)
+apply(drule POSIX_ex)
+apply(erule exE)
+apply(frule POSIX_ALT_cases2)
+apply(simp)
+apply(simp)
+apply(erule 
+prefer 2
+apply(case_tac "nullable r1")
+prefer 2
+apply(simp)
+apply(rotate_tac 1)
+apply(drule meta_mp)
+apply(rule POSIX_SEQ1)
+apply(assumption)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rotate_tac 7)
+apply(drule meta_mp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rotate_tac 7)
+apply(drule meta_mp)
+apply (metis Cons_eq_append_conv)
+
+
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(simp add: POSIX_def)
+apply(simp)
+apply(simp)
+apply(simp_all)[5]
+apply(simp add: POSIX_def)
+
+
+lemma POSIX_proj:
+  assumes "POSIX v r" "\<turnstile> v : r" "\<exists>s. flat v = c#s"
+  shows "POSIX (projval r c v) (der c r)"
+using assms
+apply(induct r arbitrary: c v rule: rexp.induct)
+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(simp add: POSIX_def)
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis ValOrd.intros(7))
+
+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(simp add: POSIX_def)
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis ValOrd.intros(7))
+apply(erule_tac [!] exE)
+prefer 3
+apply(frule POSIX_SEQ1)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(case_tac "flat v1 = []")
+apply(subgoal_tac "nullable r1")
+apply(simp)
+prefer 2
+apply(rule_tac v="v1" in Prf_flat_empty)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+
+
+lemma POSIX_proj:
+  assumes "POSIX v r" "\<turnstile> v : r" "\<exists>s. flat v = c#s"
+  shows "POSIX (projval r c v) (der c r)"
+using assms
+apply(induct r c v arbitrary: rule: projval.induct)
+defer
+defer
+defer
+defer
+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(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis ValOrd.intros(7))
+apply(erule_tac [!] exE)
+prefer 3
+apply(frule POSIX_SEQ1)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(case_tac "flat v1 = []")
+apply(subgoal_tac "nullable r1")
+apply(simp)
+prefer 2
+apply(rule_tac v="v1" in Prf_flat_empty)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(simp)
+apply(rule ccontr)
+apply(drule v3_proj)
+apply(simp)
+apply(simp)
+apply(drule POSIX_ex)
+apply(erule exE)
+apply(frule POSIX_ALT_cases2)
+apply(simp)
+apply(simp)
+apply(erule 
+prefer 2
+apply(case_tac "nullable r1")
+prefer 2
+apply(simp)
+apply(rotate_tac 1)
+apply(drule meta_mp)
+apply(rule POSIX_SEQ1)
+apply(assumption)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rotate_tac 7)
+apply(drule meta_mp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rotate_tac 7)
+apply(drule meta_mp)
+apply (metis Cons_eq_append_conv)
+
+
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(simp add: POSIX_def)
+apply(simp)
+apply(simp)
+apply(simp_all)[5]
+apply(simp add: POSIX_def)
+
+done
+(* NULL case *)
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply (metis ValOrd.intros(7))
+apply(rotate_tac 4)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(simp)
+prefer 2
+apply(simp)
+apply(frule POSIX_ALT1a)
+apply(drule meta_mp)
+apply(simp)
+apply(drule meta_mp)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(rule POSIX_ALT_I2)
+apply(assumption)
+apply(auto)[1]
+
+thm v4_proj2
+prefer 2
+apply(subst (asm) (13) POSIX_def)
+
+apply(drule_tac x="projval v2" in spec)
+apply(auto)[1]
+apply(drule mp)
+apply(rule conjI)
+apply(simp)
+apply(simp)
+
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+prefer 2
+apply(clarify)
+apply(subst (asm) (2) POSIX_def)
+
+apply (metis ValOrd.intros(5))
+apply(clarify)
+apply(simp)
+apply(rotate_tac 3)
+apply(drule_tac c="c" in t2)
+apply(subst (asm) v4_proj)
+apply(simp)
+apply(simp)
+thm contrapos_np contrapos_nn
+apply(erule contrapos_np)
+apply(rule ValOrd.intros)
+apply(subst  v4_proj2)
+apply(simp)
+apply(simp)
+apply(subgoal_tac "\<not>(length (flat v1) < length (flat (projval r2a c v2a)))")
+prefer 2
+apply(erule contrapos_nn)
+apply (metis nat_less_le v4_proj2)
+apply(simp)
+
+apply(blast)
+thm contrapos_nn
+
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(rule ValOrd.intros)
+apply(drule meta_mp)
+apply(auto)[1]
+apply (metis POSIX_ALT2 POSIX_def flat.simps(3))
+apply metis
+apply(clarify)
+apply(rule ValOrd.intros)
+apply(simp)
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(clarify)
+apply(rule ValOrd.intros)
+apply(simp)
+
+apply(drule meta_mp)
+apply(auto)[1]
+apply (metis POSIX_ALT2 POSIX_def flat.simps(3))
+apply metis
+apply(clarify)
+apply(rule ValOrd.intros)
+apply(simp)
+
+
+done
+(* EMPTY case *)
+apply(simp add: POSIX_def)
+apply(auto)[1]
+apply(rotate_tac 3)
+apply(erule Prf.cases)
+apply(simp_all)[5]
+apply(drule_tac c="c" in t2)
+apply(subst (asm) v4_proj)
+apply(auto)[2]
+
+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(simp)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+(* ALT case *)
+
+
+unfolding POSIX_def
+apply(auto)
+thm v4
+
+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)"
+using assms
+apply(induct arbitrary: v1 v2 rule: der.induct)
+(* NULL case *)
+apply(simp)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+(* EMPTY case *)
+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(simp)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+(* ALT case *)
+apply(simp)
+apply(erule ValOrd.cases)
+apply(simp_all)[8]
+apply(rule ValOrd.intros)
 apply(subst v4)
 apply(clarify)
 apply(rotate_tac 3)
@@ -769,13 +1395,16 @@
 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(rule ValOrd.intros)
@@ -805,10 +1434,37 @@
 apply(simp_all)[5]
 apply(erule Prf.cases)
 apply(simp_all)[5]
+apply(clarify)
+defer
+apply(simp)
+apply(erule ValOrd.cases)
+apply(simp_all del: injval.simps)[8]
+apply(simp)
+apply(clarify)
+apply(simp)
+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(clarify)
+apply(rule ValOrd.intros(2))
+
+
+
+
+done
+
+
+txt {*
+done
 (* nullable case - unfinished *)
 apply(simp)
 apply(erule ValOrd.cases)
-apply(simp_all)[8]
+apply(simp_all del: injval.simps)[8]
+apply(simp)
 apply(clarify)
 apply(simp)
 apply(erule Prf.cases)
@@ -820,12 +1476,9 @@
 apply(simp_all)[5]
 apply(clarify)
 apply(simp)
-apply(case_tac "injval r1 c v1 = mkeps r1") 
-apply(rule ValOrd.intros(1))
-apply(simp)
-apply (metis impossible_Cons le_add2 list.size(3) mkeps_flat monoid_add_class.add.right_neutral v4)
 apply(rule ValOrd.intros(2))
-apply(drule_tac x="proj r1 c" in spec)
+oops
+*}
 oops
 
 lemma POSIX_der:
diff -r 26b71a36f55f -r d86d685273ce thys/Test.txt
--- a/thys/Test.txt	Mon Feb 09 00:46:25 2015 +0000
+++ b/thys/Test.txt	Thu Feb 26 12:41:55 2015 +0000
@@ -1,3 +1,7 @@
+<<<<<<< local
+test2
+=======
 test
 test file
 
+>>>>>>> other
diff -r 26b71a36f55f -r d86d685273ce thys/notes.pdf
Binary file thys/notes.pdf has changed
diff -r 26b71a36f55f -r d86d685273ce thys/notes.tex
--- a/thys/notes.tex	Mon Feb 09 00:46:25 2015 +0000
+++ b/thys/notes.tex	Thu Feb 26 12:41:55 2015 +0000
@@ -348,5 +348,8 @@
 \end{tabular}
 \end{center}
 
+\subsection*{Problems in the paper proof}
+
+I cannot verify 
 
 \end{document}