diff -r c0c1ebe09c7d -r 8ffa28fce271 ChengsongTanPhdThesis/Chapters/Finite.tex --- 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