--- a/ChengsongTanPhdThesis/Chapters/Finite.tex Sat Nov 12 00:37:23 2022 +0000
+++ b/ChengsongTanPhdThesis/Chapters/Finite.tex Sat Nov 12 21:34:40 2022 +0000
@@ -8,10 +8,11 @@
%regex's derivatives.
-In this chapter we give a guarantee in terms of size of derivatives:
+In this chapter we give a bound in terms of size of
+the calculated derivatives:
given an annotated regular expression $a$, for any string $s$
-our algorithm $\blexersimp$'s internal annotated regular expression
-size is finitely bounded
+our algorithm $\blexersimp$'s derivatives
+are finitely bounded
by a constant that only depends on $a$.
Formally we show that there exists an $N_a$ such that
\begin{center}
@@ -32,8 +33,8 @@
grows beyond a finite bound, then clearly
the algorithm (which traverses these structures) will
be slow.
- The next step would be to refine the bound $N_a$ so that it
- is polynomial on $\llbracket a\rrbracket$.
+ The next step is to refine the bound $N_a$ so that it
+ is not just finite but polynomial in $\llbracket a\rrbracket$.
\item
Having the finite bound formalised
gives us a higher confidence that
@@ -41,7 +42,8 @@
like $\simpsulz$ does.
The bound is universal for a given regular expression,
which is an advantage over work which
- only gives empirical evidence on some test cases (see Verbatim++\cite{Verbatimpp}).
+ only gives empirical evidence on
+ some test cases (see Verbatim++ work\cite{Verbatimpp}).
\end{itemize}
In the next section we describe in more detail
what the finite bound means in our algorithm