
diff -r bd1354127574 -r 56057198e4f5 ChengsongTanPhdThesis/main.tex
--- a/ChengsongTanPhdThesis/main.tex	Fri Dec 30 23:41:44 2022 +0000
+++ b/ChengsongTanPhdThesis/main.tex	Fri May 26 08:09:30 2023 +0100
@@ -41,8 +41,9 @@
 \usepackage[utf8]{inputenc} % Required for inputting international characters
 \usepackage[T1]{fontenc} % Output font encoding for international characters
 %\usepackage{fdsymbol} % Loads unicode-math
-
 \usepackage{cancel}
+\usepackage{fontawesome5}
+\usepackage{bbding,pifont,dingbat}
 
 \usepackage{listings}
 \usepackage{xcolor}
@@ -290,6 +291,31 @@
 \begin{abstract}
 \addchaptertocentry{\abstractname} % Add the abstract to the table of contents
 %\addchap{Abstract} 
+\textbf{Problem: not like an abstract, more like a summary}
+\textbf{Goal for new abstract: more high-level and abstract, tell the problem and solution in a concise way.}
+
+New abstract:\\
+%Modern computer systems rely on lexing for essential applications such as
+%compilers, IDEs, file systems, and network intrusion detection systems.
+%These applications require correctness with respect to
+%the POSIX standard and high performance.
+%%While existing implementations of lexers often achieve high performance,
+%Existing implementations had drawbacks such as bugs and catastrophic backtracking,
+%preventing them from solving the problem once
+%and for all.
+%To address these drawbacks,
+%this thesis offers an algorithm with formally proven correctness and internal data structures' size bound. 
+%These mechanised proofs ensure that our algorithm is fast and correct in \textbf{all} cases.
+%Our proofs use term-rewriting relations to establish invariants during derivatives and simplifications,
+%which is extensible and friendly to theorem provers.
+
+POSIX is the most widely used disambiguation strategy for regular expression matching.  There are some difficulties associated with the POSIX strategy and according to tests conducted by Kulkewitz, many regular expression matchers implementing this strategy produce incorrect results. This thesis is concerned with an POSIX regular expression matching algorithm introduced by Sulzmann and Lu. This algorithm uses bitcoded regular expressions and is based on the idea of Brzozowski derivatives. The algorithm generates POSIX values which encode the information of how a regular expression matches a string - that is, which part of the string is matched by which part of the regular expression. This information is needed in the context of lexing in order to extract and to classify tokens.
+
+While a formalised correctness proof for Sulzmann and Lu's algorithm already exists, this proof does not include any of the crucial simplification rules. These simplification rules are however necessary in order to have an acceptable runtime for this algorithm. Our version of the simplification rules includes a number of fixes and improvements: one problem we fix has to do with their use of the nub function that does not remove non-trivial duplicates. We improve the simplification rules by formulating them as simple recursive function and also by simplifying more instances of regular expressions.  As a result we can establish a bound on the size of derivatives. Our proofs are formalised in Isabelle/HOL.
+
+
+
+Old abstract:
 This thesis is about regular expressions and derivatives. It combines functional algorithms and their formal verification in the Isabelle/HOL theorem prover. 
 Classic results say that regular expression matching should be 
 linear with respect to the input. The size of the regular expressions




