
diff -r f28cf86a1e7f -r a05b3c89e8aa thys/Paper/Paper.thy
--- a/thys/Paper/Paper.thy	Tue Mar 08 11:40:36 2016 +0000
+++ b/thys/Paper/Paper.thy	Tue Mar 08 12:02:25 2016 +0000
@@ -961,16 +961,16 @@
   ordering (from all possible solutions). The only difference between their
   GREEDY ordering and the ``ordering'' by Sulzmann and Lu is that GREEDY, if
   possible, always prefers a $Left$-value over a $Right$-value, no matter
-  what the underlying string is. This seems like only a very minor
-  difference, but it leads to drastic consequences in terms what
+  what the underlying string is. This seems to be only a very minor
+  difference, but it has drastic consequences in terms of what
   properties both orderings enjoy. What is interesting for our purposes is
   that the properties reflexivity, totality and transitivity for this GREEDY
   ordering can be proved relatively easily by induction.
 
   These properties of GREEDY, however, do not transfer to the POSIX
-  ``ordering'' by Sulzmann and Lu. To start with, $v \geq_r v′$ is not
-  defined inductively, but as $v = v′$ or $v >_r v′ \wedge |v| = |v′|$. This
-  means that $v >_r v′$ does not imply $v \geq_r v′$. Moreover, transitivity
+  ``ordering'' by Sulzmann and Lu. To start with, $v \geq_r v'$ is not
+  defined inductively, but as $v = v'$ or $v >_r v' \wedge |v| = |v'|$. This
+  means that $v >_r v'$ does not imply $v \geq_r v'$. Moreover, transitivity
   does not hold in the ``usual'' formulation, for example:
 
 \begin{proposition}
@@ -979,14 +979,14 @@
 then $v_1 \posix_r v_3$.
 \end{proposition}
 
-\noindent If formulated like this, then there are various counter examples:
-FOr example let $r$ be $a + ((a + a)\cdot (a + \textbf{0}))$ then the $v_1$,
+\noindent If formulated in this way, then there are various counter examples:
+For example let $r$ be $a + ((a + a)\cdot (a + \textbf{0}))$ then the $v_1$,
 $v_2$ and $v_3$ below are values of $r$:
 
 \begin{center}
 \begin{tabular}{lcl}
  $v_1$ & $=$ & $Left(Char\;a)$\\
- $v_2$ & $=$ & $Right((Left(Char\;a), Right(Void)))$\\
+ $v_2$ & $=$ & $Right((Left(Char\;a), Right()))$\\
  $v_3$ & $=$ & $Right((Right(Char\;a), Left(Char\;a)))$
 \end{tabular}
 \end{center}
@@ -994,7 +994,7 @@
 \noindent Moreover $v_1 \posix_r v_2$ and $v_2 \posix_r v_3$,
 but \emph{not} $v_1 \posix_r v_3$! The reason is that although
 $v_3$ is a $Right$-value, it can match a longer string, namely
-$|v_3| = aa$, while $|v_1|$ (and $|v_2|$) matches only $a$. So
+$|v_3| = [a,a]$, while $|v_1|$ (and $|v_2|$) matches only $[a]$. So
 transitivity in this formulation does not hold---in this
 example actually $v_3 \posix_r v_1$!
 
@@ -1003,26 +1003,26 @@
 underlying strings are of the same length. This excludes the
 counter example above and any counter-example we were able 
 to find (by hand and by machine). Thus the transitivity 
-lemma in should be formulated as:
+lemma should be formulated as:
 
-\begin{property}
+\begin{proposition}
 Suppose $v_1 : r$, $v_2 : r$ and 
 $v_3 : r$, and also $|v_1|=|v_2|=|v_3|$.\\
 If $v_1 \posix_r v_2$ and $v_2 \posix_r v_3$
 then $v_1 \posix_r v_3$.
-\end{property}
+\end{proposition}
 
-\noindent While we agree with Sulzmann and Lu that this property probably
+\noindent While we agree with Sulzmann and Lu that this property probably(!)
 holds, proving it seems not so straightforward: although one begins with the
 assumption that the values have the same flattening, this
 cannot be maintained as one descends into the induction. This is 
-a problem that occurs in a number of places in their proof.
-Sulzmann and Lu do not give an explicit proof
-of the transitivity property, but give a closely related
+a problem that occurs in a number of places in the proofs by Sulzmann and Lu.
+
+Although they do not give an explicit proof
+of the transitivity property, they give a closely related
 property about the existence of maximal elements. They state
 that this can be verified by an induction on $r$. We disagree
 with this as we shall show next in case of transitivity.
-
 The case where the reasoning breaks down is the sequence case,
 say $r_1\cdot r_2$. The induction hypotheses in this case
 are
@@ -1067,9 +1067,9 @@
 namely:
 
 \begin{equation}
-|(v_{1l}, v_{1r})| = |(v_{2l}, v_{2r})|
+|Seq\,v_{1l}\, v_{1r}| = |Seq\,v_{2l}\, v_{2r}|
 \qquad\textrm{and}\qquad
-|(v_{2l}, v_{2r})| = |(v_{3l}, v_{3r})|
+|Seq\,v_{2l}\, v_{2r}| = |Seq\,v_{3l}\, v_{3r}|
 \label{lens}
 \end{equation}
 
@@ -1077,7 +1077,7 @@
 We need to show that
 
 \[
-Seq\,v_{1l}\, v_{1r}) \posix_{r_1\cdot r_2} Seq\, v_{3l}\, v_{3r}
+Seq\,v_{1l}\, v_{1r} \posix_{r_1\cdot r_2} Seq\, v_{3l}\, v_{3r}
 \]
 
 \noindent holds. We can proceed by analysing how the
@@ -1109,7 +1109,7 @@
 \noindent but still \eqref{lens} will hold. Now we are stuck,
 since the IH does not apply. As said, this problem where the
 induction hypothesis does not apply arises in several places in
-the proof of Sulzmann and LU, not just when proving transitivity.
+the proof of Sulzmann and Lu, not just for proving transitivity.
 
 *}
 




