ChengsongTanPhdThesis/Chapters/Finite.tex
changeset 624 8ffa28fce271
parent 620 ae6010c14e49
child 625 b797c9a709d9
--- 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