more changes
authorChengsong
Tue, 03 Mar 2020 21:56:09 +0000
changeset 144 bc340e8f4165
parent 143 5e47080a7164
child 145 a7c063981fa5
more changes
etnms/etnms.tex
--- a/etnms/etnms.tex	Tue Mar 03 21:36:53 2020 +0000
+++ b/etnms/etnms.tex	Tue Mar 03 21:56:09 2020 +0000
@@ -909,20 +909,15 @@
 
 
 \noindent
-linking $\flex$ and $\lexer$,
+This property links $\flex$ and $\lexer$,
 it essentially does lexing by
 stacking up injection functions while doing derivatives,
 explicitly showing the order of characters being
 injected back in each step.
-With $\flex$ we can write $\lexer$ this way: 
-
-\begin{center}
-$\lexer \;r\; s = \flex \;id \; r\;s \;(\mkeps (r\backslash s))$
-\end{center}
 
 \noindent
 The other trick, which is the crux in the existing proof, 
-is the use of $\retrieve$-function by Sulzmann and Lu:
+is the use of the $\retrieve$-function by Sulzmann and Lu:
 \begin{center}
 \begin{tabular}{@{}l@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
   $\textit{retrieve}\,(_{bs}\ONE)\,\Empty$ & $\dn$ & $bs$\\
@@ -946,11 +941,11 @@
 This function assembles the bitcode 
 using information from both the derivative regular expression and the
 value. Sulzmann and Lu proposed this function, but did not prove
-anything about it. Ausaf and Urban made this important use of the
-fact about $\retrieve$ in the proof:
+anything about it. Ausaf and Urban made use of the
+fact about $\retrieve$ in their proof:
  
  \begin{center} 
- $\retrieve \rup \backslash c \; v = \retrieve  \rup (\inj \;r \;c \; v)$
+ $\retrieve\; \rup \backslash c \; v = \retrieve \;  \rup (\inj \;r \;c \; v)$
  \end{center} 
 
 \noindent
@@ -973,13 +968,13 @@
 \end{center}
 \noindent
 where $\mkeps(r\backslash s) $ is denoted using $v$,
-then a reverse induction technique is 
-best suited here to make use of 
+then a reverse induction  
+helps with using 
 the fact~\eqref{flex} in proving the $n+1$ step:
 \begin{center} 
 $ \flex \; r\; id\; (s@[c])\; v = \textit{decode} \;( \textit{retrieve}\; (\rup \backslash s) \; (\inj \; (r\backslash s) \;c\;v)\;) r$
 \end{center}
-and using a lemma that
+Using a lemma that
 \begin{center}
 $\textit{retrieve}\; (\rup \backslash s) \; (\inj \; (r\backslash s) \;c\;v)\; = \textit{retrieve}\; (\rup \backslash s@[c])  \; v\; $
 \end{center}
@@ -989,9 +984,27 @@
 \end{center}
 and the inductive step is done because
 \begin{center} 
-$ \textit{retrieve}\; (\rup \backslash s@[c]) \; \mkeps(r\backslash s) =  \bmkeps \;(\rup \backslash s@[c])$
+$ \textit{retrieve}\; (\rup \backslash s@[c]) \; \mkeps(r\backslash s) =  \bmkeps \;(\rup \backslash s@[c])$.
 \end{center}
 
+\noindent
+To use 
+$ \flex \; r\; id\; s\; v = \textit{decode} \;( \textit{retrieve}\; (\rup \backslash s) \; v \;) r$
+ for our 
+correctness proof, simply replace the $v$ with
+$\mkeps\;(r\backslash s)$, and apply the lemma that
+\begin{center}
+$ \; \bmkeps \; \rup =  (\textit{retrieve} \; \rup \; \mkeps(r))$
+\end{center}
+\noindent
+We get the correctness of our bit-coded algorithm:
+\begin{center}
+$\flex \;r\;  id \; s \; (\mkeps \; (r\backslash s)) = \textit{decode} \; (\bmkeps \; \rup\backslash s) \; r$.
+\end{center}
+\noindent
+
+
+
 \subsubsection{Using Retrieve Function In a New Setting}
  Ausaf
 and Urban used $\retrieve$  to prove  the correctness of bitcoded
@@ -1005,41 +1018,9 @@
 The idea is that using $v'$, a simplified version of $v$ that had gone
 through the same simplification step as $\textit{simp}(a)$, we are able
 to extract the bitcode that gives the same parsing information as the
-unsimplified one. However, we noticed that constructing such a  $v'$
-from $v$ is not so straightforward. The point of this is that  we might
-be able to finally bridge the gap by proving
-
-\noindent
-By using a property of retrieve we have the $\textit{RHS}$ of the above equality is
-$decode (retrieve (r^\uparrow \backslash(s @ [c])) v) r$, and this gives the 
-main lemma result:
-
-\begin{center}
-$ \flex \;r\;  id \; (s@[c]) \; v =\textit{decode}(\textit{retrieve} (\rup \backslash (s@[c])) \;v) r$
-\end{center}
-
-
-
-
-\noindent
-To use this lemma result for our 
-correctness proof, simply replace the $v$ in the
-$\textit{RHS}$ of the above equality with
-$\mkeps\;(r\backslash (s@[c]))$, and apply the lemma that
- 
-\begin{center}
-$\textit{decode} \; \bmkeps \; \rup \; r = \textit{decode} \; (\textit{retrieve} \; \rup \; \mkeps(r)) \;r$
-\end{center}
-\noindent
-We get the correctness of our bit-coded algorithm:
-\begin{center}
-$\flex \;r\;  id \; s \; (\mkeps \; r\backslash s) = \textit{decode} \; \bmkeps \; \rup\backslash s \; r$
-\end{center}
-\noindent
-The bridge between the above chain of equalities
-is the use of $\retrieve$,
-if we want to use a similar technique for the 
-simplified version of algorithm,
+unsimplified one. 
+If we want to use a similar technique as
+that of the existing proof,
 we face the problem that in the above 
 equalities,
 $\retrieve \; a \; v$ is not always defined.