
diff -r c0c1ebe09c7d -r 8ffa28fce271 ChengsongTanPhdThesis/Chapters/RelatedWork.tex
--- a/ChengsongTanPhdThesis/Chapters/RelatedWork.tex	Sat Nov 12 00:37:23 2022 +0000
+++ b/ChengsongTanPhdThesis/Chapters/RelatedWork.tex	Sat Nov 12 21:34:40 2022 +0000
@@ -15,13 +15,40 @@
 with theoretical work on them being
 fairly recent.
 
-Campaneu gave 
+Campaneu et al. studied regexes with back-references
+in the context of formal languages theory in 
+their 2003 work \cite{campeanu2003formal}.
+They devised a pumping lemma for Perl-like regexes, 
+proving that the langugages denoted by them
+is  properly  contained in context-sensitive
+languages.
+More interesting questions such as 
+whether the language denoted by Perl-like regexes
+can express palindromes ($\{w \mid w = w^R\}$)
+are discussed in \cite{campeanu2009patterns} 
+and \cite{CAMPEANU2009Intersect}.
+Freydenberger \cite{Frey2013} investigated the 
+expressive power of back-references. He showed several 
+undecidability and decriptional complexity results 
+of back-references, concluding that they add
+great power to certain programming tasks but are difficult to harness.
+An interesting question would then be
+whether we can add restrictions to them, 
+so that they become expressive enough, but not too powerful.
+Freydenberger and Schmid \cite{FREYDENBERGER20191}
+introduced the notion of deterministic
+regular expressions with back-references to achieve
+a better balance between expressiveness and tractability.
 
 
-See \cite{AHO1990255} for a survey
+Fernau and Schmid \cite{FERNAU2015287} and Schmid \cite{Schmid2012}
+investigated the time complexity of different variants
+of back-references.
+
+See \cite{BERGLUND2022} for a survey
 of these works and comparison between different
-flavours (e.g. whether references can be circular, 
-can labels be repeated etc.) of back-references syntax.
+flavours  of back-references syntax (e.g. whether references can be circular, 
+can labels be repeated etc.).
 
 
 \subsection{Matchers and Lexers with Mechanised Proofs}




