anotehr update
authorChengsong
Sun, 07 Jul 2019 22:18:24 +0100
changeset 67 e974c5477a8c
parent 66 8c8c82c0515f
child 68 3c73d95cbfef
anotehr update
ninems/ninems.tex
--- a/ninems/ninems.tex	Sun Jul 07 22:09:24 2019 +0100
+++ b/ninems/ninems.tex	Sun Jul 07 22:18:24 2019 +0100
@@ -715,7 +715,7 @@
      $\textit{pder} \; c \; r^*$ & $\dn$ & $ \{  r' \cdot r^* \mid r' \in pder \; c \; r   \}  $ \\  
  \end{tabular}
  \end{center}
-it is essentially a set of regular expressions that come from the sub-structure of the original regular expression. 
+ A partial derivative of a regular expression $r$ is essentially a set of regular expressions that are either $r$'s children expressions or a concatenation of them. 
 Antimirov has proved a nice size bound of the size of partial derivatives. Roughly speaking the size will not exceed the fourth power of the number of nodes in that regular expression.  Interestingly, we observed from experiment that after the simplification step, our regular expression has the same size or is smaller than the partial derivatives. This allows us to prove a tight bound on the size of regular expression during the running time of the algorithm if we can establish the connection between our simplification rules and partial derivatives.
 
  %We believe, and have generated test
@@ -723,10 +723,12 @@
 %Sulzmann and Lu's algorithm. Let us give some details about this next.
 
 Bit-codes look like this:
-\[			b ::=   S \mid  Z \; \;\;
+\begin{center}
+		$b ::=   S \mid  Z \; \;\;
 bs ::= [] \mid b:bs    
-\]
-They are just a string of bits, the names "S" and "Z"  here are kind of arbitrary, we can use 0 and 1 or binary symbol to substitute them. They are a compact form of parse trees.
+$
+\end{center}
+They are just a string of bits, the names $S$ and $Z$  here are quite arbitrary, we can use 0 and 1 or any other set of binary symbols to substitute them. They are a compact form of parse trees.
 Here is how values and bit-codes are related:
 Bitcodes are essentially incomplete values.
 This can be straightforwardly seen in the following transformation: