Paper/Paper.thy
changeset 122 ab6637008963
parent 121 1cf12a107b03
child 123 23c0e6f2929d
--- a/Paper/Paper.thy	Sat Feb 19 21:49:11 2011 +0000
+++ b/Paper/Paper.thy	Sat Feb 19 22:05:22 2011 +0000
@@ -1058,28 +1058,28 @@
   regular expression.
 
   While regular expressions are convenient in formalisations, they have some
-  limitations. One is that there seems to be no notion of a minimal regular
-  expression, like there is for automata. For an implementation of a simple
-  regular expression matcher, whose correctness has been formally
-  established, we refer the reader to Owens and Slind \cite{OwensSlind08}.
+  limitations. One is that there seems to be no method of calculating a
+  minimal regular expression (for example in terms of length), like there is
+  for automata. For an implementation of a simple regular expression matcher,
+  whose correctness has been formally established, we refer the reader to
+  Owens and Slind \cite{OwensSlind08}.
 
 
   Our formalisation consists of 790 lines of Isabelle/Isar code for the first
-  direction and 475 for the second, plus standard material about regular languages. 
-  While this might be seen as too large to
-  count as a concise proof pearl, this should be seen in the context of the
-  work done by Constable at al \cite{Constable00} who formalised the
-  Myhill-Nerode theorem in Nuprl using automata. 
-  They write that their
-  four-member team needed something on the magnitute of 18 months for their
-  formalisation. The estimate for our formalisation is that we
-  needed approximately 3 months and this included the time to find our proof
-  arguments. Unlike Constable et al, who were able to follow the proofs from
-  \cite{HopcroftUllman69}, we had to find our own arguments.  So for us the formalisation
-  was not the bottleneck. It is hard to gauge the size of a formalisation in
-  Nurpl, but from what is shown in the Nuprl Math Library about their
-  development it seems substantially larger than ours. The code of
-  ours can be found in the Mercurial Repository at
+  direction and 475 for the second, plus 300 lines of standard material about
+  regular languages. While this might be seen as too large to count as a
+  concise proof pearl, this should be seen in the context of the work done by
+  Constable at al \cite{Constable00} who formalised the Myhill-Nerode theorem
+  in Nuprl using automata. They write that their four-member team needed
+  something on the magnitute of 18 months for their formalisation. The
+  estimate for our formalisation is that we needed approximately 3 months and
+  this included the time to find our proof arguments. Unlike Constable et al,
+  who were able to follow the proofs from \cite{HopcroftUllman69}, we had to
+  find our own arguments.  So for us the formalisation was not the
+  bottleneck. It is hard to gauge the size of a formalisation in Nurpl, but
+  from what is shown in the Nuprl Math Library about their development it
+  seems substantially larger than ours. The code of ours can be found in the
+  Mercurial Repository at
 
   \begin{center}
   \url{http://www4.in.tum.de/~urbanc/cgi-bin/repos.cgi/regexp/}
@@ -1108,7 +1108,7 @@
   generated with respect to @{text s}.  Using the fact that two strings are
   Myhill-Nerode related whenever their derivative is the same together with
   the fact that there are only finitely many derivatives for a regular
-  expression would give us the same argument as ours. However it seems not so easy to
+  expression would give us a similar argument as ours. However it seems not so easy to
   calculate the derivatives and then to count them. Therefore we preferred our
   direct method of using tagging-functions involving equivalence classes. This
   is also where our method shines, because we can completely side-step the