--- a/Spiral.scala Wed May 08 22:09:59 2019 +0100
+++ b/Spiral.scala Tue Jun 25 18:56:52 2019 +0100
@@ -488,49 +488,56 @@
println("frect v = ")
println(frectv)
}
- */
- def retrieve_experience(){
- for(i <- 1 to 100){
- val rg = internalise(balanced_struct_gen(1))//ASTAR(List(),AALTS(List(),List(ASTAR(List(Z),ACHAR(List(),'a')), ASEQ(List(S),ACHAR(List(),'a'),ACHAR(List(),'b')))))//internalise(balanced_struct_gen(3))//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b"))))
- val st = "ab"//"abaab"
- val r_der_s = ders(st.toList, erase(rg))
- if(nullable(r_der_s)){
- val unsimplified_vl = mkeps(r_der_s)
- val r_bder_s = bders( st.toList, rg)
- val s_r_bder_s = bsimp(r_bder_s)
- val bits1 = retrieve(internalise(r_der_s), unsimplified_vl)
- println("The property: ")
- println("retrieve ar v = retrieve (bsimp ar) (decode erase(bsimp(ar)) code(v)) if |- v : r")
- println("does not hold.")
- println("Here v == mkeps r\\s and r == r\\s")
- println("regular expression is")
- println(rg)
- println("string is")
- println(st)
- println("derivative without simplification is ")
-
- println(r_bder_s)
+ *///KH8W5BXL
+ def nice_lex(r: Rexp, s: List[Char], ar: ARexp) : Val = s match {
+ case Nil =>
+ if (nullable(r)){
+ val vr = mkeps(r)
+ val bits1 = retrieve(ar, vr)
+ val av = bsimp2(ar, vr)
+ val bits2 = retrieve(av._1, av._2)
+ if(bits1 != bits2) throw new Exception("bsimp2 does not work")
+ vr
+ }
+ else throw new Exception("Not matched")
+ case c::cs => {
+ val vr = inj(r, c, nice_lex(der(c, r), cs, bder(c, ar)));
+ val bits1 = retrieve(ar, vr);
+ val av = bsimp2(ar, vr);
+ val bits2 = retrieve(av._1, av._2);
+ if(bits1 != bits2) throw new Exception("bsimp2 does not work");
+ vr
+ }
+ }
+ def test_bsimp2(){
+ for(i <- 1 to 1000){
+ val rg = (balanced_struct_gen(9))//ASTAR(List(),AALTS(List(),List(ASTAR(List(Z),ACHAR(List(),'a')), ASEQ(List(S),ACHAR(List(),'a'),ACHAR(List(),'b')))))//internalise(balanced_struct_gen(3))//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b"))))
+ val st = rd_string_gen(3, 4)
+ val a = internalise(rg)
+ val final_derivative = ders(st.toList, rg)
+ if(nullable(final_derivative))
+ nice_lex(rg, st.toList, a)
+ }
+ }
- println("after erase of this derivative")
- println(erase(r_bder_s))
- println("simplification of derivative (bsimp(ar))")
- println(s_r_bder_s)
- println("after erase of simplified derivative (erase(bsimp(ar))")
- println(erase(s_r_bder_s))
- println("decode says the above regex and the below bits(code(v)) are not decodable")
- println(unsimplified_vl)
- println(code(unsimplified_vl))
- println(bits1)
- val bits2 = retrieve(s_r_bder_s, decode(erase(s_r_bder_s), code(unsimplified_vl)))
- if(bits1 == bits2){
- println("retrieve ar v = retrieve (bsimp ar) (decode erase(bsimp(ar)) code(v)) if |- v : r")
- println("Here v == mkeps r\\s and r == r\\s")
- println(r_der_s, unsimplified_vl)
- println(s_r_bder_s, erase(s_r_bder_s), code(unsimplified_vl))
- }
+ def neat_retrieve(){
+ for(i <- 1 to 1000){
+ val rg = internalise(balanced_struct_gen(6))//ASTAR(List(),AALTS(List(),List(ASTAR(List(Z),ACHAR(List(),'a')), ASEQ(List(S),ACHAR(List(),'a'),ACHAR(List(),'b')))))//internalise(balanced_struct_gen(3))//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b"))))
+ val st = rd_string_gen(3, 5)
+ val final_derivative = ders(st.toList, erase(rg))
+ if(nullable(final_derivative)){
+ val unsimplified_vl = mkeps(final_derivative)
+ val arexp_for_retrieve = bders( st.toList, rg)
+ val simp_ar_vl = bsimp2(arexp_for_retrieve, unsimplified_vl)
+ val bits1 = retrieve(arexp_for_retrieve, unsimplified_vl)
+ val bits2 = retrieve(simp_ar_vl._1, simp_ar_vl._2)
+ if(bits1 != bits2){
+ println("nOOOOOOOOOO!")
}
}
}
+ }
+
def radical_correctness(){
enum(3, "abc").map(tests_blexer_simp(strs(3, "abc"))).toSet
random_pool(1, 5).map(tests_blexer_simp(strs(5, "abc"))).toSet
@@ -539,16 +546,18 @@
val r = ALTS(List(SEQ(ZERO,CHAR('b')), ONE))
val v = Right(Empty)
val a = internalise(r)
- val as = bsimp(a)
+ val a_v = bsimp2(a,v)
println(s"Testing ${r} and ${v}")
println(s"internalise(r) = ${a}")
+ println(s"a_v = ${a_v}")
val bs1 = retrieve(a, v)
println(bs1)
- println(s"as = ${as}")
+ println(s"as = ${a_v._1}")
//val bs2 = retrieve(as, decode(erase(as), bs1))
- val bs3 = retrieve(as, decode(erase(as), bs1.tail))
- println(decode(erase(as), bs1.tail))
- println(bs3)
+ val bs3 = retrieve(a_v._1, a_v._2)//decode(erase(as), bs1) does not work
+ //println(decode(erase(as), bs1))
+ println(s"bs1=${bs1}, bs3=${bs3}")
+ //println(decode(erase(a_v._1), bs3))
}
def essence_posix(){
//val s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"//rd_string_gen(alphabet_size, 3)//"abaa"//rd_string_gen(alphabet_size, 3)
@@ -567,8 +576,10 @@
//radical_correctness()
//correctness_proof_convenient_path()
//retrieve_experience()
+ //neat_retrieve()
+ test_bsimp2()
//christian_def()
- essence_posix()
+ //essence_posix()
}
}
Binary file corr_pr_sketch.pdf has changed
--- a/corr_pr_sketch.tex Wed May 08 22:09:59 2019 +0100
+++ b/corr_pr_sketch.tex Tue Jun 25 18:56:52 2019 +0100
@@ -18,71 +18,102 @@
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\begin{document}
-This is a sketch proof for the correctness of the algorithm ders\_simp.
-\section{Function Definitions}
+This is an outline of the structure of the paper with a little bit of flesh in it.
+\section{The Flow of thought process}
-\begin{definition}{Bits}
-\begin{verbatim}
-abstract class Bit
-case object Z extends Bit
-case object S extends Bit
-case class C(c: Char) extends Bit
-type Bits = List[Bit]
-\end{verbatim}
-\end{definition}
-
-\begin{definition}{Annotated Regular Expressions}
+\begin{definition}{Regular Expressions and values}
\begin{verbatim}
-abstract class ARexp
-case object AZERO extends ARexp
-case class AONE(bs: Bits) extends ARexp
-case class ACHAR(bs: Bits, f: Char) extends ARexp
-case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp
-case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp
-case class ASTAR(bs: Bits, r: ARexp) extends ARexp
+TODO
\end{verbatim}
\end{definition}
-\begin{definition}{bnullable}
+Value is.a parse tree for the regular expression matching the string.
+
+
+
+\begin{definition}{nullable}
\begin{verbatim}
- def bnullable (r: ARexp) : Boolean = r match {
- case AZERO => false
- case AONE(_) => true
- case ACHAR(_,_) => false
- case AALTS(_, rs) => rs.exists(bnullable)
- case ASEQ(_, r1, r2) => bnullable(r1) && bnullable(r2)
- case ASTAR(_, _) => true
- }
+TODO
+\end{verbatim}
+\end{definition}
+The idea behind nullable: whether it contains the empty string.
+
+\begin{definition}{derivatives}
+TODO
+
+\end{definition}
+
+This definition can be used for matching algorithm.
+
+\begin{definition}{matcher}
+TODO
+\end{definition}
+
+\begin{definition}{POSIX values}
+TODO
+\end{definition}
+
+\begin{definition}{POSIX lexer algorithm}
+TODO
+\end{definition}
+
+\begin{definition}{POSIX lexer algorithm with simplification}
+TODO
+\end{definition}
+This simplification algorithm is rather complicated as it entangles derivative, simplification and value reconstruction. We need to split the regular expression structure of the information for lexing so that simplifcation only changes the regex but does not destroy the information for reconstructing the resulting value.\\
+
+Introduce regex with auxiliary information:
+
+\begin{definition}{annotated regular expression}
+TODO
+\end{definition}
+
+\begin{definition}{encoding}
+TODO
+\end{definition}
+Encoding translates values into bit codes with some information loss.
+
+\begin{definition}{decoding}
+TODO
+\end{definition}
+Decoding translates bitcodes back into values with the help of regex to recover the structure.\\
+
+During different phases of lexing, we sometimes already know what the value would look like if we match the branch of regex with the string(e.g. a STAR with 1 more iteration, a left/right value), so we can partially encode the value at diffferent phases of the algorithm for later decoding.
+\\
+Examples of such partial encoding:
+
+\begin{definition}{internalise}
+TODO
+\end{definition}
+When doing internalise on ALT:\\
+Whichever branch is chosen, we know exactly the shape of the value, and therefore can get the bit code for such a value: Left corresponds to Z and Right to S
+
+\begin{definition}{bmkeps}
+TODO
+\end{definition}
+bmkeps on the STAR case:\\
+We know there could be no more iteration for a star if we want to get a POSIX value for an empty string, so the value must be Stars [], corresponding to an S in the bit code.
+
+\begin{definition}{bder}
+TODO
+\end{definition}
+SEQ case with the first regex nullable:\\
+bmkeps will extract the value for how a1 mathces the empty string and encode it into a bit sequence.
+
+\begin{definition}{blexer}
+\begin{verbatim}
+TODO
\end{verbatim}
\end{definition}
-\begin{definition}{ders\_simp}
-\begin{verbatim}
-def ders_simp(r: ARexp, s: List[Char]): ARexp = {
- s match {
- case Nil => r
- case c::cs => ders_simp(bsimp(bder(c, r)), cs)
- }
-}\end{verbatim}
-\end{definition}
+adding simplifcation.\\
+
+size of simplified regex: smaller than Antimirov's pder.\\
-\begin{definition}{bder}
-\begin{verbatim}
-def bder(c: Char, r: ARexp) : ARexp = r match {
- case AZERO => AZERO
- case AONE(_) => AZERO
- case ACHAR(bs, f) => if (c == f) AONE(bs:::List(C(c))) else AZERO
- case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _)))
- case ASEQ(bs, r1, r2) => {
- if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(mkepsBC(r1), bder(c, r2)))
- else ASEQ(bs, bder(c, r1), r2)
- }
- case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r))
-}
-\end{verbatim}
-\end{definition}
+
+The rest of the document is the residual from a previous doc and may be deleted.\\
\begin{definition}{bsimp}
\begin{verbatim}
def bsimp(r: ARexp): ARexp = r match {
Binary file ecp/.DS_Store has changed
Binary file ecp/cc-by.pdf has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/data.sty Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,111 @@
+% The data files, written on the first run.
+
+%% example a?{n} a{n}
+\begin{filecontents}{re-python.data}
+1 0.029
+5 0.029
+10 0.029
+15 0.032
+16 0.042
+17 0.042
+18 0.055
+19 0.084
+20 0.136
+21 0.248
+22 0.464
+23 0.899
+24 1.773
+25 3.505
+26 6.993
+27 14.503
+28 29.307
+#29 58.886
+\end{filecontents}
+
+
+\begin{filecontents}{re-python2.data}
+1 0.033
+5 0.036
+10 0.034
+15 0.036
+18 0.059
+19 0.084
+20 0.141
+21 0.248
+22 0.485
+23 0.878
+24 1.71
+25 3.40
+26 7.08
+27 14.12
+28 26.69
+\end{filecontents}
+
+%% example a?{n} a{n}
+\begin{filecontents}{re-ruby.data}
+1 0.00006
+#2 0.00003
+#3 0.00001
+#4 0.00001
+5 0.00001
+#6 0.00002
+#7 0.00002
+#8 0.00004
+#9 0.00007
+10 0.00013
+#11 0.00026
+#12 0.00055
+#13 0.00106
+#14 0.00196
+15 0.00378
+16 0.00764
+17 0.01606
+18 0.03094
+19 0.06508
+20 0.12420
+21 0.25393
+22 0.51449
+23 1.02174
+24 2.05998
+25 4.22514
+26 8.42479
+27 16.88678
+28 34.79653
+\end{filecontents}
+
+% JavaScript, example (a*)*b
+\begin{filecontents}{re-js.data}
+5 0.061
+10 0.061
+15 0.061
+20 0.070
+23 0.131
+25 0.308
+26 0.564
+28 1.994
+30 7.648
+31 15.881
+32 32.190
+\end{filecontents}
+
+% Java 8, example (a*)*b
+\begin{filecontents}{re-java.data}
+5 0.00298
+10 0.00418
+15 0.00996
+16 0.01710
+17 0.03492
+18 0.03303
+19 0.05084
+20 0.10177
+21 0.19960
+22 0.41159
+23 0.82234
+24 1.70251
+25 3.36112
+26 6.63998
+27 13.35120
+28 29.81185
+\end{filecontents}
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/ecoop_paper.aux Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,42 @@
+\relax
+\providecommand\hyper@newdestlabel[2]{}
+\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
+\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
+\global\let\oldcontentsline\contentsline
+\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
+\global\let\oldnewlabel\newlabel
+\gdef\newlabel#1#2{\newlabelxx{#1}#2}
+\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
+\AtEndDocument{\ifx\hyper@anchor\@undefined
+\let\contentsline\oldcontentsline
+\let\newlabel\oldnewlabel
+\fi}
+\fi}
+\global\let\hyper@last\relax
+\gdef\HyperFirstAtBeginDocument#1{#1}
+\providecommand\HyField@AuxAddToFields[1]{}
+\providecommand\HyField@AuxAddToCoFields[2]{}
+\citation{Davis18}
+\babel@aux{UKenglish}{}
+\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}{section.1}}
+\citation{AusafDyckhoffUrban2016}
+\citation{OkuiSuzuki2010}
+\citation{Vansummeren2006}
+\citation{CrashCourse2014}
+\citation{Kuklewicz}
+\citation{Sulzmann2014}
+\citation{Brzozowski1964}
+\@writefile{toc}{\contentsline {section}{\numberline {2}The Algorithms by Brzozowski, and Sulzmann and Lu}{2}{section.2}}
+\citation{Sulzmann2014}
+\citation{Sulzmann2014}
+\citation{AusafDyckhoffUrban2016}
+\citation{Antimirov95}
+\citation{Sulzmann2014}
+\@writefile{toc}{\contentsline {section}{\numberline {3}Simplification of Regular Expressions}{4}{section.3}}
+\citation{Sulzmann2014}
+\@writefile{toc}{\contentsline {section}{\numberline {4}Conclusion}{5}{section.4}}
+\bibstyle{plain}
+\bibdata{root}
+\newlabel{LastPage}{{}{6}{}{page.6}{}}
+\xdef\lastpage@lastpage{6}
+\xdef\lastpage@lastpageHy{6}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/ecoop_paper.log Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,1332 @@
+This is pdfTeX, Version 3.14159265-2.6-1.40.19 (TeX Live 2018) (preloaded format=pdflatex 2019.2.7) 25 JUN 2019 18:43
+entering extended mode
+ restricted \write18 enabled.
+ file:line:error style messages enabled.
+ %&-line parsing enabled.
+**ecoop_paper.tex
+(./ecoop_paper.tex
+LaTeX2e <2018-04-01> patch level 2
+Babel <3.18> and hyphenation patterns for 84 language(s) loaded.
+(./lipics.cls
+Document Class: lipics 2010/09/27 v1.1 LIPIcs articles
+(/usr/local/texlive/2018/texmf-dist/tex/latex/base/article.cls
+Document Class: article 2014/09/29 v1.4h Standard LaTeX document class
+(/usr/local/texlive/2018/texmf-dist/tex/latex/base/fleqn.clo
+File: fleqn.clo 2016/12/29 v1.2a Standard LaTeX option (flush left equations)
+\mathindent=\dimen102
+Applying: [2015/01/01] Make \[ robust on input line 50.
+LaTeX Info: Redefining \[ on input line 51.
+Already applied: [0000/00/00] Make \[ robust on input line 62.
+Applying: [2015/01/01] Make \] robust on input line 74.
+LaTeX Info: Redefining \] on input line 75.
+Already applied: [0000/00/00] Make \] robust on input line 83.
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/base/size10.clo
+File: size10.clo 2014/09/29 v1.4h Standard LaTeX file (size option)
+)
+\c@part=\count80
+\c@section=\count81
+\c@subsection=\count82
+\c@subsubsection=\count83
+\c@paragraph=\count84
+\c@subparagraph=\count85
+\c@figure=\count86
+\c@table=\count87
+\abovecaptionskip=\skip41
+\belowcaptionskip=\skip42
+\bibindent=\dimen103
+)
+\tocfile=\write3
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/base/inputenc.sty
+Package: inputenc 2018/04/06 v1.3b Input encoding file
+\inpenc@prehook=\toks14
+\inpenc@posthook=\toks15
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/lm/lmodern.sty
+Package: lmodern 2009/10/30 v1.6 Latin Modern Fonts
+LaTeX Font Info: Overwriting symbol font `operators' in version `normal'
+(Font) OT1/cmr/m/n --> OT1/lmr/m/n on input line 22.
+LaTeX Font Info: Overwriting symbol font `letters' in version `normal'
+(Font) OML/cmm/m/it --> OML/lmm/m/it on input line 23.
+LaTeX Font Info: Overwriting symbol font `symbols' in version `normal'
+(Font) OMS/cmsy/m/n --> OMS/lmsy/m/n on input line 24.
+LaTeX Font Info: Overwriting symbol font `largesymbols' in version `normal'
+(Font) OMX/cmex/m/n --> OMX/lmex/m/n on input line 25.
+LaTeX Font Info: Overwriting symbol font `operators' in version `bold'
+(Font) OT1/cmr/bx/n --> OT1/lmr/bx/n on input line 26.
+LaTeX Font Info: Overwriting symbol font `letters' in version `bold'
+(Font) OML/cmm/b/it --> OML/lmm/b/it on input line 27.
+LaTeX Font Info: Overwriting symbol font `symbols' in version `bold'
+(Font) OMS/cmsy/b/n --> OMS/lmsy/b/n on input line 28.
+LaTeX Font Info: Overwriting symbol font `largesymbols' in version `bold'
+(Font) OMX/cmex/m/n --> OMX/lmex/m/n on input line 29.
+LaTeX Font Info: Overwriting math alphabet `\mathbf' in version `normal'
+(Font) OT1/cmr/bx/n --> OT1/lmr/bx/n on input line 31.
+LaTeX Font Info: Overwriting math alphabet `\mathsf' in version `normal'
+(Font) OT1/cmss/m/n --> OT1/lmss/m/n on input line 32.
+LaTeX Font Info: Overwriting math alphabet `\mathit' in version `normal'
+(Font) OT1/cmr/m/it --> OT1/lmr/m/it on input line 33.
+LaTeX Font Info: Overwriting math alphabet `\mathtt' in version `normal'
+(Font) OT1/cmtt/m/n --> OT1/lmtt/m/n on input line 34.
+LaTeX Font Info: Overwriting math alphabet `\mathbf' in version `bold'
+(Font) OT1/cmr/bx/n --> OT1/lmr/bx/n on input line 35.
+LaTeX Font Info: Overwriting math alphabet `\mathsf' in version `bold'
+(Font) OT1/cmss/bx/n --> OT1/lmss/bx/n on input line 36.
+LaTeX Font Info: Overwriting math alphabet `\mathit' in version `bold'
+(Font) OT1/cmr/bx/it --> OT1/lmr/bx/it on input line 37.
+LaTeX Font Info: Overwriting math alphabet `\mathtt' in version `bold'
+(Font) OT1/cmtt/m/n --> OT1/lmtt/m/n on input line 38.
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/base/fontenc.sty
+Package: fontenc 2017/04/05 v2.0i Standard LaTeX package
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/base/t1enc.def
+File: t1enc.def 2017/04/05 v2.0i Standard LaTeX file
+LaTeX Font Info: Redeclaring font encoding T1 on input line 48.
+))
+(/usr/local/texlive/2018/texmf-dist/tex/latex/base/textcomp.sty
+Package: textcomp 2017/04/05 v2.0i Standard LaTeX package
+Package textcomp Info: Sub-encoding information:
+(textcomp) 5 = only ISO-Adobe without \textcurrency
+(textcomp) 4 = 5 + \texteuro
+(textcomp) 3 = 4 + \textohm
+(textcomp) 2 = 3 + \textestimated + \textcurrency
+(textcomp) 1 = TS1 - \textcircled - \t
+(textcomp) 0 = TS1 (full)
+(textcomp) Font families with sub-encoding setting implement
+(textcomp) only a restricted character set as indicated.
+(textcomp) Family '?' is the default used for unknown fonts.
+(textcomp) See the documentation for details.
+Package textcomp Info: Setting ? sub-encoding to TS1/1 on input line 79.
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/base/ts1enc.def
+File: ts1enc.def 2001/06/05 v3.0e (jk/car/fm) Standard LaTeX file
+Now handling font encoding TS1 ...
+... processing UTF-8 mapping file for font encoding TS1
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/base/ts1enc.dfu
+File: ts1enc.dfu 2018/04/05 v1.2c UTF-8 support for inputenc
+ defining Unicode char U+00A2 (decimal 162)
+ defining Unicode char U+00A3 (decimal 163)
+ defining Unicode char U+00A4 (decimal 164)
+ defining Unicode char U+00A5 (decimal 165)
+ defining Unicode char U+00A6 (decimal 166)
+ defining Unicode char U+00A7 (decimal 167)
+ defining Unicode char U+00A8 (decimal 168)
+ defining Unicode char U+00A9 (decimal 169)
+ defining Unicode char U+00AA (decimal 170)
+ defining Unicode char U+00AC (decimal 172)
+ defining Unicode char U+00AE (decimal 174)
+ defining Unicode char U+00AF (decimal 175)
+ defining Unicode char U+00B0 (decimal 176)
+ defining Unicode char U+00B1 (decimal 177)
+ defining Unicode char U+00B2 (decimal 178)
+ defining Unicode char U+00B3 (decimal 179)
+ defining Unicode char U+00B4 (decimal 180)
+ defining Unicode char U+00B5 (decimal 181)
+ defining Unicode char U+00B6 (decimal 182)
+ defining Unicode char U+00B7 (decimal 183)
+ defining Unicode char U+00B9 (decimal 185)
+ defining Unicode char U+00BA (decimal 186)
+ defining Unicode char U+00BC (decimal 188)
+ defining Unicode char U+00BD (decimal 189)
+ defining Unicode char U+00BE (decimal 190)
+ defining Unicode char U+00D7 (decimal 215)
+ defining Unicode char U+00F7 (decimal 247)
+ defining Unicode char U+0192 (decimal 402)
+ defining Unicode char U+02C7 (decimal 711)
+ defining Unicode char U+02D8 (decimal 728)
+ defining Unicode char U+02DD (decimal 733)
+ defining Unicode char U+0E3F (decimal 3647)
+ defining Unicode char U+2016 (decimal 8214)
+ defining Unicode char U+2020 (decimal 8224)
+ defining Unicode char U+2021 (decimal 8225)
+ defining Unicode char U+2022 (decimal 8226)
+ defining Unicode char U+2030 (decimal 8240)
+ defining Unicode char U+2031 (decimal 8241)
+ defining Unicode char U+203B (decimal 8251)
+ defining Unicode char U+203D (decimal 8253)
+ defining Unicode char U+2044 (decimal 8260)
+ defining Unicode char U+204E (decimal 8270)
+ defining Unicode char U+2052 (decimal 8274)
+ defining Unicode char U+20A1 (decimal 8353)
+ defining Unicode char U+20A4 (decimal 8356)
+ defining Unicode char U+20A6 (decimal 8358)
+ defining Unicode char U+20A9 (decimal 8361)
+ defining Unicode char U+20AB (decimal 8363)
+ defining Unicode char U+20AC (decimal 8364)
+ defining Unicode char U+20B1 (decimal 8369)
+ defining Unicode char U+2103 (decimal 8451)
+ defining Unicode char U+2116 (decimal 8470)
+ defining Unicode char U+2117 (decimal 8471)
+ defining Unicode char U+211E (decimal 8478)
+ defining Unicode char U+2120 (decimal 8480)
+ defining Unicode char U+2122 (decimal 8482)
+ defining Unicode char U+2126 (decimal 8486)
+ defining Unicode char U+2127 (decimal 8487)
+ defining Unicode char U+212E (decimal 8494)
+ defining Unicode char U+2190 (decimal 8592)
+ defining Unicode char U+2191 (decimal 8593)
+ defining Unicode char U+2192 (decimal 8594)
+ defining Unicode char U+2193 (decimal 8595)
+ defining Unicode char U+2329 (decimal 9001)
+ defining Unicode char U+232A (decimal 9002)
+ defining Unicode char U+2422 (decimal 9250)
+ defining Unicode char U+25E6 (decimal 9702)
+ defining Unicode char U+25EF (decimal 9711)
+ defining Unicode char U+266A (decimal 9834)
+ defining Unicode char U+FEFF (decimal 65279)
+))
+LaTeX Info: Redefining \oldstylenums on input line 334.
+Package textcomp Info: Setting cmr sub-encoding to TS1/0 on input line 349.
+Package textcomp Info: Setting cmss sub-encoding to TS1/0 on input line 350.
+Package textcomp Info: Setting cmtt sub-encoding to TS1/0 on input line 351.
+Package textcomp Info: Setting cmvtt sub-encoding to TS1/0 on input line 352.
+Package textcomp Info: Setting cmbr sub-encoding to TS1/0 on input line 353.
+Package textcomp Info: Setting cmtl sub-encoding to TS1/0 on input line 354.
+Package textcomp Info: Setting ccr sub-encoding to TS1/0 on input line 355.
+Package textcomp Info: Setting ptm sub-encoding to TS1/4 on input line 356.
+Package textcomp Info: Setting pcr sub-encoding to TS1/4 on input line 357.
+Package textcomp Info: Setting phv sub-encoding to TS1/4 on input line 358.
+Package textcomp Info: Setting ppl sub-encoding to TS1/3 on input line 359.
+Package textcomp Info: Setting pag sub-encoding to TS1/4 on input line 360.
+Package textcomp Info: Setting pbk sub-encoding to TS1/4 on input line 361.
+Package textcomp Info: Setting pnc sub-encoding to TS1/4 on input line 362.
+Package textcomp Info: Setting pzc sub-encoding to TS1/4 on input line 363.
+Package textcomp Info: Setting bch sub-encoding to TS1/4 on input line 364.
+Package textcomp Info: Setting put sub-encoding to TS1/5 on input line 365.
+Package textcomp Info: Setting uag sub-encoding to TS1/5 on input line 366.
+Package textcomp Info: Setting ugq sub-encoding to TS1/5 on input line 367.
+Package textcomp Info: Setting ul8 sub-encoding to TS1/4 on input line 368.
+Package textcomp Info: Setting ul9 sub-encoding to TS1/4 on input line 369.
+Package textcomp Info: Setting augie sub-encoding to TS1/5 on input line 370.
+Package textcomp Info: Setting dayrom sub-encoding to TS1/3 on input line 371.
+Package textcomp Info: Setting dayroms sub-encoding to TS1/3 on input line 372.
+
+Package textcomp Info: Setting pxr sub-encoding to TS1/0 on input line 373.
+Package textcomp Info: Setting pxss sub-encoding to TS1/0 on input line 374.
+Package textcomp Info: Setting pxtt sub-encoding to TS1/0 on input line 375.
+Package textcomp Info: Setting txr sub-encoding to TS1/0 on input line 376.
+Package textcomp Info: Setting txss sub-encoding to TS1/0 on input line 377.
+Package textcomp Info: Setting txtt sub-encoding to TS1/0 on input line 378.
+Package textcomp Info: Setting lmr sub-encoding to TS1/0 on input line 379.
+Package textcomp Info: Setting lmdh sub-encoding to TS1/0 on input line 380.
+Package textcomp Info: Setting lmss sub-encoding to TS1/0 on input line 381.
+Package textcomp Info: Setting lmssq sub-encoding to TS1/0 on input line 382.
+Package textcomp Info: Setting lmvtt sub-encoding to TS1/0 on input line 383.
+Package textcomp Info: Setting lmtt sub-encoding to TS1/0 on input line 384.
+Package textcomp Info: Setting qhv sub-encoding to TS1/0 on input line 385.
+Package textcomp Info: Setting qag sub-encoding to TS1/0 on input line 386.
+Package textcomp Info: Setting qbk sub-encoding to TS1/0 on input line 387.
+Package textcomp Info: Setting qcr sub-encoding to TS1/0 on input line 388.
+Package textcomp Info: Setting qcs sub-encoding to TS1/0 on input line 389.
+Package textcomp Info: Setting qpl sub-encoding to TS1/0 on input line 390.
+Package textcomp Info: Setting qtm sub-encoding to TS1/0 on input line 391.
+Package textcomp Info: Setting qzc sub-encoding to TS1/0 on input line 392.
+Package textcomp Info: Setting qhvc sub-encoding to TS1/0 on input line 393.
+Package textcomp Info: Setting futs sub-encoding to TS1/4 on input line 394.
+Package textcomp Info: Setting futx sub-encoding to TS1/4 on input line 395.
+Package textcomp Info: Setting futj sub-encoding to TS1/4 on input line 396.
+Package textcomp Info: Setting hlh sub-encoding to TS1/3 on input line 397.
+Package textcomp Info: Setting hls sub-encoding to TS1/3 on input line 398.
+Package textcomp Info: Setting hlst sub-encoding to TS1/3 on input line 399.
+Package textcomp Info: Setting hlct sub-encoding to TS1/5 on input line 400.
+Package textcomp Info: Setting hlx sub-encoding to TS1/5 on input line 401.
+Package textcomp Info: Setting hlce sub-encoding to TS1/5 on input line 402.
+Package textcomp Info: Setting hlcn sub-encoding to TS1/5 on input line 403.
+Package textcomp Info: Setting hlcw sub-encoding to TS1/5 on input line 404.
+Package textcomp Info: Setting hlcf sub-encoding to TS1/5 on input line 405.
+Package textcomp Info: Setting pplx sub-encoding to TS1/3 on input line 406.
+Package textcomp Info: Setting pplj sub-encoding to TS1/3 on input line 407.
+Package textcomp Info: Setting ptmx sub-encoding to TS1/4 on input line 408.
+Package textcomp Info: Setting ptmj sub-encoding to TS1/4 on input line 409.
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/amsfonts/eucal.sty
+Package: eucal 2009/06/22 v3.00 Euler Script fonts
+LaTeX Font Info: Overwriting math alphabet `\EuScript' in version `bold'
+(Font) U/eus/m/n --> U/eus/b/n on input line 33.
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/amsfonts/amssymb.sty
+Package: amssymb 2013/01/14 v3.01 AMS font symbols
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/amsfonts/amsfonts.sty
+Package: amsfonts 2013/01/14 v3.01 Basic AMSFonts support
+\@emptytoks=\toks16
+\symAMSa=\mathgroup4
+\symAMSb=\mathgroup5
+LaTeX Font Info: Overwriting math alphabet `\mathfrak' in version `bold'
+(Font) U/euf/m/n --> U/euf/b/n on input line 106.
+))
+(/usr/local/texlive/2018/texmf-dist/tex/latex/soul/soul.sty
+Package: soul 2003/11/17 v2.4 letterspacing/underlining (mf)
+\SOUL@word=\toks17
+\SOUL@lasttoken=\toks18
+\SOUL@cmds=\toks19
+\SOUL@buffer=\toks20
+\SOUL@token=\toks21
+\SOUL@spaceskip=\skip43
+\SOUL@ttwidth=\dimen104
+\SOUL@uldp=\dimen105
+\SOUL@ulht=\dimen106
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/graphics/color.sty
+Package: color 2016/07/10 v1.1e Standard LaTeX Color (DPC)
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/graphics-cfg/color.cfg
+File: color.cfg 2016/01/02 v1.6 sample color configuration
+)
+Package color Info: Driver file: pdftex.def on input line 147.
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/graphics-def/pdftex.def
+File: pdftex.def 2018/01/08 v1.0l Graphics/color driver for pdftex
+))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/babel/babel.sty
+Package: babel 2018/02/14 3.18 The Babel package
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/babel/switch.def
+File: switch.def 2018/02/14 3.18 Babel switching mechanism
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/babel-english/UKenglish.ldf
+Language: UKenglish 2017/06/06 v3.3r English support from the babel system
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/babel-english/english.ldf
+Language: english 2017/06/06 v3.3r English support from the babel system
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/babel/babel.def
+File: babel.def 2018/02/14 3.18 Babel common definitions
+\babel@savecnt=\count88
+\U@D=\dimen107
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/babel/txtbabel.def)
+\bbl@dirlevel=\count89
+)
+\l@canadian = a dialect from \language\l@american
+\l@australian = a dialect from \language\l@british
+\l@newzealand = a dialect from \language\l@british
+)))
+(/usr/local/texlive/2018/texmf-dist/tex/latex/amsmath/amsmath.sty
+Package: amsmath 2017/09/02 v2.17a AMS math features
+\@mathmargin=\skip44
+
+For additional information on amsmath, use the `?' option.
+(/usr/local/texlive/2018/texmf-dist/tex/latex/amsmath/amstext.sty
+Package: amstext 2000/06/29 v2.01 AMS text
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/amsmath/amsgen.sty
+File: amsgen.sty 1999/11/30 v2.0 generic functions
+\@emptytoks=\toks22
+\ex@=\dimen108
+))
+(/usr/local/texlive/2018/texmf-dist/tex/latex/amsmath/amsbsy.sty
+Package: amsbsy 1999/11/29 v1.2d Bold Symbols
+\pmbraise@=\dimen109
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/amsmath/amsopn.sty
+Package: amsopn 2016/03/08 v2.02 operator names
+)
+\inf@bad=\count90
+LaTeX Info: Redefining \frac on input line 213.
+\uproot@=\count91
+\leftroot@=\count92
+LaTeX Info: Redefining \overline on input line 375.
+\classnum@=\count93
+\DOTSCASE@=\count94
+LaTeX Info: Redefining \ldots on input line 472.
+LaTeX Info: Redefining \dots on input line 475.
+LaTeX Info: Redefining \cdots on input line 596.
+\Mathstrutbox@=\box26
+\strutbox@=\box27
+\big@size=\dimen110
+LaTeX Font Info: Redeclaring font encoding OML on input line 712.
+LaTeX Font Info: Redeclaring font encoding OMS on input line 713.
+\macc@depth=\count95
+\c@MaxMatrixCols=\count96
+\dotsspace@=\muskip10
+\c@parentequation=\count97
+\dspbrk@lvl=\count98
+\tag@help=\toks23
+\row@=\count99
+\column@=\count100
+\maxfields@=\count101
+\andhelp@=\toks24
+\eqnshift@=\dimen111
+\alignsep@=\dimen112
+\tagshift@=\dimen113
+\tagwidth@=\dimen114
+\totwidth@=\dimen115
+\lineht@=\dimen116
+\@envbody=\toks25
+\multlinegap=\skip45
+\multlinetaggap=\skip46
+\mathdisplay@stack=\toks26
+LaTeX Info: Redefining \[ on input line 2817.
+LaTeX Info: Redefining \] on input line 2818.
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/amscls/amsthm.sty
+Package: amsthm 2017/10/31 v2.20.4
+\thm@style=\toks27
+\thm@bodyfont=\toks28
+\thm@headfont=\toks29
+\thm@notefont=\toks30
+\thm@headpunct=\toks31
+\thm@preskip=\skip47
+\thm@postskip=\skip48
+\thm@headsep=\skip49
+\dth@everypar=\toks32
+)
+\c@theorem=\count102
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/graphics/graphicx.sty
+Package: graphicx 2017/06/01 v1.1a Enhanced LaTeX Graphics (DPC,SPQR)
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/graphics/keyval.sty
+Package: keyval 2014/10/28 v1.15 key=value parser (DPC)
+\KV@toks@=\toks33
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/graphics/graphics.sty
+Package: graphics 2017/06/25 v1.2c Standard LaTeX Graphics (DPC,SPQR)
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/graphics/trig.sty
+Package: trig 2016/01/03 v1.10 sin cos tan (DPC)
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/graphics-cfg/graphics.cfg
+File: graphics.cfg 2016/06/04 v1.11 sample graphics configuration
+)
+Package graphics Info: Driver file: pdftex.def on input line 99.
+)
+\Gin@req@height=\dimen117
+\Gin@req@width=\dimen118
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/tools/array.sty
+Package: array 2018/04/07 v2.4g Tabular extension package (FMi)
+\col@sep=\dimen119
+\ar@mcellbox=\box28
+\extrarowheight=\dimen120
+\NC@list=\toks34
+\extratabsurround=\skip50
+\backup@length=\skip51
+\ar@cellbox=\box29
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/multirow/multirow.sty
+Package: multirow 2016/11/25 v2.2 Span multiple rows of a table
+\multirow@colwidth=\skip52
+\multirow@cntb=\count103
+\multirow@dima=\skip53
+\bigstrutjot=\dimen121
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/tools/tabularx.sty
+Package: tabularx 2016/02/03 v2.11b `tabularx' package (DPC)
+\TX@col@width=\dimen122
+\TX@old@table=\dimen123
+\TX@old@col=\dimen124
+\TX@target=\dimen125
+\TX@delta=\dimen126
+\TX@cols=\count104
+\TX@ftn=\toks35
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/threeparttable/threeparttable.sty
+Package: threeparttable 2003/06/13 v 3.0
+\@tempboxb=\box30
+) (/usr/local/texlive/2018/texmf-dist/tex/latex/listings/listings.sty
+\lst@mode=\count105
+\lst@gtempboxa=\box31
+\lst@token=\toks36
+\lst@length=\count106
+\lst@currlwidth=\dimen127
+\lst@column=\count107
+\lst@pos=\count108
+\lst@lostspace=\dimen128
+\lst@width=\dimen129
+\lst@newlines=\count109
+\lst@lineno=\count110
+\lst@maxwidth=\dimen130
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/listings/lstmisc.sty
+File: lstmisc.sty 2015/06/04 1.6 (Carsten Heinz)
+\c@lstnumber=\count111
+\lst@skipnumbers=\count112
+\lst@framebox=\box32
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/listings/listings.cfg
+File: listings.cfg 2015/06/04 1.6 listings configuration
+))
+Package: listings 2015/06/04 1.6 (Carsten Heinz)
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/lastpage/lastpage.sty
+Package: lastpage 2015/03/29 v1.2m Refers to last page's name (HMM; JPG)
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/doi/doi.sty
+Package: doi 2007/07/24 handle doi numbers
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/hyperref/hyperref.sty
+Package: hyperref 2018/02/06 v6.86b Hypertext links for LaTeX
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/oberdiek/hobsub-hyperref.sty
+Package: hobsub-hyperref 2016/05/16 v1.14 Bundle oberdiek, subset hyperref (HO)
+
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/oberdiek/hobsub-generic.sty
+Package: hobsub-generic 2016/05/16 v1.14 Bundle oberdiek, subset generic (HO)
+Package: hobsub 2016/05/16 v1.14 Construct package bundles (HO)
+Package: infwarerr 2016/05/16 v1.4 Providing info/warning/error messages (HO)
+Package: ltxcmds 2016/05/16 v1.23 LaTeX kernel commands for general use (HO)
+Package: ifluatex 2016/05/16 v1.4 Provides the ifluatex switch (HO)
+Package ifluatex Info: LuaTeX not detected.
+Package: ifvtex 2016/05/16 v1.6 Detect VTeX and its facilities (HO)
+Package ifvtex Info: VTeX not detected.
+Package: intcalc 2016/05/16 v1.2 Expandable calculations with integers (HO)
+Package: ifpdf 2017/03/15 v3.2 Provides the ifpdf switch
+Package: etexcmds 2016/05/16 v1.6 Avoid name clashes with e-TeX commands (HO)
+Package etexcmds Info: Could not find \expanded.
+(etexcmds) That can mean that you are not using pdfTeX 1.50 or
+(etexcmds) that some package has redefined \expanded.
+(etexcmds) In the latter case, load this package earlier.
+Package: kvsetkeys 2016/05/16 v1.17 Key value parser (HO)
+Package: kvdefinekeys 2016/05/16 v1.4 Define keys (HO)
+Package: pdftexcmds 2018/01/30 v0.27 Utility functions of pdfTeX for LuaTeX (HO
+)
+Package pdftexcmds Info: LuaTeX not detected.
+Package pdftexcmds Info: \pdf@primitive is available.
+Package pdftexcmds Info: \pdf@ifprimitive is available.
+Package pdftexcmds Info: \pdfdraftmode found.
+Package: pdfescape 2016/05/16 v1.14 Implements pdfTeX's escape features (HO)
+Package: bigintcalc 2016/05/16 v1.4 Expandable calculations on big integers (HO
+)
+Package: bitset 2016/05/16 v1.2 Handle bit-vector datatype (HO)
+Package: uniquecounter 2016/05/16 v1.3 Provide unlimited unique counter (HO)
+)
+Package hobsub Info: Skipping package `hobsub' (already loaded).
+Package: letltxmacro 2016/05/16 v1.5 Let assignment for LaTeX macros (HO)
+Package: hopatch 2016/05/16 v1.3 Wrapper for package hooks (HO)
+Package: xcolor-patch 2016/05/16 xcolor patch
+Package: atveryend 2016/05/16 v1.9 Hooks at the very end of document (HO)
+Package atveryend Info: \enddocument detected (standard20110627).
+Package: atbegshi 2016/06/09 v1.18 At begin shipout hook (HO)
+Package: refcount 2016/05/16 v3.5 Data extraction from label references (HO)
+Package: hycolor 2016/05/16 v1.8 Color options for hyperref/bookmark (HO)
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/ifxetex/ifxetex.sty
+Package: ifxetex 2010/09/12 v0.6 Provides ifxetex conditional
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/oberdiek/auxhook.sty
+Package: auxhook 2016/05/16 v1.4 Hooks for auxiliary files (HO)
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/oberdiek/kvoptions.sty
+Package: kvoptions 2016/05/16 v3.12 Key value format for package options (HO)
+)
+\@linkdim=\dimen131
+\Hy@linkcounter=\count113
+\Hy@pagecounter=\count114
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/hyperref/pd1enc.def
+File: pd1enc.def 2018/02/06 v6.86b Hyperref: PDFDocEncoding definition (HO)
+Now handling font encoding PD1 ...
+... no UTF-8 mapping file for font encoding PD1
+)
+\Hy@SavedSpaceFactor=\count115
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/latexconfig/hyperref.cfg
+File: hyperref.cfg 2002/06/06 v1.2 hyperref configuration of TeXLive
+)
+Package hyperref Info: Hyper figures OFF on input line 4509.
+Package hyperref Info: Link nesting OFF on input line 4514.
+Package hyperref Info: Hyper index ON on input line 4517.
+Package hyperref Info: Plain pages OFF on input line 4524.
+Package hyperref Info: Backreferencing OFF on input line 4529.
+Package hyperref Info: Implicit mode ON; LaTeX internals redefined.
+Package hyperref Info: Bookmarks ON on input line 4762.
+\c@Hy@tempcnt=\count116
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/url/url.sty
+\Urlmuskip=\muskip11
+Package: url 2013/09/16 ver 3.4 Verb mode for urls, etc.
+)
+LaTeX Info: Redefining \url on input line 5115.
+\XeTeXLinkMargin=\dimen132
+\Fld@menulength=\count117
+\Field@Width=\dimen133
+\Fld@charsize=\dimen134
+Package hyperref Info: Hyper figures OFF on input line 6369.
+Package hyperref Info: Link nesting OFF on input line 6374.
+Package hyperref Info: Hyper index ON on input line 6377.
+Package hyperref Info: backreferencing OFF on input line 6384.
+Package hyperref Info: Link coloring OFF on input line 6389.
+Package hyperref Info: Link coloring with OCG OFF on input line 6394.
+Package hyperref Info: PDF/A mode OFF on input line 6399.
+LaTeX Info: Redefining \ref on input line 6439.
+LaTeX Info: Redefining \pageref on input line 6443.
+\Hy@abspage=\count118
+\c@Item=\count119
+\c@Hfootnote=\count120
+)
+Package hyperref Info: Driver (autodetected): hpdftex.
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/hyperref/hpdftex.def
+File: hpdftex.def 2018/02/06 v6.86b Hyperref driver for pdfTeX
+\Fld@listcount=\count121
+\c@bookmark@seq@number=\count122
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/oberdiek/rerunfilecheck.sty
+Package: rerunfilecheck 2016/05/16 v1.8 Rerun checks for auxiliary files (HO)
+Package uniquecounter Info: New unique counter `rerunfilecheck' on input line 2
+82.
+)
+\Hy@SectionHShift=\skip54
+))
+(/usr/local/texlive/2018/texmf-dist/tex/latex/caption/caption.sty
+Package: caption 2016/02/21 v3.3-144 Customizing captions (AR)
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/caption/caption3.sty
+Package: caption3 2016/05/22 v1.7-166 caption3 kernel (AR)
+Package caption3 Info: TeX engine: e-TeX on input line 67.
+\captionmargin=\dimen135
+\captionmargin@=\dimen136
+\captionwidth=\dimen137
+\caption@tempdima=\dimen138
+\caption@indent=\dimen139
+\caption@parindent=\dimen140
+\caption@hangindent=\dimen141
+)
+\c@ContinuedFloat=\count123
+Package caption Info: hyperref package is loaded.
+Package caption Info: listings package is loaded.
+Package caption Info: threeparttable package is loaded.
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/graphics/rotating.sty
+Package: rotating 2016/08/11 v2.16d rotated objects in LaTeX
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/base/ifthen.sty
+Package: ifthen 2014/09/29 v1.1c Standard LaTeX ifthen package (DPC)
+)
+\c@r@tfl@t=\count124
+\rotFPtop=\skip55
+\rotFPbot=\skip56
+\rot@float@box=\box33
+\rot@mess@toks=\toks37
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/subfig/subfig.sty
+Package: subfig 2005/06/28 ver: 1.3 subfig package
+\c@KVtest=\count125
+\sf@farskip=\skip57
+\sf@captopadj=\dimen142
+\sf@capskip=\skip58
+\sf@nearskip=\skip59
+\c@subfigure=\count126
+\c@subfigure@save=\count127
+\c@lofdepth=\count128
+\c@subtable=\count129
+\c@subtable@save=\count130
+\c@lotdepth=\count131
+\sf@top=\skip60
+\sf@bottom=\skip61
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/preprint/authblk.sty
+Package: authblk 2001/02/27 1.3 (PWD)
+\affilsep=\skip62
+\@affilsep=\skip63
+\c@Maxaffil=\count132
+\c@authors=\count133
+\c@affil=\count134
+))
+(./graphic.sty
+(/usr/local/texlive/2018/texmf-dist/tex/latex/pgf/frontendlayer/tikz.sty
+(/usr/local/texlive/2018/texmf-dist/tex/latex/pgf/basiclayer/pgf.sty
+(/usr/local/texlive/2018/texmf-dist/tex/latex/pgf/utilities/pgfrcs.sty
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/utilities/pgfutil-common.te
+x
+\pgfutil@everybye=\toks38
+\pgfutil@tempdima=\dimen143
+\pgfutil@tempdimb=\dimen144
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/utilities/pgfutil-common-li
+sts.tex))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/utilities/pgfutil-latex.def
+\pgfutil@abb=\box34
+(/usr/local/texlive/2018/texmf-dist/tex/latex/ms/everyshi.sty
+Package: everyshi 2001/05/15 v3.00 EveryShipout Package (MS)
+))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/utilities/pgfrcs.code.tex
+Package: pgfrcs 2015/08/07 v3.0.1a (rcs-revision 1.31)
+))
+Package: pgf 2015/08/07 v3.0.1a (rcs-revision 1.15)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/pgf/basiclayer/pgfcore.sty
+(/usr/local/texlive/2018/texmf-dist/tex/latex/pgf/systemlayer/pgfsys.sty
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/systemlayer/pgfsys.code.tex
+Package: pgfsys 2014/07/09 v3.0.1a (rcs-revision 1.48)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/utilities/pgfkeys.code.tex
+\pgfkeys@pathtoks=\toks39
+\pgfkeys@temptoks=\toks40
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/utilities/pgfkeysfiltered.c
+ode.tex
+\pgfkeys@tmptoks=\toks41
+))
+\pgf@x=\dimen145
+\pgf@y=\dimen146
+\pgf@xa=\dimen147
+\pgf@ya=\dimen148
+\pgf@xb=\dimen149
+\pgf@yb=\dimen150
+\pgf@xc=\dimen151
+\pgf@yc=\dimen152
+\w@pgf@writea=\write4
+\r@pgf@reada=\read1
+\c@pgf@counta=\count135
+\c@pgf@countb=\count136
+\c@pgf@countc=\count137
+\c@pgf@countd=\count138
+\t@pgf@toka=\toks42
+\t@pgf@tokb=\toks43
+\t@pgf@tokc=\toks44
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/systemlayer/pgf.cfg
+File: pgf.cfg 2008/05/14 (rcs-revision 1.7)
+)
+Driver file for pgf: pgfsys-pdftex.def
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/systemlayer/pgfsys-pdftex.d
+ef
+File: pgfsys-pdftex.def 2014/10/11 (rcs-revision 1.35)
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/systemlayer/pgfsys-common-p
+df.def
+File: pgfsys-common-pdf.def 2013/10/10 (rcs-revision 1.13)
+)))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/systemlayer/pgfsyssoftpath.
+code.tex
+File: pgfsyssoftpath.code.tex 2013/09/09 (rcs-revision 1.9)
+\pgfsyssoftpath@smallbuffer@items=\count139
+\pgfsyssoftpath@bigbuffer@items=\count140
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/systemlayer/pgfsysprotocol.
+code.tex
+File: pgfsysprotocol.code.tex 2006/10/16 (rcs-revision 1.4)
+)) (/usr/local/texlive/2018/texmf-dist/tex/latex/xcolor/xcolor.sty
+Package: xcolor 2016/05/11 v2.12 LaTeX color extensions (UK)
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/graphics-cfg/color.cfg
+File: color.cfg 2016/01/02 v1.6 sample color configuration
+)
+Package xcolor Info: Driver file: pdftex.def on input line 225.
+LaTeX Info: Redefining \color on input line 709.
+Package xcolor Info: Model `cmy' substituted by `cmy0' on input line 1348.
+Package xcolor Info: Model `hsb' substituted by `rgb' on input line 1352.
+Package xcolor Info: Model `RGB' extended on input line 1364.
+Package xcolor Info: Model `HTML' substituted by `rgb' on input line 1366.
+Package xcolor Info: Model `Hsb' substituted by `hsb' on input line 1367.
+Package xcolor Info: Model `tHsb' substituted by `hsb' on input line 1368.
+Package xcolor Info: Model `HSB' substituted by `hsb' on input line 1369.
+Package xcolor Info: Model `Gray' substituted by `gray' on input line 1370.
+Package xcolor Info: Model `wave' substituted by `hsb' on input line 1371.
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcore.code.tex
+Package: pgfcore 2010/04/11 v3.0.1a (rcs-revision 1.7)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathcalc.code.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathutil.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathparser.code.tex
+\pgfmath@dimen=\dimen153
+\pgfmath@count=\count141
+\pgfmath@box=\box35
+\pgfmath@toks=\toks45
+\pgfmath@stack@operand=\toks46
+\pgfmath@stack@operation=\toks47
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.code.
+tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.basic
+.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.trigo
+nometric.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.rando
+m.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.compa
+rison.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.base.
+code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.round
+.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.misc.
+code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.integ
+erarithmetics.code.tex)))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmathfloat.code.tex
+\c@pgfmathroundto@lastzeros=\count142
+))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepoints.co
+de.tex
+File: pgfcorepoints.code.tex 2013/10/07 (rcs-revision 1.27)
+\pgf@picminx=\dimen154
+\pgf@picmaxx=\dimen155
+\pgf@picminy=\dimen156
+\pgf@picmaxy=\dimen157
+\pgf@pathminx=\dimen158
+\pgf@pathmaxx=\dimen159
+\pgf@pathminy=\dimen160
+\pgf@pathmaxy=\dimen161
+\pgf@xx=\dimen162
+\pgf@xy=\dimen163
+\pgf@yx=\dimen164
+\pgf@yy=\dimen165
+\pgf@zx=\dimen166
+\pgf@zy=\dimen167
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathconst
+ruct.code.tex
+File: pgfcorepathconstruct.code.tex 2013/10/07 (rcs-revision 1.29)
+\pgf@path@lastx=\dimen168
+\pgf@path@lasty=\dimen169
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathusage
+.code.tex
+File: pgfcorepathusage.code.tex 2014/11/02 (rcs-revision 1.24)
+\pgf@shorten@end@additional=\dimen170
+\pgf@shorten@start@additional=\dimen171
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcorescopes.co
+de.tex
+File: pgfcorescopes.code.tex 2015/05/08 (rcs-revision 1.46)
+\pgfpic=\box36
+\pgf@hbox=\box37
+\pgf@layerbox@main=\box38
+\pgf@picture@serial@count=\count143
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcoregraphicst
+ate.code.tex
+File: pgfcoregraphicstate.code.tex 2014/11/02 (rcs-revision 1.12)
+\pgflinewidth=\dimen172
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcoretransform
+ations.code.tex
+File: pgfcoretransformations.code.tex 2015/08/07 (rcs-revision 1.20)
+\pgf@pt@x=\dimen173
+\pgf@pt@y=\dimen174
+\pgf@pt@temp=\dimen175
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcorequick.cod
+e.tex
+File: pgfcorequick.code.tex 2008/10/09 (rcs-revision 1.3)
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreobjects.c
+ode.tex
+File: pgfcoreobjects.code.tex 2006/10/11 (rcs-revision 1.2)
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathproce
+ssing.code.tex
+File: pgfcorepathprocessing.code.tex 2013/09/09 (rcs-revision 1.9)
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcorearrows.co
+de.tex
+File: pgfcorearrows.code.tex 2015/05/14 (rcs-revision 1.43)
+\pgfarrowsep=\dimen176
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreshade.cod
+e.tex
+File: pgfcoreshade.code.tex 2013/07/15 (rcs-revision 1.15)
+\pgf@max=\dimen177
+\pgf@sys@shading@range@num=\count144
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreimage.cod
+e.tex
+File: pgfcoreimage.code.tex 2013/07/15 (rcs-revision 1.18)
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreexternal.
+code.tex
+File: pgfcoreexternal.code.tex 2014/07/09 (rcs-revision 1.21)
+\pgfexternal@startupbox=\box39
+))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcorelayers.co
+de.tex
+File: pgfcorelayers.code.tex 2013/07/18 (rcs-revision 1.7)
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcoretranspare
+ncy.code.tex
+File: pgfcoretransparency.code.tex 2013/09/30 (rcs-revision 1.5)
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepatterns.
+code.tex
+File: pgfcorepatterns.code.tex 2013/11/07 (rcs-revision 1.5)
+)))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/modules/pgfmoduleshapes.cod
+e.tex
+File: pgfmoduleshapes.code.tex 2014/03/21 (rcs-revision 1.35)
+\pgfnodeparttextbox=\box40
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/modules/pgfmoduleplot.code.
+tex
+File: pgfmoduleplot.code.tex 2015/08/03 (rcs-revision 1.13)
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version
+-0-65.sty
+Package: pgfcomp-version-0-65 2007/07/03 v3.0.1a (rcs-revision 1.7)
+\pgf@nodesepstart=\dimen178
+\pgf@nodesepend=\dimen179
+)
+(/usr/local/texlive/2018/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version
+-1-18.sty
+Package: pgfcomp-version-1-18 2007/07/23 v3.0.1a (rcs-revision 1.1)
+))
+(/usr/local/texlive/2018/texmf-dist/tex/latex/pgf/utilities/pgffor.sty
+(/usr/local/texlive/2018/texmf-dist/tex/latex/pgf/utilities/pgfkeys.sty
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/utilities/pgfkeys.code.tex)
+) (/usr/local/texlive/2018/texmf-dist/tex/latex/pgf/math/pgfmath.sty
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/utilities/pgffor.code.tex
+Package: pgffor 2013/12/13 v3.0.1a (rcs-revision 1.25)
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex)
+\pgffor@iter=\dimen180
+\pgffor@skip=\dimen181
+\pgffor@stack=\toks48
+\pgffor@toks=\toks49
+))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/frontendlayer/tikz/tikz.cod
+e.tex
+Package: tikz 2015/08/07 v3.0.1a (rcs-revision 1.151)
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/libraries/pgflibraryplothan
+dlers.code.tex
+File: pgflibraryplothandlers.code.tex 2013/08/31 v3.0.1a (rcs-revision 1.20)
+\pgf@plot@mark@count=\count145
+\pgfplotmarksize=\dimen182
+)
+\tikz@lastx=\dimen183
+\tikz@lasty=\dimen184
+\tikz@lastxsaved=\dimen185
+\tikz@lastysaved=\dimen186
+\tikzleveldistance=\dimen187
+\tikzsiblingdistance=\dimen188
+\tikz@figbox=\box41
+\tikz@figbox@bg=\box42
+\tikz@tempbox=\box43
+\tikz@tempbox@bg=\box44
+\tikztreelevel=\count146
+\tikznumberofchildren=\count147
+\tikznumberofcurrentchild=\count148
+\tikz@fig@count=\count149
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/modules/pgfmodulematrix.cod
+e.tex
+File: pgfmodulematrix.code.tex 2013/09/17 (rcs-revision 1.8)
+\pgfmatrixcurrentrow=\count150
+\pgfmatrixcurrentcolumn=\count151
+\pgf@matrix@numberofcolumns=\count152
+)
+\tikz@expandcount=\count153
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/frontendlayer/tikz/librarie
+s/tikzlibrarytopaths.code.tex
+File: tikzlibrarytopaths.code.tex 2008/06/17 v3.0.1a (rcs-revision 1.2)
+)))
+(/usr/local/texlive/2018/texmf-dist/tex/latex/pgfplots/pgfplots.sty
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplots.revision.tex)
+Package: pgfplots 2018/03/28 v1.16 Data Visualization (1.16)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplots.code.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplotscore.code.tex
+\t@pgfplots@toka=\toks50
+\t@pgfplots@tokb=\toks51
+\t@pgfplots@tokc=\toks52
+\pgfplots@tmpa=\dimen189
+\c@pgfplots@coordindex=\count154
+\c@pgfplots@scanlineindex=\count155
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/sys/pgfplotssysgeneric
+.code.tex))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/libs/pgfplotslibrary.c
+ode.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/oldpgfcompatib/pgfplot
+soldpgfsupp_loader.code.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/libraries/pgflibraryfpu.cod
+e.tex)
+Package pgfplots: loading complementary arithmetics for your pgf version...
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/oldpgfcompatib/pgfplot
+soldpgfsupp_pgflibraryfpu.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/oldpgfcompatib/pgfplot
+soldpgfsupp_pgfmathfloat.code.tex
+\c@pgfmathroundto@lastzeros=\count156
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/oldpgfcompatib/pgfplot
+soldpgfsupp_leq.code.tex))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/util/pgfplotsutil.code
+.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/liststructure/pgfplots
+liststructure.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/liststructure/pgfplots
+liststructureext.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/liststructure/pgfplots
+array.code.tex
+\c@pgfplotsarray@tmp=\count157
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/liststructure/pgfplots
+matrix.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/numtable/pgfplotstable
+shared.code.tex
+\c@pgfplotstable@counta=\count158
+\t@pgfplotstable@a=\toks53
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/liststructure/pgfplots
+deque.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/util/pgfplotsbinary.co
+de.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/util/pgfplotsbinary.da
+ta.code.tex))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/util/pgfplotsutil.verb
+.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/libs/pgflibrarypgfplot
+s.surfshading.code.tex
+\c@pgfplotslibrarysurf@no=\count159
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/sys/pgflibrarypgfplots
+.surfshading.pgfsys-pdftex.def)))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/util/pgfplotscolormap.
+code.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/util/pgfplotscolor.cod
+e.tex))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplotsstackedplots.c
+ode.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplotsplothandlers.c
+ode.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplotsmeshplothandle
+r.code.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplotsmeshplotimage.
+code.tex)))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplots.scaling.code.
+tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplotscoordprocessin
+g.code.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplots.errorbars.cod
+e.tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplots.markers.code.
+tex)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplotsticks.code.tex
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgfplots/pgfplots.paths.code.te
+x)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/frontendlayer/tikz/librarie
+s/tikzlibrarydecorations.code.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/modules/pgfmoduledecoration
+s.code.tex
+\pgfdecoratedcompleteddistance=\dimen190
+\pgfdecoratedremainingdistance=\dimen191
+\pgfdecoratedinputsegmentcompleteddistance=\dimen192
+\pgfdecoratedinputsegmentremainingdistance=\dimen193
+\pgf@decorate@distancetomove=\dimen194
+\pgf@decorate@repeatstate=\count160
+\pgfdecorationsegmentamplitude=\dimen195
+\pgfdecorationsegmentlength=\dimen196
+)
+\tikz@lib@dec@box=\box45
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/frontendlayer/tikz/librarie
+s/tikzlibrarydecorations.pathmorphing.code.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/libraries/decorations/pgfli
+brarydecorations.pathmorphing.code.tex))
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/frontendlayer/tikz/librarie
+s/tikzlibrarydecorations.pathreplacing.code.tex
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/libraries/decorations/pgfli
+brarydecorations.pathreplacing.code.tex))
+\pgfplots@numplots=\count161
+\pgfplots@xmin@reg=\dimen197
+\pgfplots@xmax@reg=\dimen198
+\pgfplots@ymin@reg=\dimen199
+\pgfplots@ymax@reg=\dimen256
+\pgfplots@zmin@reg=\dimen257
+\pgfplots@zmax@reg=\dimen258
+)
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/frontendlayer/tikz/librarie
+s/tikzlibraryplotmarks.code.tex
+File: tikzlibraryplotmarks.code.tex 2008/01/09 v3.0.1a (rcs-revision 1.1)
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/pgf/libraries/pgflibraryplotmar
+ks.code.tex
+File: pgflibraryplotmarks.code.tex 2015/08/03 v3.0.1a (rcs-revision 1.14)
+)))) (./data.sty
+
+LaTeX Warning: File `re-python.data' already exists on the system.
+ Not generating it from this source.
+
+
+LaTeX Warning: File `re-python2.data' already exists on the system.
+ Not generating it from this source.
+
+
+LaTeX Warning: File `re-ruby.data' already exists on the system.
+ Not generating it from this source.
+
+
+LaTeX Warning: File `re-js.data' already exists on the system.
+ Not generating it from this source.
+
+
+LaTeX Warning: File `re-java.data' already exists on the system.
+ Not generating it from this source.
+
+) (./ecoop_paper.aux)
+\openout1 = `ecoop_paper.aux'.
+
+LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 42.
+LaTeX Font Info: ... okay on input line 42.
+LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 42.
+LaTeX Font Info: ... okay on input line 42.
+LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 42.
+LaTeX Font Info: ... okay on input line 42.
+LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 42.
+LaTeX Font Info: ... okay on input line 42.
+LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 42.
+LaTeX Font Info: ... okay on input line 42.
+LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 42.
+LaTeX Font Info: ... okay on input line 42.
+LaTeX Font Info: Checking defaults for TS1/cmr/m/n on input line 42.
+LaTeX Font Info: Try loading font information for TS1+cmr on input line 42.
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/base/ts1cmr.fd
+File: ts1cmr.fd 2014/09/29 v2.5h Standard LaTeX font definitions
+)
+LaTeX Font Info: ... okay on input line 42.
+LaTeX Font Info: Checking defaults for PD1/pdf/m/n on input line 42.
+LaTeX Font Info: ... okay on input line 42.
+LaTeX Font Info: Try loading font information for T1+lmr on input line 42.
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/lm/t1lmr.fd
+File: t1lmr.fd 2009/10/30 v1.6 Font defs for Latin Modern
+)
+(/usr/local/texlive/2018/texmf-dist/tex/context/base/mkii/supp-pdf.mkii
+[Loading MPS to PDF converter (version 2006.09.02).]
+\scratchcounter=\count162
+\scratchdimen=\dimen259
+\scratchbox=\box46
+\nofMPsegments=\count163
+\nofMParguments=\count164
+\everyMPshowfont=\toks54
+\MPscratchCnt=\count165
+\MPscratchDim=\dimen260
+\MPnumerator=\count166
+\makeMPintoPDFobject=\count167
+\everyMPtoPDFconversion=\toks55
+) (/usr/local/texlive/2018/texmf-dist/tex/latex/oberdiek/epstopdf-base.sty
+Package: epstopdf-base 2016/05/15 v2.6 Base part for package epstopdf
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/oberdiek/grfext.sty
+Package: grfext 2016/05/16 v1.2 Manage graphics extensions (HO)
+)
+Package epstopdf-base Info: Redefining graphics rule for `.eps' on input line 4
+38.
+Package grfext Info: Graphics extension search list:
+(grfext) [.pdf,.png,.jpg,.mps,.jpeg,.jbig2,.jb2,.PDF,.PNG,.JPG,.JPE
+G,.JBIG2,.JB2,.eps]
+(grfext) \AppendGraphicsExtensions on input line 456.
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/latexconfig/epstopdf-sys.cfg
+File: epstopdf-sys.cfg 2010/07/13 v1.3 Configuration of (r)epstopdf for TeX Liv
+e
+))
+\c@lstlisting=\count168
+Package lastpage Info: Please have a look at the pageslts package at
+(lastpage) https://www.ctan.org/pkg/pageslts
+(lastpage) ! on input line 42.
+\AtBeginShipoutBox=\box47
+Package hyperref Info: Link coloring OFF on input line 42.
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/hyperref/nameref.sty
+Package: nameref 2016/05/21 v2.44 Cross-referencing by name of section
+
+(/usr/local/texlive/2018/texmf-dist/tex/generic/oberdiek/gettitlestring.sty
+Package: gettitlestring 2016/05/16 v1.5 Cleanup title references (HO)
+)
+\c@section@level=\count169
+)
+LaTeX Info: Redefining \ref on input line 42.
+LaTeX Info: Redefining \pageref on input line 42.
+LaTeX Info: Redefining \nameref on input line 42.
+
+(./ecoop_paper.out) (./ecoop_paper.out)
+\@outlinefile=\write5
+\openout5 = `ecoop_paper.out'.
+
+Package caption Info: Begin \AtBeginDocument code.
+Package caption Info: subfig package v1.3 is loaded.
+Package caption Info: rotating package is loaded.
+Package caption Info: End \AtBeginDocument code.
+ ABD: EveryShipout initializing macros
+
+Package pgfplots Warning: running in backwards compatibility mode (unsuitable t
+ick labels; missing features). Consider writing \pgfplotsset{compat=1.16} into
+your preamble.
+ on input line 42.
+
+LaTeX Font Info: Try loading font information for T1+lmss on input line 44.
+(/usr/local/texlive/2018/texmf-dist/tex/latex/lm/t1lmss.fd
+File: t1lmss.fd 2009/10/30 v1.6 Font defs for Latin Modern
+)
+LaTeX Font Info: Try loading font information for OT1+lmr on input line 44.
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/lm/ot1lmr.fd
+File: ot1lmr.fd 2009/10/30 v1.6 Font defs for Latin Modern
+)
+LaTeX Font Info: Try loading font information for OML+lmm on input line 44.
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/lm/omllmm.fd
+File: omllmm.fd 2009/10/30 v1.6 Font defs for Latin Modern
+)
+LaTeX Font Info: Try loading font information for OMS+lmsy on input line 44.
+
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/lm/omslmsy.fd
+File: omslmsy.fd 2009/10/30 v1.6 Font defs for Latin Modern
+)
+LaTeX Font Info: Try loading font information for OMX+lmex on input line 44.
+
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/lm/omxlmex.fd
+File: omxlmex.fd 2009/10/30 v1.6 Font defs for Latin Modern
+)
+LaTeX Font Info: External font `lmex10' loaded for size
+(Font) <10> on input line 44.
+LaTeX Font Info: External font `lmex10' loaded for size
+(Font) <7> on input line 44.
+LaTeX Font Info: External font `lmex10' loaded for size
+(Font) <5> on input line 44.
+LaTeX Font Info: Try loading font information for U+msa on input line 44.
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/amsfonts/umsa.fd
+File: umsa.fd 2013/01/14 v3.01 AMS symbols A
+)
+LaTeX Font Info: Try loading font information for U+msb on input line 44.
+
+(/usr/local/texlive/2018/texmf-dist/tex/latex/amsfonts/umsb.fd
+File: umsb.fd 2013/01/14 v3.01 AMS symbols B
+)
+\openout3 = `ecoop_paper.vtc'.
+
+PGFPlots: reading {re-js.data}
+LaTeX Font Info: External font `lmex10' loaded for size
+(Font) <9> on input line 99.
+LaTeX Font Info: External font `lmex10' loaded for size
+(Font) <6> on input line 99.
+PGFPlots: reading {re-python2.data}
+PGFPlots: reading {re-java.data}
+
+Overfull \hbox (2.08597pt too wide) in paragraph at lines 80--146
+ []
+ []
+
+
+LaTeX Warning: Citation `Davis18' on page 1 undefined on input line 159.
+
+<cc-by.pdf, id=24, 88.33pt x 31.11626pt>
+File: cc-by.pdf Graphic file (type pdf)
+<use cc-by.pdf>
+Package pdftex.def Info: cc-by.pdf used on input line 171.
+(pdftex.def) Requested size: 39.74274pt x 14.0pt.
+<lipics-logo-bw.pdf, id=27, 591.44762pt x 144.42657pt>
+File: lipics-logo-bw.pdf Graphic file (type pdf)
+<use lipics-logo-bw.pdf>
+Package pdftex.def Info: lipics-logo-bw.pdf used on input line 171.
+(pdftex.def) Requested size: 64.00354pt x 14.0pt.
+[1
+
+{/usr/local/texlive/2018/texmf-var/fonts/map/pdftex/updmap/pdftex.map} <./cc-by
+.pdf> <./lipics-logo-bw.pdf>]
+
+LaTeX Warning: Citation `AusafDyckhoffUrban2016' on page 2 undefined on input l
+ine 198.
+
+
+LaTeX Warning: Citation `OkuiSuzuki2010' on page 2 undefined on input line 198.
+
+
+
+LaTeX Warning: Citation `Vansummeren2006' on page 2 undefined on input line 198
+.
+
+
+LaTeX Warning: Citation `CrashCourse2014' on page 2 undefined on input line 203
+.
+
+
+LaTeX Warning: Citation `Kuklewicz' on page 2 undefined on input line 213.
+
+
+LaTeX Warning: Citation `Sulzmann2014' on page 2 undefined on input line 218.
+
+
+LaTeX Warning: Citation `Brzozowski1964' on page 2 undefined on input line 220.
+
+
+[2]
+
+LaTeX Warning: Citation `Sulzmann2014' on page 3 undefined on input line 314.
+
+[3]
+
+LaTeX Warning: Citation `Sulzmann2014' on page 4 undefined on input line 353.
+
+
+LaTeX Warning: Citation `AusafDyckhoffUrban2016' on page 4 undefined on input l
+ine 382.
+
+
+LaTeX Warning: Citation `Antimirov95' on page 4 undefined on input line 386.
+
+
+LaTeX Warning: Citation `Sulzmann2014' on page 4 undefined on input line 391.
+
+[4]
+
+LaTeX Warning: Citation `Sulzmann2014' on page 5 undefined on input line 460.
+
+[5]
+No file ecoop_paper.bbl.
+
+AED: lastpage setting LastPage
+[6]
+Package atveryend Info: Empty hook `BeforeClearDocument' on input line 505.
+Package atveryend Info: Empty hook `AfterLastShipout' on input line 505.
+ (./ecoop_paper.aux)
+Package atveryend Info: Executing hook `AtVeryEndDocument' on input line 505.
+Package atveryend Info: Executing hook `AtEndAfterFileList' on input line 505.
+Package rerunfilecheck Info: File `ecoop_paper.out' has not changed.
+(rerunfilecheck) Checksum: 933C7631DC4522E6647001738211F5B1;248.
+
+
+LaTeX Warning: There were undefined references.
+
+Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 505.
+ )
+Here is how much of TeX's memory you used:
+ 30594 strings out of 492649
+ 711121 string characters out of 6129623
+ 946443 words of memory out of 5000000
+ 33896 multiletter control sequences out of 15000+600000
+ 119541 words of font info for 70 fonts, out of 8000000 for 9000
+ 1141 hyphenation exceptions out of 8191
+ 69i,24n,107p,725b,2349s stack positions out of 5000i,500n,10000p,200000b,80000s
+{/usr/local/texlive/2018/texmf-dist/fonts/enc/dvips/lm/lm-ec.enc}{/usr/local/
+texlive/2018/texmf-dist/fonts/enc/dvips/lm/lm-rm.enc}{/usr/local/texlive/2018/t
+exmf-dist/fonts/enc/dvips/lm/lm-mathsy.enc}{/usr/local/texlive/2018/texmf-dist/
+fonts/enc/dvips/lm/lm-mathit.enc}{/usr/local/texlive/2018/texmf-dist/fonts/enc/
+dvips/lm/lm-mathex.enc}</usr/local/texlive/2018/texmf-dist/fonts/type1/public/l
+m/lmbx10.pfb></usr/local/texlive/2018/texmf-dist/fonts/type1/public/lm/lmbx9.pf
+b></usr/local/texlive/2018/texmf-dist/fonts/type1/public/lm/lmex10.pfb></usr/lo
+cal/texlive/2018/texmf-dist/fonts/type1/public/lm/lmmi10.pfb></usr/local/texliv
+e/2018/texmf-dist/fonts/type1/public/lm/lmmi6.pfb></usr/local/texlive/2018/texm
+f-dist/fonts/type1/public/lm/lmmi7.pfb></usr/local/texlive/2018/texmf-dist/font
+s/type1/public/lm/lmmi9.pfb></usr/local/texlive/2018/texmf-dist/fonts/type1/pub
+lic/lm/lmr10.pfb></usr/local/texlive/2018/texmf-dist/fonts/type1/public/lm/lmr6
+.pfb></usr/local/texlive/2018/texmf-dist/fonts/type1/public/lm/lmr7.pfb></usr/l
+ocal/texlive/2018/texmf-dist/fonts/type1/public/lm/lmr9.pfb></usr/local/texlive
+/2018/texmf-dist/fonts/type1/public/lm/lmri10.pfb></usr/local/texlive/2018/texm
+f-dist/fonts/type1/public/lm/lmri9.pfb></usr/local/texlive/2018/texmf-dist/font
+s/type1/public/lm/lmssbx10.pfb></usr/local/texlive/2018/texmf-dist/fonts/type1/
+public/lm/lmsy10.pfb></usr/local/texlive/2018/texmf-dist/fonts/type1/public/lm/
+lmsy6.pfb></usr/local/texlive/2018/texmf-dist/fonts/type1/public/lm/lmsy7.pfb><
+/usr/local/texlive/2018/texmf-dist/fonts/type1/public/lm/lmsy9.pfb>
+Output written on ecoop_paper.pdf (6 pages, 323164 bytes).
+PDF statistics:
+ 160 PDF objects out of 1000 (max. 8388607)
+ 124 compressed objects within 2 object streams
+ 11 named destinations out of 1000 (max. 500000)
+ 61 words of extra memory for PDF output out of 10000 (max. 10000000)
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/ecoop_paper.out Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,4 @@
+\BOOKMARK [1][-]{section.1}{Introduction}{}% 1
+\BOOKMARK [1][-]{section.2}{The Algorithms by Brzozowski, and Sulzmann and Lu}{}% 2
+\BOOKMARK [1][-]{section.3}{Simplification of Regular Expressions}{}% 3
+\BOOKMARK [1][-]{section.4}{Conclusion}{}% 4
Binary file ecp/ecoop_paper.pdf has changed
Binary file ecp/ecoop_paper.synctex.gz has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/ecoop_paper.tex Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,505 @@
+\documentclass[a4paper,UKenglish]{lipics}
+\usepackage{graphic}
+\usepackage{data}
+% \documentclass{article}
+%\usepackage[utf8]{inputenc}
+%\usepackage[english]{babel}
+%\usepackage{listings}
+% \usepackage{amsthm}
+% \usepackage{hyperref}
+% \usepackage[margin=0.5in]{geometry}
+%\usepackage{pmboxdraw}
+
+\title{POSIX Regular Expression Matching and Lexing}
+\author[1]{Annonymous}
+
+\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
+\newcommand{\ZERO}{\mbox{\bf 0}}
+\newcommand{\ONE}{\mbox{\bf 1}}
+\def\lexer{\mathit{lexer}}
+\def\mkeps{\mathit{mkeps}}
+\def\inj{\mathit{inj}}
+\def\Empty{\mathit{Empty}}
+\def\Left{\mathit{Left}}
+\def\Right{\mathit{Right}}
+\def\Stars{\mathit{Stars}}
+\def\Char{\mathit{Char}}
+\def\Seq{\mathit{Seq}}
+\def\Der{\mathit{Der}}
+\def\nullable{\mathit{nullable}}
+\def\Z{\mathit{Z}}
+\def\S{\mathit{S}}
+
+%\theoremstyle{theorem}
+%\newtheorem{theorem}{Theorem}
+%\theoremstyle{lemma}
+%\newtheorem{lemma}{Lemma}
+%\newcommand{\lemmaautorefname}{Lemma}
+%\theoremstyle{definition}
+%\newtheorem{definition}{Definition}
+
+
+\begin{document}
+
+\maketitle
+\begin{abstract}
+ Brzozowski introduced in 1964 a beautifully simple algorithm for
+ regular expression matching based on the notion of derivatives of
+ regular expressions. In 2014, Sulzmann and Lu extended this
+ algorithm to not just give a YES/NO answer for whether or not a regular
+ expression matches a string, but in case it matches also \emph{how}
+ it matches the string. This is important for applications such as
+ lexing (tokenising a string). The problem is to make the algorithm
+ by Sulzmann and Lu fast on all inputs without breaking its
+ correctness.
+\end{abstract}
+
+\section{Introduction}
+
+This PhD-project is about regular expression matching and
+lexing. Given the maturity of this topic, the reader might wonder:
+Surely, regular expressions must have already been studied to death?
+What could possibly be \emph{not} known in this area? And surely all
+implemented algorithms for regular expression matching are blindingly
+fast?
+
+
+
+Unfortunately these preconceptions are not supported by evidence: Take
+for example the regular expression $(a^*)^*\,b$ and ask whether
+strings of the form $aa..a$ match this regular
+expression. Obviously they do not match---the expected $b$ in the last
+position is missing. One would expect that modern regular expression
+matching engines can find this out very quickly. Alas, if one tries
+this example in JavaScript, Python or Java 8 with strings like 28
+$a$'s, one discovers that this decision takes around 30 seconds and
+takes considerably longer when adding a few more $a$'s, as the graphs
+below show:
+
+\begin{center}
+\begin{tabular}{@{}c@{\hspace{0mm}}c@{\hspace{0mm}}c@{}}
+\begin{tikzpicture}
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.05,-0.05)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=33,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5cm,
+ height=4cm,
+ legend entries={JavaScript},
+ legend pos=north west,
+ legend cell align=left]
+\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+\end{axis}
+\end{tikzpicture}
+ &
+\begin{tikzpicture}
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.05,-0.05)}},
+ %ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=33,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5cm,
+ height=4cm,
+ legend entries={Python},
+ legend pos=north west,
+ legend cell align=left]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+\end{axis}
+\end{tikzpicture}
+ &
+\begin{tikzpicture}
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.05,-0.05)}},
+ %ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=33,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5cm,
+ height=4cm,
+ legend entries={Java 8},
+ legend pos=north west,
+ legend cell align=left]
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\end{axis}
+\end{tikzpicture}\\
+\multicolumn{3}{c}{Graphs: Runtime for matching $(a^*)^*\,b$ with strings
+ of the form $\underbrace{aa..a}_{n}$.}
+\end{tabular}
+\end{center}
+
+\noindent These are clearly abysmal and possibly surprising results.
+One would expect these systems doing much better than that---after
+all, given a DFA and a string, whether a string is matched by this DFA
+should be linear.
+
+Admittedly, the regular expression $(a^*)^*\,b$ is carefully chosen to
+exhibit this ``exponential behaviour''. Unfortunately, such regular
+expressions are not just a few ``outliers'', but actually they are
+frequent enough that a separate name has been created for
+them---\emph{evil regular expressions}. In empiric work, Davis et al
+report that they have found thousands of such evil regular expressions
+in the JavaScript and Python ecosystems \cite{Davis18}.
+
+This exponential blowup sometimes causes real pain in ``real life'':
+for example one evil regular expression brought on 20 July 2016 the
+webpage \href{http://stackexchange.com}{Stack Exchange} to its knees.
+In this instance, a regular expression intended to just trim white
+spaces from the beginning and the end of a line actually consumed
+massive amounts of CPU-resources and because of this the web servers
+ground to a halt. This happened when a post with 20,000 white spaces
+was submitted, but importantly the white spaces were neither at the
+beginning nor at the end. As a result, the regular expression matching
+engine needed to backtrack over many choices.
+
+The underlying problem is that many ``real life'' regular expression
+matching engines do not use DFAs for matching. This is because they
+support regular expressions that are not covered by the classical
+automata theory, and in this more general setting there are quite a
+few research questions still unanswered and fast algorithms still need
+to be developed.
+
+There is also another under-researched problem to do with regular
+expressions and lexing, i.e.~the process of breaking up strings into
+sequences of tokens according to some regular expressions. In this
+setting one is not just interested in whether or not a regular
+expression matches a string, but if it matches also in \emph{how} it
+matches the string. Consider for example a regular expression
+$r_{key}$ for recognising keywords such as \textit{if}, \textit{then}
+and so on; and a regular expression $r_{id}$ for recognising
+identifiers (say, a single character followed by characters or
+numbers). One can then form the compound regular expression
+$(r_{key} + r_{id})^*$ and use it to tokenise strings. But then how
+should the string \textit{iffoo} be tokenised? It could be tokenised
+as a keyword followed by an identifier, or the entire string as a
+single identifier. Similarly, how should the string \textit{if} be
+tokenised? Both regular expressions, $r_{key}$ and $r_{id}$, would
+``fire''---so is it an identifier or a keyword? While in applications
+there is a well-known strategy to decide these questions, called POSIX
+matching, only relatively recently precise definitions of what POSIX
+matching actually means have been formalised
+\cite{AusafDyckhoffUrban2016,OkuiSuzuki2010,Vansummeren2006}. Roughly,
+POSIX matching means to match the longest initial substring and
+possible ties are solved according to some priorities attached to the
+regular expressions (e.g.~keywords have a higher priority than
+identifiers). This sounds rather simple, but according to Grathwohl et
+al \cite[Page 36]{CrashCourse2014} this is not the case. They wrote:
+
+\begin{quote}
+\it{}``The POSIX strategy is more complicated than the greedy because of
+the dependence on information about the length of matched strings in the
+various subexpressions.''
+\end{quote}
+
+\noindent
+This is also supported by evidence collected by Kuklewicz
+\cite{Kuklewicz} who noticed that a number of POSIX regular expression
+matchers calculate incorrect results.
+
+Our focus is on an algorithm introduced by Sulzmann and Lu in 2014 for
+regular expression matching according to the POSIX strategy
+\cite{Sulzmann2014}. Their algorithm is based on an older algorithm by
+Brzozowski from 1964 where he introduced the notion of derivatives of
+regular expressions \cite{Brzozowski1964}. We shall briefly explain
+the algorithms next.
+
+\section{The Algorithms by Brzozowski, and Sulzmann and Lu}
+
+Suppose regular expressions are given by the following grammar (for
+the moment ignore the grammar for values on the right-hand side):
+
+
+\begin{center}
+ \begin{tabular}{c@{\hspace{20mm}}c}
+ \begin{tabular}{@{}rrl@{}}
+ \multicolumn{3}{@{}l}{\textbf{Regular Expressions}}\medskip\\
+ $r$ & $::=$ & $\ZERO$\\
+ & $\mid$ & $\ONE$ \\
+ & $\mid$ & $c$ \\
+ & $\mid$ & $r_1 \cdot r_2$\\
+ & $\mid$ & $r_1 + r_2$ \\
+ \\
+ & $\mid$ & $r^*$ \\
+ \end{tabular}
+ &
+ \begin{tabular}{@{\hspace{0mm}}rrl@{}}
+ \multicolumn{3}{@{}l}{\textbf{Values}}\medskip\\
+ $v$ & $::=$ & \\
+ & & $\Empty$ \\
+ & $\mid$ & $\Char(c)$ \\
+ & $\mid$ & $\Seq\,v_1\, v_2$\\
+ & $\mid$ & $\Left(v)$ \\
+ & $\mid$ & $\Right(v)$ \\
+ & $\mid$ & $\Stars\,[v_1,\ldots\,v_n]$ \\
+ \end{tabular}
+ \end{tabular}
+\end{center}
+
+\noindent
+The intended meaning of the regular expressions is as usual: $\ZERO$
+cannot match any string, $\ONE$ can match the empty string, the
+character regular expression $c$ can match the character $c$, and so
+on. The brilliant contribution by Brzozowski is the notion of
+\emph{derivatives} of regular expressions. The idea behind this
+notion is as follows: suppose a regular expression $r$ can match a
+string of the form $c\!::\! s$ (that is a list of characters starting
+with $c$), what does the regular expression look like that can match
+just $s$? Brzozowski gave a neat answer to this question. He defined
+the following operation on regular expressions, written
+$r\backslash c$ (the derivative of $r$ w.r.t.~the character $c$):
+
+\begin{center}
+\begin{tabular}{lcl}
+ $\ZERO \backslash c$ & $\dn$ & $\ZERO$\\
+ $\ONE \backslash c$ & $\dn$ & $\ZERO$\\
+ $d \backslash c$ & $\dn$ &
+ $\mathit{if} \;c = d\;\mathit{then}\;\ONE\;\mathit{else}\;\ZERO$\\
+$(r_1 + r_2)\backslash c$ & $\dn$ & $r_1 \backslash c \,+\, r_2 \backslash c$\\
+$(r_1 \cdot r_2)\backslash c$ & $\dn$ & $\mathit{if} \nullable(r_1)$\\
+ & & $\mathit{then}\;(r_1\backslash c) \cdot r_2 \,+\, r_2\backslash c$\\
+ & & $\mathit{else}\;(r_1\backslash c) \cdot r_2$\\
+ $(r^*)\backslash c$ & $\dn$ & $(r\backslash c) \cdot r^*$\\
+\end{tabular}
+\end{center}
+
+\noindent
+In this definition $\nullable(\_)$ stands for a simple recursive
+function that tests whether a regular expression can match the empty
+string (its definition is omitted). Assuming the classic notion of a
+\emph{language} of a regular expression, written $L(\_)$, the main
+property of the derivative operation is that
+
+\begin{center}
+$c\!::\!s \in L(r)$ holds
+if and only if $s \in L(r\backslash c)$.
+\end{center}
+
+\noindent
+The beauty of derivatives is that they lead to a really simple regular
+expression matching algorithm: To find out whether a string $s$
+matches with a regular expression $r$, build the derivatives of $r$
+w.r.t.\ (in succession) all the characters of the string $s$. Finally,
+test whether the resulting regular expression can match the empty
+string. If yes, then $r$ matches $s$, and no in the negative
+case. For us the main advantage is that derivatives can be
+straightforwardly implemented in any functional programming language,
+and are easily definable and reasoned about in theorem provers---the
+definitions just consist of inductive datatypes and simple recursive
+functions. Moreover, the notion of derivatives can be easily
+generalised to cover extended regular expression constructors such as
+the not-regular expression, written $\neg\,r$, or bounded repetitions
+(for example $r^{\{n\}}$ and $r^{\{n..m\}}$), which cannot be so
+straightforwardly realised within the classic automata approach.
+
+
+One limitation, however, of Brzozowski's algorithm is that it only
+produces a YES/NO answer for whether a string is being matched by a
+regular expression. Sulzmann and Lu~\cite{Sulzmann2014} extended this
+algorithm to allow generation of an actual matching, called a
+\emph{value}---see the grammar above for its definition. Assuming a
+regular expression matches a string, values encode the information of
+\emph{how} the string is matched by the regular expression---that is,
+which part of the string is matched by which part of the regular
+expression. To illustrate this consider the string $xy$ and the
+regular expression $(x + (y + xy))^*$. We can view this regular
+expression as a tree and if the string $xy$ is matched by two Star
+``iterations'', then the $x$ is matched by the left-most alternative
+in this tree and the $y$ by the right-left alternative. This suggests
+to record this matching as
+
+\begin{center}
+$\Stars\,[\Left\,(\Char\,x), \Right(\Left(\Char\,y))]$
+\end{center}
+
+\noindent
+where $\Stars$ records how many
+iterations were used; and $\Left$, respectively $\Right$, which
+alternative is used. The value for
+matching $xy$ in a single ``iteration'', i.e.~the POSIX value,
+would look as follows
+
+\begin{center}
+$\Stars\,[\Seq\,(\Char\,x)\,(\Char\,y)]$
+\end{center}
+
+\noindent
+where $\Stars$ has only a single-element list for the single iteration
+and $\Seq$ indicates that $xy$ is matched by a sequence regular
+expression.
+
+The contribution of Sulzmann and Lu is an extension of Brzozowski's
+algorithm by a second phase (the first phase being building successive
+derivatives). In this second phase, for every successful match the
+corresponding POSIX value is computed. As mentioned before, from this
+value we can extract the information \emph{how} a regular expression
+matched a string. We omit the details here on how Sulzmann and Lu
+achieved this~(see \cite{Sulzmann2014}). Rather, we shall focus next on the
+process of simplification of regular expressions, which is needed in
+order to obtain \emph{fast} versions of the Brzozowski's, and Sulzmann
+and Lu's algorithms. This is where the PhD-project hopes to advance
+the state-of-the-art.
+
+
+\section{Simplification of Regular Expressions}
+
+The main drawback of building successive derivatives according to
+Brzozowski's definition is that they can grow very quickly in size.
+This is mainly due to the fact that the derivative operation generates
+often ``useless'' $\ZERO$s and $\ONE$s in derivatives. As a result,
+if implemented naively both algorithms by Brzozowski and by Sulzmann
+and Lu are excruciatingly slow. For example when starting with the
+regular expression $(a + aa)^*$ and building 12 successive derivatives
+w.r.t.~the character $a$, one obtains a derivative regular expression
+with more than 8000 nodes (when viewed as a tree). Operations like
+derivative and $\nullable$ need to traverse such trees and
+consequently the bigger the size of the derivative the slower the
+algorithm. Fortunately, one can simplify regular expressions after
+each derivative step. Various simplifications of regular expressions
+are possible, such as the simplifications of $\ZERO + r$,
+$r + \ZERO$, $\ONE\cdot r$, $r \cdot \ONE$, and $r + r$ to just
+$r$. These simplifications do not affect the answer for whether a
+regular expression matches a string or not, but fortunately also do
+not affect the POSIX strategy of how regular expressions match
+strings---although the latter is much harder to establish. Some
+initial results in this regard have been obtained in
+\cite{AusafDyckhoffUrban2016}. However, what has not been achieved yet
+is a very tight bound for the size. Such a tight bound is suggested by
+work of Antimirov who proved that (partial) derivatives can be bound
+by the number of characters contained in the initial regular
+expression \cite{Antimirov95}. We believe, and have generated test
+data, that a similar bound can be obtained for the derivatives in
+Sulzmann and Lu's algorithm. Let us give some details about this next.
+
+We first followed Sulzmann and Lu's idea of introducing
+\emph{annotated regular expressions}~\cite{Sulzmann2014}. They are
+defined by the following grammar:
+
+\begin{center}
+\begin{tabular}{lcl}
+ $\textit{a}$ & $::=$ & $\textit{ZERO}$\\
+ & $\mid$ & $\textit{ONE}\;\;bs$\\
+ & $\mid$ & $\textit{CHAR}\;\;bs\,c$\\
+ & $\mid$ & $\textit{ALTS}\;\;bs\,as$\\
+ & $\mid$ & $\textit{SEQ}\;\;bs\,a_1\,a_2$\\
+ & $\mid$ & $\textit{STAR}\;\;bs\,a$
+\end{tabular}
+\end{center}
+
+\noindent
+where $bs$ stands for bitsequences, and $as$ (in \textit{ALTS}) for a
+list of annotated regular expressions. These bitsequences encode
+information about the (POSIX) value that should be generated by the
+Sulzmann and Lu algorithm. There are operations that can transform the
+usual (un-annotated) regular expressions into annotated regular
+expressions, and there are operations for encoding/decoding values to
+or from bitsequences. For example the encoding function for values is
+defined as follows:
+
+\begin{center}
+\begin{tabular}{lcl}
+ $\textit{code}(\Empty)$ & $\dn$ & $[]$\\
+ $\textit{code}(\Char\,c)$ & $\dn$ & $[]$\\
+ $\textit{code}(\Left\,v)$ & $\dn$ & $\Z :: code(v)$\\
+ $\textit{code}(\Right\,v)$ & $\dn$ & $\S :: code(v)$\\
+ $\textit{code}(\Seq\,v_1\,v_2)$ & $\dn$ & $code(v_1) \,@\, code(v_2)$\\
+ $\textit{code}(\Stars\,[])$ & $\dn$ & $[\S]$\\
+ $\textit{code}(\Stars\,(v\!::\!vs))$ & $\dn$ & $\Z :: code(v) \;@\;
+ code(\Stars\,vs)$
+\end{tabular}
+\end{center}
+
+\noindent
+where $\Z$ and $\S$ are arbitrary names for the ``bits'' in the
+bitsequences. Although this encoding is ``lossy'' in the sense of not
+recording all details of a value, Sulzmann and Lu have defined the
+decoding function such that with additional information (namely the
+corresponding regular expression) a value can be precisely extracted
+from a bitsequence.
+
+The main point of the bitsequences and annotated regular expressions
+is that we can apply rather aggressive (in terms of size)
+simplification rules in order to keep derivatives small. We have
+developed such ``aggressive'' simplification rules and generated test
+data that show that the expected bound can be achieved. Obviously we
+could only cover partially the search space as there are infinitely
+many regular expressions and strings. One modification we introduced
+is to allow a list of annotated regular expressions in the
+\textit{ALTS} constructor. This allows us to not just delete
+unnecessary $\ZERO$s and $\ONE$s from regular expressions, but also
+unnecessary ``copies'' of regular expressions (very similar to
+simplifying $r + r$ to just $r$, but in a more general
+setting). Another modification is that we use simplification rules
+inspired by Antimirov's work on partial derivatives. They maintain the
+idea that only the first ``copy'' of a regular expression in an
+alternative contributes to the calculation of a POSIX value. All
+subsequent copies can be prunned from the regular expression.
+
+We are currently engaged with proving that our simplification rules
+actually do not affect the POSIX value that should be generated by the
+algorithm according to the specification of a POSIX value and
+furthermore that our derivatives stay small for all derivatives. For
+this proof we use the theorem prover Isabelle. Once completed, this
+result will advance the state-of-the-art: Sulzmann and Lu wrote in
+their paper \cite{Sulzmann2014} about the bitcoded ``incremental
+parsing method'' (that is the matching algorithm outlined in this
+section):
+
+\begin{quote}\it
+ ``Correctness Claim: We further claim that the incremental parsing
+ method in Figure~5 in combination with the simplification steps in
+ Figure 6 yields POSIX parse trees. We have tested this claim
+ extensively by using the method in Figure~3 as a reference but yet
+ have to work out all proof details.''
+\end{quote}
+
+\noindent
+We would settle the correctness claim and furthermore obtain a much
+tighter bound on the sizes of derivatives. The result is that our
+algorithm should be correct and faster on all inputs. The original
+blow-up, as observed in JavaScript, Python and Java, would be excluded
+from happening in our algorithm.
+
+\section{Conclusion}
+
+In this PhD-project we are interested in fast algorithms for regular
+expression matching. While this seems to be a ``settled'' area, in
+fact interesting research questions are popping up as soon as one steps
+outside the classic automata theory (for example in terms of what kind
+of regular expressions are supported). The reason why it is
+interesting for us to look at the derivative approach introduced by
+Brzozowski for regular expression matching, and then much further
+developed by Sulzmann and Lu, is that derivatives can elegantly deal
+with some of the regular expressions that are of interest in ``real
+life''. This includes the not-regular expression, written $\neg\,r$
+(that is all strings that are not recognised by $r$), but also bounded
+regular expressions such as $r^{\{n\}}$ and $r^{\{n..m\}}$). There is
+also hope that the derivatives can provide another angle for how to
+deal more efficiently with back-references, which are one of the
+reasons why regular expression engines in JavaScript, Python and Java
+choose to not implement the classic automata approach of transforming
+regular expressions into NFAs and then DFAs---because we simply do not
+know how such back-references can be represented by DFAs.
+
+
+\bibliographystyle{plain}
+\bibliography{root}
+
+
+\end{document}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/ecoop_paper.vtc Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,1 @@
+\contitem\title{POSIX Regular Expression Matching and Lexing}\author{Annonymous}\page{1}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/graphic.sty Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,12 @@
+\usepackage{tikz}
+%\usepackage{pgf}
+%\usetikzlibrary{positioning}
+%\usetikzlibrary{calc}
+%\usetikzlibrary{automata}
+%\usetikzlibrary{arrows}
+%\usetikzlibrary{backgrounds}
+%\usetikzlibrary{fit}
+%\usepackage{tikz-qtree}
+\usepackage{pgfplots}
+
+%\pgfplotsset{compat=1.15}
Binary file ecp/lipics-logo-bw.pdf has changed
Binary file ecp/lipics-manual.pdf has changed
Binary file ecp/lipics-sample-article.pdf has changed
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/lipics-sample-article.tex Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,146 @@
+\documentclass[a4paper,UKenglish]{lipics}
+%This is a template for producing LIPIcs articles.
+%See lipics-manual.pdf for further information.
+%for A4 paper format use option "a4paper", for US-letter use option "letterpaper"
+%for british hyphenation rules use option "UKenglish", for american hyphenation rules use option "USenglish"
+% for section-numbered lemmas etc., use "numberwithinsect"
+
+\usepackage{microtype}%if unwanted, comment out or use option "draft"
+
+%\graphicspath{{./graphics/}}%helpful if your graphic files are in another directory
+
+\bibliographystyle{plain}% the recommended bibstyle
+
+% Author macros::begin %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\title{A Sample Article for the LIPIcs series\footnote{This work was partially supported by someone.}}
+\titlerunning{A Sample LIPIcs Article} %optional, in case that the title is too long; the running title should fit into the top page column
+
+\author[1]{John Q. Open}
+\author[2]{Joan R. Access}
+\affil[1]{Dummy University Computing Laboratory\\
+ Address, Country\\
+ \texttt{open@dummyuni.org}}
+\affil[2]{Department of Informatics, Dummy College\\
+ Address, Country\\
+ \texttt{access@dummycollege.org}}
+\authorrunning{J.\,Q. Open and J.\,R. Access} %mandatory. First: Use abbreviated first/middle names. Second (only in severe cases): Use first author plus 'et. al.'
+
+\Copyright{John Q. Open and Joan R. Access}%mandatory, please use full first names. LIPIcs license is "CC-BY"; http://creativecommons.org/licenses/by/3.0/
+
+\subjclass{Dummy classification -- please refer to \url{http://www.acm.org/about/class/ccs98-html}}% mandatory: Please choose ACM 1998 classifications from http://www.acm.org/about/class/ccs98-html . E.g., cite as "F.1.1 Models of Computation".
+\keywords{Dummy keyword -- please provide 1--5 keywords}% mandatory: Please provide 1-5 keywords
+% Author macros::end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%Editor-only macros:: begin (do not touch as author)%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\serieslogo{}%please provide filename (without suffix)
+\volumeinfo%(easychair interface)
+ {Billy Editor and Bill Editors}% editors
+ {2}% number of editors: 1, 2, ....
+ {Conference title on which this volume is based on}% event
+ {1}% volume
+ {1}% issue
+ {1}% starting page number
+\EventShortName{}
+\DOI{10.4230/LIPIcs.xxx.yyy.p}% to be completed by the volume editor
+% Editor-only macros::end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\begin{document}
+
+\maketitle
+
+\begin{abstract}
+Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent convallis orci arcu, eu mollis dolor. Aliquam eleifend suscipit lacinia. Maecenas quam mi, porta ut lacinia sed, convallis ac dui. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Suspendisse potenti.
+ \end{abstract}
+
+\section{Typesetting instructions -- please read carefully}
+Please comply with the following instructions when preparing your article for a LIPIcs proceedings volume.
+\begin{itemize}
+\item Use pdflatex and an up-to-date LaTeX system.
+\item Use further LaTeX packages only if required.
+\item Add custom made macros carefully and only those which are needed in the document (i.e., do not simply add your convolute of macros collected over the years).
+\item Do not use a different main font. For example, the usage of the times-package is forbidden.
+\item Provide full author names (especially with regard to the first name) in the \verb+\author+ macro and in the \verb+\Copyright+ macro.
+\item Fill out the \verb+\subjclass+ and \verb+\keywords+ macros. For the \verb+\subjclass+, please refer to the ACM classification at \url{http://www.acm.org/about/class/ccs98-html}.
+\item Take care of suitable linebreaks and pagebreaks. No overfull \verb+\hboxes+ should occur in the warnings log.
+\item Provide suitable graphics of at least 300dpi (preferrably in pdf format).
+\item Use the provided sectioning macros: \verb+\section+, \verb+\subsection+, \verb+\subsection*+, \verb+\paragraph+, \verb+\subparagraph*+, ... ``Self-made'' sectioning commands (for example, \verb+\noindent{\bf My+ \verb+subparagraph.}+ will be removed and replaced by standard LIPIcs style sectioning commands.
+\item Do not alter the spacing of the \verb+lipics.cls+ style file. Such modifications will be removed.
+\item Do not use conditional structures to include/exclude content. Instead, please provide only the content that should be published and nothing else.
+\item Remove all comments, especially avoid commenting large text blocks or using \verb+\iffalse+ \verb+... \fi+ constructions.
+\item Keep the standard style (\verb+plain+) for the bibliography as provided by the \verb+lipics.cls+ style file.
+\item Use BibTex and provide exactly one BibTex file for your article. The BibTex file should contain only entries that are referenced in the article. Please make sure that there are no errors and warnings with the referenced BibTex entries.
+\item Use a spellchecker to get rid of typos.
+\item A manual for the LIPIcs style is available at \url{http://drops.dagstuhl.de/styles/lipics/lipics-authors/lipics-manual.pdf}.
+\end{itemize}
+
+
+\section{Lorem ipsum dolor sit amet}
+
+Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent convallis orci arcu, eu mollis dolor. Aliquam eleifend suscipit lacinia. Maecenas quam mi, porta ut lacinia sed, convallis ac dui. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Suspendisse potenti. Donec eget odio et magna ullamcorper vehicula ut vitae libero. Maecenas lectus nulla, auctor nec varius ac, ultricies et turpis. Pellentesque id ante erat. In hac habitasse platea dictumst. Curabitur a scelerisque odio. Pellentesque elit risus, posuere quis elementum at, pellentesque ut diam. Quisque aliquam libero id mi imperdiet quis convallis turpis eleifend.
+
+\begin{lemma}[Lorem ipsum]
+Vestibulum sodales dolor et dui cursus iaculis. Nullam ullamcorper purus vel turpis lobortis eu tempus lorem semper. Proin facilisis gravida rutrum. Etiam sed sollicitudin lorem. Proin pellentesque risus at elit hendrerit pharetra. Integer at turpis varius libero rhoncus fermentum vitae vitae metus. \end{lemma}
+\begin{proof}
+Cras purus lorem, pulvinar et fermentum sagittis, suscipit quis magna.
+\end{proof}
+
+\subsection{Curabitur dictum felis id sapien}
+
+Curabitur dictum felis id sapien mollis ut venenatis tortor feugiat. Curabitur sed velit diam. Integer aliquam, nunc ac egestas lacinia, nibh est vehicula nibh, ac auctor velit tellus non arcu. Vestibulum lacinia ipsum vitae nisi ultrices eget gravida turpis laoreet. Duis rutrum dapibus ornare. Nulla vehicula vulputate iaculis. Proin a consequat neque. Donec ut rutrum urna. Morbi scelerisque turpis sed elit sagittis eu scelerisque quam condimentum. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Aenean nec faucibus leo. Cras ut nisl odio, non tincidunt lorem. Integer purus ligula, venenatis et convallis lacinia, scelerisque at erat. Fusce risus libero, convallis at fermentum in, dignissim sed sem. Ut dapibus orci vitae nisl viverra nec adipiscing tortor condimentum. Donec non suscipit lorem. Nam sit amet enim vitae nisl accumsan pretium.
+
+\begin{lstlisting}[caption={Useless code},label=list:8-6,captionpos=t,float,abovecaptionskip=-\medskipamount]
+for i:=maxint to 0 do
+begin
+ j:=square(root(i));
+end;
+\end{lstlisting}
+
+\subsection{Proin ac fermentum augue}
+
+Proin ac fermentum augue. Nullam bibendum enim sollicitudin tellus egestas lacinia euismod orci mollis. Nulla facilisi. Vivamus volutpat venenatis sapien, vitae feugiat arcu fringilla ac. Mauris sapien tortor, sagittis eget auctor at, vulputate pharetra magna. Sed congue, dui nec vulputate convallis, sem nunc adipiscing dui, vel venenatis mauris sem in dui. Praesent a pretium quam. Mauris non mauris sit amet eros rutrum aliquam id ut sapien. Nulla aliquet fringilla sagittis. Pellentesque eu metus posuere nunc tincidunt dignissim in tempor dolor. Nulla cursus aliquet enim. Cras sapien risus, accumsan eu cursus ut, commodo vel velit. Praesent aliquet consectetur ligula, vitae iaculis ligula interdum vel. Integer faucibus faucibus felis.
+
+\begin{itemize}
+\item Ut vitae diam augue.
+\item Integer lacus ante, pellentesque sed sollicitudin et, pulvinar adipiscing sem.
+\item Maecenas facilisis, leo quis tincidunt egestas, magna ipsum condimentum orci, vitae facilisis nibh turpis et elit.
+\end{itemize}
+
+\section{Pellentesque quis tortor}
+
+Nec urna malesuada sollicitudin. Nulla facilisi. Vivamus aliquam tempus ligula eget ornare. Praesent eget magna ut turpis mattis cursus. Aliquam vel condimentum orci. Nunc congue, libero in gravida convallis, orci nibh sodales quam, id egestas felis mi nec nisi. Suspendisse tincidunt, est ac vestibulum posuere, justo odio bibendum urna, rutrum bibendum dolor sem nec tellus.
+
+\begin{lemma} [Quisque blandit tempus nunc]
+Sed interdum nisl pretium non. Mauris sodales consequat risus vel consectetur. Aliquam erat volutpat. Nunc sed sapien ligula. Proin faucibus sapien luctus nisl feugiat convallis faucibus elit cursus. Nunc vestibulum nunc ac massa pretium pharetra. Nulla facilisis turpis id augue venenatis blandit. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus.
+\end{lemma}
+
+Fusce eu leo nisi. Cras eget orci neque, eleifend dapibus felis. Duis et leo dui. Nam vulputate, velit et laoreet porttitor, quam arcu facilisis dui, sed malesuada risus massa sit amet neque.
+
+
+\subparagraph*{Acknowledgements}
+
+I want to thank \dots
+
+\appendix
+\section{Morbi eros magna}
+
+Morbi eros magna, vestibulum non posuere non, porta eu quam. Maecenas vitae orci risus, eget imperdiet mauris. Donec massa mauris, pellentesque vel lobortis eu, molestie ac turpis. Sed condimentum convallis dolor, a dignissim est ultrices eu. Donec consectetur volutpat eros, et ornare dui ultricies id. Vivamus eu augue eget dolor euismod ultrices et sit amet nisi. Vivamus malesuada leo ac leo ullamcorper tempor. Donec justo mi, tempor vitae aliquet non, faucibus eu lacus. Donec dictum gravida neque, non porta turpis imperdiet eget. Curabitur quis euismod ligula.
+
+
+%%
+%% Bibliography
+%%
+
+%% Either use bibtex (recommended), but commented out in this sample
+
+%\bibliography{dummybib}
+
+%% .. or use bibitems explicitely
+
+\nocite{Simpson}
+
+\begin{thebibliography}{50}
+\bibitem{Simpson} Homer J. Simpson. \textsl{Mmmmm...donuts}. Evergreen Terrace Printing Co., Springfield, Somewhere, USA, 1998
+\end{thebibliography}
+
+
+\end{document}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/lipics.cls Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,646 @@
+%%
+%% This is file `lipics.cls',
+%% generated with the docstrip utility.
+%%
+%% The original source files were:
+%%
+%% lipics.dtx (with options: `class')
+%%
+%% -----------------------------------------------------------------
+%% Author: le-tex publishing services
+%%
+%% This file is part of the lipics package for preparing
+%% LIPICS articles.
+%%
+%% Copyright (C) 2010 Schloss Dagstuhl
+%% -----------------------------------------------------------------
+\NeedsTeXFormat{LaTeX2e}[2005/12/01]
+\ProvidesClass{lipics}
+ [2010/09/27 v1.1 LIPIcs articles]
+\emergencystretch1em
+\advance\hoffset-1in
+\advance\voffset-1in
+\advance\hoffset2.95mm
+\newif\if@nobotseplist \@nobotseplistfalse
+\def\@endparenv{%
+ \addpenalty\@endparpenalty\if@nobotseplist\else\addvspace\@topsepadd\fi\@endpetrue}
+\def\@doendpe{%
+ \@endpetrue
+ \def\par{\@restorepar
+ \everypar{}%
+ \par
+ \if@nobotseplist
+ \addvspace\topsep
+ \addvspace\partopsep
+ \global\@nobotseplistfalse
+ \fi
+ \@endpefalse}%
+ \everypar{{\setbox\z@\lastbox}%
+ \everypar{}%
+ \if@nobotseplist\global\@nobotseplistfalse\fi
+ \@endpefalse}}
+\def\enumerate{%
+ \ifnum \@enumdepth >\thr@@\@toodeep\else
+ \advance\@enumdepth\@ne
+ \edef\@enumctr{enum\romannumeral\the\@enumdepth}%
+ \expandafter
+ \list
+ \csname label\@enumctr\endcsname
+ {\advance\partopsep\topsep
+ \topsep\z@\@plus\p@
+ \ifnum\@listdepth=\@ne
+ \labelsep0.72em
+ \else
+ \ifnum\@listdepth=\tw@
+ \labelsep0.3em
+ \else
+ \labelsep0.5em
+ \fi
+ \fi
+ \usecounter\@enumctr\def\makelabel##1{\hss\llap{##1}}}%
+ \fi}
+\def\endenumerate{\ifnum\@listdepth=\@ne\global\@nobotseplisttrue\fi\endlist}
+\def\itemize{%
+ \ifnum \@itemdepth >\thr@@\@toodeep\else
+ \advance\@itemdepth\@ne
+ \edef\@itemitem{labelitem\romannumeral\the\@itemdepth}%
+ \expandafter
+ \list
+ \csname\@itemitem\endcsname
+ {\advance\partopsep\topsep
+ \topsep\z@\@plus\p@
+ \ifnum\@listdepth=\@ne
+ \labelsep0.83em
+ \else
+ \ifnum\@listdepth=\tw@
+ \labelsep0.75em
+ \else
+ \labelsep0.5em
+ \fi
+ \fi
+ \def\makelabel##1{\hss\llap{##1}}}%
+ \fi}
+\def\enditemize{\ifnum\@listdepth=\@ne\global\@nobotseplisttrue\fi\endlist}
+\def\@sect#1#2#3#4#5#6[#7]#8{%
+ \ifnum #2>\c@secnumdepth
+ \let\@svsec\@empty
+ \else
+ \refstepcounter{#1}%
+ \protected@edef\@svsec{\@seccntformat{#1}\relax}%
+ \fi
+ \@tempskipa #5\relax
+ \ifdim \@tempskipa>\z@
+ \begingroup
+ #6{%
+ \@hangfrom{\hskip #3\relax
+ \ifnum #2=1
+ \colorbox[rgb]{0.99,0.78,0.07}{\kern0.15em\@svsec\kern0.15em}\quad
+ \else
+ \@svsec\quad
+ \fi}%
+ \interlinepenalty \@M #8\@@par}%
+ \endgroup
+ \csname #1mark\endcsname{#7}%
+ \addcontentsline{toc}{#1}{%
+ \ifnum #2>\c@secnumdepth \else
+ \protect\numberline{\csname the#1\endcsname}%
+ \fi
+ #7}%
+ \else
+ \def\@svsechd{%
+ #6{\hskip #3\relax
+ \@svsec #8}%
+ \csname #1mark\endcsname{#7}%
+ \addcontentsline{toc}{#1}{%
+ \ifnum #2>\c@secnumdepth \else
+ \protect\numberline{\csname the#1\endcsname}%
+ \fi
+ #7}}%
+ \fi
+ \@xsect{#5}}
+\def\@seccntformat#1{\csname the#1\endcsname}
+\def\@biblabel#1{\textcolor{darkgray}{\sffamily\bfseries#1}}
+\def\copyrightline{%
+ \ifx\@serieslogo\@empty
+ \else
+ \setbox\@tempboxa\hbox{\includegraphics[height=42\p@]{\@serieslogo}}%
+ \rlap{\hspace\textwidth\hspace{-\wd\@tempboxa}\hspace{\z@}%
+ \vtop to\z@{\vskip-0mm\unhbox\@tempboxa\vss}}%
+ \fi
+ \scriptsize
+ \vtop{\hsize\textwidth
+ \nobreakspace\\
+ \@Copyright
+ \ifx\@Event\@empty\else\@Event.\\\fi
+ \ifx\@Editors\@empty\else
+ \@Eds: \@Editors
+ ; pp. \thepage--\pageref{LastPage}%
+ \\
+ \fi
+ \setbox\@tempboxa\hbox{\includegraphics[height=14\p@,trim=0 15 0 0]{lipics-logo-bw}}%
+ \hspace*{\wd\@tempboxa}\enskip
+ \href{http://www.dagstuhl.de/lipics/}%
+ {Leibniz International Proceedings in Informatics}\\
+ \smash{\unhbox\@tempboxa}\enskip
+ \href{http://www.dagstuhl.de}%
+ {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik, Dagstuhl Publishing, Germany}}}
+\def\ps@plain{\let\@mkboth\@gobbletwo
+ \let\@oddhead\@empty
+ \let\@evenhead\@empty
+ \let\@evenfoot\copyrightline
+ \let\@oddfoot\copyrightline}
+\def\lipics@opterrshort{Option "\CurrentOption" not supported}
+\def\lipics@opterrlong{The option "\CurrentOption" from article.cls is not supported by lipics.cls.}
+\DeclareOption{a5paper}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{b5paper}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{legalpaper}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{executivepaper}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{landscape}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{10pt}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{11pt}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{12pt}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{oneside}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{twoside}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{titlepage}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{notitlepage}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{onecolumn}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{twocolumn}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{fleqn}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{openbib}{\@latexerr{\lipics@opterrshort}{\lipics@opterrlong}}
+\DeclareOption{a4paper}{\PassOptionsToClass{\CurrentOption}{article}
+ \advance\hoffset-2.95mm
+ \advance\voffset8.8mm}
+\DeclareOption{numberwithinsect}{\let\numberwithinsect\relax}
+\DeclareOption*{\PassOptionsToClass{\CurrentOption}{article}}
+\ProcessOptions
+\LoadClass[twoside,notitlepage,fleqn]{article}
+\renewcommand\normalsize{%
+ \@setfontsize\normalsize\@xpt{13}%
+ \abovedisplayskip 10\p@ \@plus2\p@ \@minus5\p@
+ \abovedisplayshortskip \z@ \@plus3\p@
+ \belowdisplayshortskip 6\p@ \@plus3\p@ \@minus3\p@
+ \belowdisplayskip \abovedisplayskip
+ \let\@listi\@listI}
+\normalsize
+\renewcommand\small{%
+ \@setfontsize\small\@ixpt{11.5}%
+ \abovedisplayskip 8.5\p@ \@plus3\p@ \@minus4\p@
+ \abovedisplayshortskip \z@ \@plus2\p@
+ \belowdisplayshortskip 4\p@ \@plus2\p@ \@minus2\p@
+ \def\@listi{\leftmargin\leftmargini
+ \topsep 4\p@ \@plus2\p@ \@minus2\p@
+ \parsep 2\p@ \@plus\p@ \@minus\p@
+ \itemsep \parsep}%
+ \belowdisplayskip \abovedisplayskip
+}
+\renewcommand\footnotesize{%
+ \@setfontsize\footnotesize{8.5}{9.5}%
+ \abovedisplayskip 6\p@ \@plus2\p@ \@minus4\p@
+ \abovedisplayshortskip \z@ \@plus\p@
+ \belowdisplayshortskip 3\p@ \@plus\p@ \@minus2\p@
+ \def\@listi{\leftmargin\leftmargini
+ \topsep 3\p@ \@plus\p@ \@minus\p@
+ \parsep 2\p@ \@plus\p@ \@minus\p@
+ \itemsep \parsep}%
+ \belowdisplayskip \abovedisplayskip
+}
+\renewcommand\large{\@setfontsize\large{10.5}{13}}
+\renewcommand\Large{\@setfontsize\Large{12}{14}}
+\setlength\parindent{1.5em}
+\setlength\headheight{3mm}
+\setlength\headsep {10mm}
+\setlength\footskip{3mm}
+\setlength\textwidth{140mm}
+\setlength\textheight{222mm}
+\setlength\oddsidemargin{32mm}
+\setlength\evensidemargin{38mm}
+\setlength\marginparwidth{25mm}
+\setlength\topmargin{13mm}
+\setlength{\skip\footins}{2\baselineskip \@plus 4\p@ \@minus 2\p@}
+\def\@listi{\leftmargin\leftmargini
+ \parsep\z@ \@plus\p@
+ \topsep 8\p@ \@plus2\p@ \@minus4\p@
+ \itemsep \parsep}
+\let\@listI\@listi
+\@listi
+\def\@listii {\leftmargin\leftmarginii
+ \labelwidth\leftmarginii
+ \advance\labelwidth-\labelsep
+ \topsep 4\p@ \@plus2\p@ \@minus\p@
+ \parsep\z@ \@plus\p@
+ \itemsep \parsep}
+\def\@listiii{\leftmargin\leftmarginiii
+ \labelwidth\leftmarginiii
+ \advance\labelwidth-\labelsep
+ \topsep 2\p@ \@plus\p@\@minus\p@
+ \parsep \z@
+ \partopsep \p@ \@plus\z@ \@minus\p@
+ \itemsep \z@ \@plus\p@}
+\def\ps@headings{%
+ \def\@evenhead{\large\sffamily\bfseries
+ \llap{\hbox to0.5\oddsidemargin{\thepage\hss}}\leftmark\hfil}%
+ \def\@oddhead{\large\sffamily\bfseries\rightmark\hfil
+ \rlap{\hbox to0.5\oddsidemargin{\hss\thepage}}}%
+ \def\@oddfoot{\hfil
+ \rlap{%
+ \vtop{%
+ \vskip10mm
+ \colorbox[rgb]{0.99,0.78,0.07}
+ {\@tempdima\evensidemargin
+ \advance\@tempdima1in
+ \advance\@tempdima\hoffset
+ \hb@xt@\@tempdima{%
+ \textcolor{darkgray}{\normalsize\sffamily
+ \bfseries\quad
+ \expandafter\textsolittle
+ \expandafter{\@EventShortName}}%
+ \strut\hss}}}}}
+ \let\@evenfoot\@empty
+ \let\@mkboth\markboth
+ \let\sectionmark\@gobble
+ \let\subsectionmark\@gobble}
+\pagestyle{headings}
+\renewcommand\maketitle{\par
+ \begingroup
+ \renewcommand\thefootnote{\@fnsymbol\c@footnote}%
+ \if@twocolumn
+ \ifnum \col@number=\@ne
+ \@maketitle
+ \else
+ \twocolumn[\@maketitle]%
+ \fi
+ \else
+ \newpage
+ \global\@topnum\z@ % Prevents figures from going at top of page.
+ \@maketitle
+ \fi
+ \thispagestyle{plain}\@thanks
+ \endgroup
+ \setcounter{footnote}{0}%
+ \global\let\thanks\relax
+ \global\let\maketitle\relax
+ \global\let\@maketitle\relax
+ \global\let\@thanks\@empty
+ \global\let\@author\@empty
+ \global\let\@date\@empty
+ \global\let\@title\@empty
+ \global\let\title\relax
+ \global\let\author\relax
+ \global\let\date\relax
+ \global\let\and\relax
+}
+\newwrite\tocfile
+\def\@maketitle{%
+ \newpage
+ \null\vskip-\baselineskip
+ \vskip-\headsep
+ \@titlerunning
+ \@authorrunning
+ \let \footnote \thanks
+ \parindent\z@ \raggedright
+ {\LARGE\sffamily\bfseries\mathversion{bold}\@title \par}%
+ \vskip 1.5em%
+ \ifnum\c@authors=0 %
+ \@latexerr{No \noexpand\author given}%
+ {Provide at least one author. See the LIPIcs class documentation.}%
+ \else
+ \@author
+ \fi
+ \bgroup
+ \let\footnote\@gobble
+ \immediate\openout\tocfile=\jobname.vtc
+ \protected@write\tocfile{}{%
+ \string\contitem
+ \string\title{\@title}%
+ \string\author{\AB@authfortoc}%
+ \string\page{\thepage}}%
+ \closeout\tocfile
+ \egroup
+ \par}
+\setcounter{secnumdepth}{4}
+\renewcommand\section{\@startsection {section}{1}{\z@}%
+ {-3.5ex \@plus -1ex \@minus -.2ex}%
+ {2.3ex \@plus.2ex}%
+ {\sffamily\Large\bfseries\raggedright}}
+\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
+ {-3.25ex\@plus -1ex \@minus -.2ex}%
+ {1.5ex \@plus .2ex}%
+ {\sffamily\Large\bfseries\raggedright}}
+\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
+ {-3.25ex\@plus -1ex \@minus -.2ex}%
+ {1.5ex \@plus .2ex}%
+ {\sffamily\Large\bfseries\raggedright}}
+\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
+ {-3.25ex \@plus-1ex \@minus-.2ex}%
+ {1.5ex \@plus .2ex}%
+ {\sffamily\large\bfseries\raggedright}}
+\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\z@}%
+ {3.25ex \@plus1ex \@minus .2ex}%
+ {-1em}%
+ {\sffamily\normalsize\bfseries}}
+\setlength\leftmargini \parindent
+\setlength\leftmarginii {1.2em}
+\setlength\leftmarginiii{1.2em}
+\setlength\leftmarginiv {1.2em}
+\setlength\leftmarginv {1.2em}
+\setlength\leftmarginvi {1.2em}
+\renewcommand\labelenumi{%
+ \textcolor{darkgray}{\sffamily\bfseries\mathversion{bold}\theenumi.}}
+\renewcommand\labelenumii{%
+ \textcolor{darkgray}{\sffamily\bfseries\mathversion{bold}\theenumii.}}
+\renewcommand\labelenumiii{%
+ \textcolor{darkgray}{\sffamily\bfseries\mathversion{bold}\theenumiii.}}
+\renewcommand\labelenumiv{%
+ \textcolor{darkgray}{\sffamily\bfseries\mathversion{bold}\theenumiv.}}
+\renewcommand\labelitemi{%
+ \textcolor[rgb]{0.6,0.6,0.61}{\ifnum\@listdepth=\@ne
+ \rule{0.67em}{0.33em}%
+ \else
+ \rule{0.45em}{0.225em}%
+ \fi}}
+\renewcommand\labelitemii{%
+ \textcolor[rgb]{0.6,0.6,0.61}{\rule{0.45em}{0.225em}}}
+\renewcommand\labelitemiii{%
+ \textcolor[rgb]{0.6,0.6,0.61}{\sffamily\bfseries\textasteriskcentered}}
+\renewcommand\labelitemiv{%
+ \textcolor[rgb]{0.6,0.6,0.61}{\sffamily\bfseries\textperiodcentered}}
+\renewenvironment{description}
+ {\list{}{\advance\partopsep\topsep\topsep\z@\@plus\p@
+ \labelwidth\z@ \itemindent-\leftmargin
+ \let\makelabel\descriptionlabel}}
+ {\ifnum\@listdepth=\@ne\global\@nobotseplisttrue\fi\endlist}
+\renewcommand*\descriptionlabel[1]{%
+ \hspace\labelsep\textcolor{darkgray}{\sffamily\bfseries\mathversion{bold}#1}}
+\renewenvironment{abstract}{%
+ \vskip\bigskipamount
+ \noindent
+ \rlap{\color[rgb]{0.51,0.50,0.52}\vrule\@width\textwidth\@height1\p@}%
+ \hspace*{7mm}\fboxsep1.5mm\colorbox[rgb]{1,1,1}{\raisebox{-0.4ex}{%
+ \large\selectfont\sffamily\bfseries\abstractname}}%
+ \vskip3\p@
+ \fontsize{9.5}{12.5}\selectfont
+ \noindent\ignorespaces}
+ {\ifx\@subjclass\@empty\else
+ \vskip\baselineskip\noindent
+ \subjclassHeading\@subjclass
+ \fi
+ \ifx\@keywords\@empty\else
+ \vskip\baselineskip\noindent
+ \keywordsHeading\@keywords
+ \fi
+ \ifx\@DOI\@empty\else
+ \vskip\baselineskip\noindent
+ \doiHeading\doi{\@DOI}%
+ \fi}
+\renewenvironment{thebibliography}[1]
+ {\if@noskipsec \leavevmode \fi
+ \par
+ \@tempskipa-3.5ex \@plus -1ex \@minus -.2ex\relax
+ \@afterindenttrue
+ \@tempskipa -\@tempskipa \@afterindentfalse
+ \if@nobreak
+ \everypar{}%
+ \else
+ \addpenalty\@secpenalty\addvspace\@tempskipa
+ \fi
+ \noindent
+ \rlap{\color[rgb]{0.51,0.50,0.52}\vrule\@width\textwidth\@height1\p@}%
+ \hspace*{7mm}\fboxsep1.5mm\colorbox[rgb]{1,1,1}{\raisebox{-0.4ex}{%
+ \normalsize\sffamily\bfseries\refname}}%
+ \@xsect{1ex \@plus.2ex}%
+ \list{\@biblabel{\@arabic\c@enumiv}}%
+ {\leftmargin8.5mm
+ \labelsep\leftmargin
+ \settowidth\labelwidth{\@biblabel{#1}}%
+ \advance\labelsep-\labelwidth
+ \usecounter{enumiv}%
+ \let\p@enumiv\@empty
+ \renewcommand\theenumiv{\@arabic\c@enumiv}}%
+ \fontsize{9.5}{12.5}\selectfont
+ \sloppy
+ \clubpenalty4000
+ \@clubpenalty \clubpenalty
+ \widowpenalty4000%
+ \sfcode`\.\@m}
+ {\def\@noitemerr
+ {\@latex@warning{Empty `thebibliography' environment}}%
+ \endlist}
+\renewcommand\footnoterule{%
+ \kern-8\p@
+ {\color[rgb]{0.60,0.60,0.61}\hrule\@width40mm\@height1\p@}%
+ \kern6.6\p@}
+\renewcommand\@makefntext[1]{%
+ \parindent\z@\hangindent1em
+ \leavevmode
+ \hb@xt@1em{\@makefnmark\hss}#1}
+\usepackage[utf8]{inputenc}
+\IfFileExists{lmodern.sty}{\RequirePackage{lmodern}}{}
+\RequirePackage[T1]{fontenc}
+\RequirePackage{textcomp}
+\RequirePackage[mathscr]{eucal}
+\RequirePackage{amssymb}
+\RequirePackage{soul}
+\sodef\textsolittle{}{.12em}{.5em\@plus.08em\@minus.06em}%
+ {.4em\@plus.275em\@minus.183em}
+\RequirePackage{color}
+\definecolor{darkgray}{rgb}{0.31,0.31,0.33}
+\RequirePackage{babel}
+\RequirePackage[tbtags,fleqn]{amsmath}
+\RequirePackage{amsthm}
+\thm@headfont{%
+ \textcolor{darkgray}{$\blacktriangleright$}\nobreakspace\sffamily\bfseries}
+\def\th@remark{%
+ \thm@headfont{%
+ \textcolor{darkgray}{$\blacktriangleright$}\nobreakspace\sffamily}%
+ \normalfont % body font
+ \thm@preskip\topsep \divide\thm@preskip\tw@
+ \thm@postskip\thm@preskip
+}
+\def\@endtheorem{\endtrivlist}%\@endpefalse
+\renewcommand\qedsymbol{\textcolor{darkgray}{\ensuremath{\blacktriangleleft}}}
+\renewenvironment{proof}[1][\proofname]{\par
+ \pushQED{\qed}%
+ \normalfont \topsep6\p@\@plus6\p@\relax
+ \trivlist
+ \item[\hskip\labelsep
+ \color{darkgray}\sffamily\bfseries
+ #1\@addpunct{.}]\ignorespaces
+}{%
+ \popQED\endtrivlist%\@endpefalse
+}
+\theoremstyle{plain}
+\newtheorem{theorem}{Theorem}
+\newtheorem{lemma}[theorem]{Lemma}
+\newtheorem{corollary}[theorem]{Corollary}
+\theoremstyle{definition}
+\newtheorem{definition}[theorem]{Definition}
+\newtheorem{example}[theorem]{Example}
+\theoremstyle{remark}
+\newtheorem*{remark}{Remark}
+\ifx\numberwithinsect\relax
+ \@addtoreset{theorem}{section}
+ \edef\thetheorem{\expandafter\noexpand\thesection\@thmcountersep\@thmcounter{theorem}}
+\fi
+\RequirePackage{graphicx}
+\RequirePackage{array}
+\let\@classzold\@classz
+\def\@classz{%
+ \expandafter\ifx\d@llarbegin\begingroup
+ \toks \count@ =
+ \expandafter{\expandafter\small\the\toks\count@}%
+ \fi
+ \@classzold}
+\RequirePackage{multirow}
+\RequirePackage{tabularx}
+\RequirePackage[online]{threeparttable}
+\def\TPTtagStyle#1{#1)}
+\def\tablenotes{\small\TPT@defaults
+ \@ifnextchar[\TPT@setuptnotes\TPTdoTablenotes} % ]
+\RequirePackage{listings}
+\lstset{basicstyle=\small\ttfamily,%
+ backgroundcolor=\color[rgb]{0.85,0.85,0.86},%
+ frame=single,framerule=0pt,xleftmargin=\fboxsep,xrightmargin=\fboxsep}
+\RequirePackage{lastpage}
+\IfFileExists{doi.sty}
+ {\RequirePackage{doi}%
+ \renewcommand*{\doitext}{}}
+ {\RequirePackage{hyperref}%
+ \def\doi##1{##1}}
+\hypersetup{pdfborder={0 0 0}}
+\RequirePackage[labelsep=space,singlelinecheck=false,%
+ font={up,small},labelfont={sf,bf},%
+ listof=false]{caption}%"listof" instead of "list" for backward compatibility
+\@ifpackagelater{hyperref}{2009/12/09}
+ {\captionsetup{compatibility=false}}%cf. http://groups.google.de/group/comp.text.tex/browse_thread/thread/db9310eb540fbbd8/42e30f3b7b3aa17a?lnk=raot
+ {}
+\DeclareCaptionLabelFormat{boxed}{%
+ \kern0.05em{\color[rgb]{0.99,0.78,0.07}\rule{0.73em}{0.73em}}%
+ \hspace*{0.67em}\bothIfFirst{#1}{~}#2}
+\captionsetup{labelformat=boxed}
+\captionsetup[table]{position=top}
+\RequirePackage[figuresright]{rotating}
+\RequirePackage{subfig}
+\def\titlerunning#1{\gdef\@titlerunning{{\let\footnote\@gobble\markboth{#1}{#1}}}}
+\def\authorrunning#1{%
+ \gdef\@authorrunning{\expandafter\def\expandafter\@tempa\expandafter{#1}%
+ \ifx\@tempa\@empty\else\markright{#1}\fi}}
+\titlerunning{\@title}
+\authorrunning{\AB@authrunning}
+\newcommand*\volumeinfo[6]{%
+ {\gdef\@Editors{#1}%
+ \gdef\@Eds{Editor}\ifnum #2>1 \gdef\@Eds{Editors}\fi
+ \gdef\@Event{#3}%
+ \setcounter{page}{#6}}}
+\volumeinfo{}{1}{}{}{}{1}
+\RequirePackage{authblk}
+\renewcommand*\Authand{{ and }}
+\renewcommand*\Authfont{\Large\bfseries\mathversion{bold}}
+\renewcommand*\AB@authnote[1]{\textsuperscript{#1}}
+\renewcommand*\AB@affilnote[1]{\protect\item[#1]}
+\renewcommand*\Affilfont{\fontsize{9.5}{12}\selectfont}
+\setlength\affilsep{\baselineskip}
+\newcommand\AB@authrunning{}
+\newcommand\AB@authfortoc{}
+\renewcommand\author[2][]%
+ {\ifnewaffil\addtocounter{affil}{1}%
+ \edef\AB@thenote{\arabic{affil}}\fi
+ \if\relax#1\relax\def\AB@note{\AB@thenote}\else\def\AB@note{#1}%
+ \setcounter{Maxaffil}{0}\fi
+ \ifnum\value{authors}>1\relax
+ \@namedef{@sep\number\c@authors}{\Authsep}\fi
+ \addtocounter{authors}{1}%
+ \begingroup
+ \let\protect\@unexpandable@protect \let\and\AB@pand
+ \def\thanks{\protect\thanks}\def\footnote{\protect\footnote}%
+ \@temptokena=\expandafter{\AB@authors}%
+ {\def\\{\protect\\[\@affilsep]\protect\Affilfont
+ \protect\AB@resetsep}%
+ \xdef\AB@author{\AB@blk@and#2}%
+ \ifnewaffil\gdef\AB@las{}\gdef\AB@lasx{\protect\Authand}\gdef\AB@as{}%
+ \xdef\AB@authors{\the\@temptokena\AB@blk@and}%
+ \else
+ \xdef\AB@authors{\the\@temptokena\AB@as\AB@au@str}%
+ \global\let\AB@las\AB@lasx\gdef\AB@lasx{\protect\Authands}%
+ \gdef\AB@as{\Authsep}%
+ \fi
+ \gdef\AB@au@str{#2}}%
+ \@temptokena=\expandafter{\AB@authlist}%
+ \let\\=\authorcr
+ \xdef\AB@authlist{\the\@temptokena
+ \protect\@nameuse{@sep\number\c@authors}%
+ \protect\Authfont#2\AB@authnote{\AB@note}}%
+ %new
+ \@temptokena=\expandafter{\AB@authrunning}%
+ \let\\=\authorcr
+ \xdef\AB@authrunning{\the\@temptokena
+ \protect\@nameuse{@sep\number\c@authors}#2}%
+ %
+ %new
+ \@temptokena=\expandafter{\AB@authfortoc}%
+ \let\\=\authorcr
+ \xdef\AB@authfortoc{\the\@temptokena
+ \expandafter\noexpand\csname @sep\number\c@authors\endcsname#2}%
+ %
+ \endgroup
+ \ifnum\value{authors}>2\relax
+ \@namedef{@sep\number\c@authors}{\Authands}\fi
+ \newaffilfalse
+}
+\renewcommand\affil[2][]%
+ {\newaffiltrue\let\AB@blk@and\AB@pand
+ \if\relax#1\relax\def\AB@note{\AB@thenote}\else\def\AB@note{#1}%
+ \setcounter{Maxaffil}{0}\fi
+ \begingroup
+ \let\protect\@unexpandable@protect
+ \def\thanks{\protect\thanks}\def\footnote{\protect\footnote}%
+ \@temptokena=\expandafter{\AB@authors}%
+ {\def\\{\protect\\\protect\Affilfont}\xdef\AB@temp{#2}}%
+ \xdef\AB@authors{\the\@temptokena\AB@las\AB@au@str
+ \protect\\[\affilsep]\protect\Affilfont\AB@temp}%
+ \gdef\AB@las{}\gdef\AB@au@str{}%
+ {\xdef\AB@temp{#2}}%
+ \@temptokena=\expandafter{\AB@affillist}%
+ \xdef\AB@affillist{\the\@temptokena \AB@affilsep
+ \AB@affilnote{\AB@note}\protect\Affilfont\AB@temp}%
+ \endgroup
+ \let\AB@affilsep\AB@affilsepx}
+\renewcommand\@author{\ifx\AB@affillist\AB@empty\AB@authrunning\else
+ \ifnum\value{affil}>\value{Maxaffil}\def\rlap##1{##1}%
+ \AB@authlist\\[\affilsep]
+ \labelwidth1.5em\labelsep\z@\leftmargini\labelwidth
+ \edef\@enumctr{enumi}%
+ \list\theenumi{\usecounter\@enumctr\def\makelabel##1{\rlap{##1}\hss}}%
+ \AB@affillist
+ \endlist
+ \else \AB@authors\fi\fi}
+\newcommand*\Copyright[1]{%
+ \def\@Copyright{%
+ \setbox\@tempboxa\hbox{\includegraphics[height=14\p@,clip]{cc-by}}%
+ \hspace*{\wd\@tempboxa}\enskip\ifx#1\@empty \else \textcopyright\ #1;\\\fi
+ \href{http://creativecommons.org/licenses/by/3.0/}%
+ {\smash{\unhbox\@tempboxa}}\enskip
+ licensed under Creative Commons License CC-BY\\
+ }}
+\Copyright{\@empty}
+\def\keywords#1{\def\@keywords{#1}}
+\let\@keywords\@empty
+\def\keywordsHeading{%
+ \textcolor{darkgray}{\fontsize{9.5}{12.5}\sffamily\bfseries
+ Keywords and phrases\enskip}}
+\def\subjclass#1{\gdef\@subjclass{#1}}
+\let\@subjclass\@empty
+\def\subjclassHeading{%
+ \textcolor{darkgray}{\fontsize{9.5}{12.5}\sffamily\bfseries
+ 1998 ACM Subject Classification\enskip}}
+\def\doiHeading{%
+ \textcolor{darkgray}{\fontsize{9.5}{12.5}\sffamily\bfseries
+ Digital Object Identifier\enskip}}
+\def\serieslogo#1{\gdef\@serieslogo{#1}}
+\serieslogo{}
+\def\EventShortName#1{\gdef\@EventShortName{#1}}
+\EventShortName{}
+\def\DOI#1{\gdef\@DOI{#1}}
+\DOI{}
+\endinput
+%%
+%% End of file `lipics.cls'.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/re-java.data Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,20 @@
+%% LaTeX2e file `re-java.data'
+%% generated by the `filecontents' environment
+%% from source `corr_pr_sketch' on 2019/06/08.
+%%
+5 0.00298
+10 0.00418
+15 0.00996
+16 0.01710
+17 0.03492
+18 0.03303
+19 0.05084
+20 0.10177
+21 0.19960
+22 0.41159
+23 0.82234
+24 1.70251
+25 3.36112
+26 6.63998
+27 13.35120
+28 29.81185
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/re-js.data Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,15 @@
+%% LaTeX2e file `re-js.data'
+%% generated by the `filecontents' environment
+%% from source `corr_pr_sketch' on 2019/06/08.
+%%
+5 0.061
+10 0.061
+15 0.061
+20 0.070
+23 0.131
+25 0.308
+26 0.564
+28 1.994
+30 7.648
+31 15.881
+32 32.190
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/re-python.data Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,22 @@
+%% LaTeX2e file `re-python.data'
+%% generated by the `filecontents' environment
+%% from source `corr_pr_sketch' on 2019/06/08.
+%%
+1 0.029
+5 0.029
+10 0.029
+15 0.032
+16 0.042
+17 0.042
+18 0.055
+19 0.084
+20 0.136
+21 0.248
+22 0.464
+23 0.899
+24 1.773
+25 3.505
+26 6.993
+27 14.503
+28 29.307
+#29 58.886
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/re-python2.data Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,19 @@
+%% LaTeX2e file `re-python2.data'
+%% generated by the `filecontents' environment
+%% from source `corr_pr_sketch' on 2019/06/08.
+%%
+1 0.033
+5 0.036
+10 0.034
+15 0.036
+18 0.059
+19 0.084
+20 0.141
+21 0.248
+22 0.485
+23 0.878
+24 1.71
+25 3.40
+26 7.08
+27 14.12
+28 26.69
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/re-ruby.data Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,32 @@
+%% LaTeX2e file `re-ruby.data'
+%% generated by the `filecontents' environment
+%% from source `corr_pr_sketch' on 2019/06/08.
+%%
+1 0.00006
+#2 0.00003
+#3 0.00001
+#4 0.00001
+5 0.00001
+#6 0.00002
+#7 0.00002
+#8 0.00004
+#9 0.00007
+10 0.00013
+#11 0.00026
+#12 0.00055
+#13 0.00106
+#14 0.00196
+15 0.00378
+16 0.00764
+17 0.01606
+18 0.03094
+19 0.06508
+20 0.12420
+21 0.25393
+22 0.51449
+23 1.02174
+24 2.05998
+25 4.22514
+26 8.42479
+27 16.88678
+28 34.79653
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ecp/root.bib Tue Jun 25 18:56:52 2019 +0100
@@ -0,0 +1,350 @@
+@article{HosoyaVouillonPierce2005,
+ author = {H.~Hosoya and J.~Vouillon and B.~C.~Pierce},
+ title = {{R}egular {E}xpression {T}ypes for {XML}},
+ journal = {ACM Transactions on Programming Languages and Systems (TOPLAS)},
+ year = {2005},
+ volume = 27,
+ number = 1,
+ pages = {46--90}
+}
+
+
+@Misc{POSIX,
+ title = {{T}he {O}pen {G}roup {B}ase {S}pecification {I}ssue 6 {IEEE} {S}td 1003.1 2004 {E}dition},
+ year = {2004},
+ note = {\url{http://pubs.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap09.html}}
+}
+
+
+@InProceedings{AusafDyckhoffUrban2016,
+ author = {F.~Ausaf and R.~Dyckhoff and C.~Urban},
+ title = {{POSIX} {L}exing with {D}erivatives of {R}egular {E}xpressions ({P}roof {P}earl)},
+ year = {2016},
+ booktitle = {Proc.~of the 7th International Conference on Interactive Theorem Proving (ITP)},
+ volume = {9807},
+ series = {LNCS},
+ pages = {69--86}
+}
+
+@article{aduAFP16,
+ author = {F.~Ausaf and R.~Dyckhoff and C.~Urban},
+ title = {{POSIX} {L}exing with {D}erivatives of {R}egular {E}xpressions},
+ journal = {Archive of Formal Proofs},
+ year = 2016,
+ note = {\url{http://www.isa-afp.org/entries/Posix-Lexing.shtml}, Formal proof development},
+ ISSN = {2150-914x}
+}
+
+
+@TechReport{CrashCourse2014,
+ author = {N.~B.~B.~Grathwohl and F.~Henglein and U.~T.~Rasmussen},
+ title = {{A} {C}rash-{C}ourse in {R}egular {E}xpression {P}arsing and {R}egular
+ {E}xpressions as {T}ypes},
+ institution = {University of Copenhagen},
+ year = {2014},
+ annote = {draft report}
+}
+
+@inproceedings{Sulzmann2014,
+ author = {M.~Sulzmann and K.~Lu},
+ title = {{POSIX} {R}egular {E}xpression {P}arsing with {D}erivatives},
+ booktitle = {Proc.~of the 12th International Conference on Functional and Logic Programming (FLOPS)},
+ pages = {203--220},
+ year = {2014},
+ volume = {8475},
+ series = {LNCS}
+}
+
+@inproceedings{Sulzmann2014b,
+ author = {M.~Sulzmann and P.~van Steenhoven},
+ title = {{A} {F}lexible and {E}fficient {ML} {L}exer {T}ool {B}ased on {E}xtended {R}egular
+ {E}xpression {S}ubmatching},
+ booktitle = {Proc.~of the 23rd International Conference on Compiler Construction (CC)},
+ pages = {174--191},
+ year = {2014},
+ volume = {8409},
+ series = {LNCS}
+}
+
+@book{Pierce2015,
+ author = {B.~C.~Pierce and C.~Casinghino and M.~Gaboardi and
+ M.~Greenberg and C.~Hri\c{t}cu and
+ V.~Sj\"{o}berg and B.~Yorgey},
+ title = {{S}oftware {F}oundations},
+ year = {2015},
+ publisher = {Electronic textbook},
+ note = {\url{http://www.cis.upenn.edu/~bcpierce/sf}}
+}
+
+@Misc{Kuklewicz,
+ author = {C.~Kuklewicz},
+ title = {{R}egex {P}osix},
+ howpublished = "\url{https://wiki.haskell.org/Regex_Posix}"
+}
+
+@article{Vansummeren2006,
+ author = {S.~Vansummeren},
+ title = {{T}ype {I}nference for {U}nique {P}attern {M}atching},
+ year = {2006},
+ journal = {ACM Transactions on Programming Languages and Systems},
+ volume = {28},
+ number = {3},
+ pages = {389--428}
+}
+
+@InProceedings{Asperti12,
+ author = {A.~Asperti},
+ title = {{A} {C}ompact {P}roof of {D}ecidability for {R}egular {E}xpression {E}quivalence},
+ booktitle = {Proc.~of the 3rd International Conference on Interactive Theorem Proving (ITP)},
+ pages = {283--298},
+ year = {2012},
+ volume = {7406},
+ series = {LNCS}
+}
+
+@inproceedings{Frisch2004,
+ author = {A.~Frisch and L.~Cardelli},
+ title = {{G}reedy {R}egular {E}xpression {M}atching},
+ booktitle = {Proc.~of the 31st International Conference on Automata, Languages and Programming (ICALP)},
+ pages = {618--629},
+ year = {2004},
+ volume = {3142},
+ series = {LNCS}
+}
+
+@ARTICLE{Antimirov95,
+ author = {V.~Antimirov},
+ title = {{P}artial {D}erivatives of {R}egular {E}xpressions and
+ {F}inite {A}utomata {C}onstructions},
+ journal = {Theoretical Computer Science},
+ year = {1995},
+ volume = {155},
+ pages = {291--319}
+}
+
+@inproceedings{Nipkow98,
+ author={T.~Nipkow},
+ title={{V}erified {L}exical {A}nalysis},
+ booktitle={Proc.~of the 11th International Conference on Theorem Proving in Higher Order Logics (TPHOLs)},
+ series={LNCS},
+ volume=1479,
+ pages={1--15},
+ year=1998
+}
+
+@article{Brzozowski1964,
+ author = {J.~A.~Brzozowski},
+ title = {{D}erivatives of {R}egular {E}xpressions},
+ journal = {Journal of the {ACM}},
+ volume = {11},
+ number = {4},
+ pages = {481--494},
+ year = {1964}
+}
+
+@article{Leroy2009,
+ author = {X.~Leroy},
+ title = {{F}ormal {V}erification of a {R}ealistic {C}ompiler},
+ journal = {Communications of the ACM},
+ year = 2009,
+ volume = 52,
+ number = 7,
+ pages = {107--115}
+}
+
+@InProceedings{Paulson2015,
+ author = {L.~C.~Paulson},
+ title = {{A} {F}ormalisation of {F}inite {A}utomata {U}sing {H}ereditarily {F}inite {S}ets},
+ booktitle = {Proc.~of the 25th International Conference on Automated Deduction (CADE)},
+ pages = {231--245},
+ year = {2015},
+ volume = {9195},
+ series = {LNAI}
+}
+
+@Article{Wu2014,
+ author = {C.~Wu and X.~Zhang and C.~Urban},
+ title = {{A} {F}ormalisation of the {M}yhill-{N}erode {T}heorem based on {R}egular {E}xpressions},
+ journal = {Journal of Automatic Reasoning},
+ year = {2014},
+ volume = {52},
+ number = {4},
+ pages = {451--480}
+}
+
+@InProceedings{Regehr2011,
+ author = {X.~Yang and Y.~Chen and E.~Eide and J.~Regehr},
+ title = {{F}inding and {U}nderstanding {B}ugs in {C} {C}ompilers},
+ pages = {283--294},
+ year = {2011},
+ booktitle = {Proc.~of the 32nd ACM SIGPLAN Conference on Programming Language Design and
+ Implementation (PLDI)}
+}
+
+@Article{Norrish2014,
+ author = {A.~Barthwal and M.~Norrish},
+ title = {{A} {M}echanisation of {S}ome {C}ontext-{F}ree {L}anguage {T}heory in {HOL4}},
+ journal = {Journal of Computer and System Sciences},
+ year = {2014},
+ volume = {80},
+ number = {2},
+ pages = {346--362}
+}
+
+@Article{Thompson1968,
+ author = {K.~Thompson},
+ title = {{P}rogramming {T}echniques: {R}egular {E}xpression {S}earch {A}lgorithm},
+ journal = {Communications of the ACM},
+ issue_date = {June 1968},
+ volume = {11},
+ number = {6},
+ year = {1968},
+ pages = {419--422}
+}
+
+@article{Owens2009,
+ author = {S.~Owens and J.~H.~Reppy and A.~Turon},
+ title = {{R}egular-{E}xpression {D}erivatives {R}e-{E}xamined},
+ journal = {Journal of Functinal Programming},
+ volume = {19},
+ number = {2},
+ pages = {173--190},
+ year = {2009}
+}
+
+@inproceedings{Sulzmann2015,
+ author = {M.~Sulzmann and P.~Thiemann},
+ title = {{D}erivatives for {R}egular {S}huffle {E}xpressions},
+ booktitle = {Proc.~of the 9th International Conference on Language and Automata Theory
+ and Applications (LATA)},
+ pages = {275--286},
+ year = {2015},
+ volume = {8977},
+ series = {LNCS}
+}
+
+@inproceedings{Chen2012,
+ author = {H.~Chen and S.~Yu},
+ title = {{D}erivatives of {R}egular {E}xpressions and an {A}pplication},
+ booktitle = {Proc.~in the International Workshop on Theoretical
+ Computer Science (WTCS)},
+ pages = {343--356},
+ year = {2012},
+ volume = {7160},
+ series = {LNCS}
+}
+
+@article{Krauss2011,
+ author={A.~Krauss and T.~Nipkow},
+ title={{P}roof {P}earl: {R}egular {E}xpression {E}quivalence and {R}elation {A}lgebra},
+ journal={Journal of Automated Reasoning},
+ volume=49,
+ pages={95--106},
+ year=2012
+}
+
+@InProceedings{Traytel2015,
+ author = {D.~Traytel},
+ title = {{A} {C}oalgebraic {D}ecision {P}rocedure for {WS1S}},
+ booktitle = {Proc.~of the 24th Annual Conference on Computer Science Logic (CSL)},
+ pages = {487--503},
+ series = {LIPIcs},
+ year = {2015},
+ volume = {41}
+}
+
+@inproceedings{Traytel2013,
+ author={D.~Traytel and T.~Nipkow},
+ title={{A} {V}erified {D}ecision {P}rocedure for {MSO} on
+ {W}ords {B}ased on {D}erivatives of {R}egular {E}xpressions},
+ booktitle={Proc.~of the 18th ACM SIGPLAN International Conference on Functional Programming (ICFP)},
+ pages={3-12},
+ year=2013
+}
+
+@InProceedings{Coquand2012,
+ author = {T.~Coquand and V.~Siles},
+ title = {{A} {D}ecision {P}rocedure for {R}egular {E}xpression {E}quivalence in {T}ype {T}heory},
+ booktitle = {Proc.~of the 1st International Conference on Certified Programs and Proofs (CPP)},
+ pages = {119--134},
+ year = {2011},
+ volume = {7086},
+ series = {LNCS}
+}
+
+@InProceedings{Almeidaetal10,
+ author = {J.~B.~Almeida and N.~Moriera and D.~Pereira and S.~M.~de Sousa},
+ title = {{P}artial {D}erivative {A}utomata {F}ormalized in {C}oq},
+ booktitle = {Proc.~of the 15th International Conference on Implementation
+ and Application of Automata (CIAA)},
+ pages = {59-68},
+ year = {2010},
+ volume = {6482},
+ series = {LNCS}
+}
+
+@article{Owens2008,
+ author = {S.~Owens and K.~Slind},
+ title = {{A}dapting {F}unctional {P}rograms to {H}igher {O}rder {L}ogic},
+ journal = {Higher-Order and Symbolic Computation},
+ volume = {21},
+ number = {4},
+ year = {2008},
+ pages = {377--409}
+}
+
+
+@article{Owens2,
+ author = {S.~Owens and K.~Slind},
+ title = {Adapting functional programs to higher order logic},
+ journal = {Higher-Order and Symbolic Computation},
+ volume = {21},
+ number = {4},
+ pages = {377--409},
+ year = {2008},
+ url = {http://dx.doi.org/10.1007/s10990-008-9038-0},
+ doi = {10.1007/s10990-008-9038-0},
+ timestamp = {Wed, 16 Dec 2009 13:51:02 +0100},
+ biburl = {http://dblp.uni-trier.de/rec/bib/journals/lisp/OwensS08},
+ bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@misc{PCRE,
+ title = "{PCRE - Perl Compatible Regular Expressions}",
+ url = {http://www.pcre.org},
+}
+
+
+
+@InProceedings{OkuiSuzuki2010,
+ author = {S.~Okui and T.~Suzuki},
+ title = {{D}isambiguation in {R}egular {E}xpression {M}atching via
+ {P}osition {A}utomata with {A}ugmented {T}ransitions},
+ booktitle = {Proc.~of the 15th International Conference on Implementation
+ and Application of Automata (CIAA)},
+ year = {2010},
+ volume = {6482},
+ series = {LNCS},
+ pages = {231--240}
+}
+
+
+
+@TechReport{OkuiSuzukiTech,
+ author = {S.~Okui and T.~Suzuki},
+ title = {{D}isambiguation in {R}egular {E}xpression {M}atching via
+ {P}osition {A}utomata with {A}ugmented {T}ransitions},
+ institution = {University of Aizu},
+ year = {2013}
+}
+
+@inproceedings{Davis18,
+ author = {J.~C.~Davis and C.~.A.~Coghlan and F.~Servant and D.~Lee},
+ title = {{T}he {I}mpact of {R}egular {E}xpression {D}enial of {S}ervice ({ReDoS}) in
+ {P}ractice: {A}n {E}mpirical {S}tudy at the {E}cosystem {S}cale},
+ booktitle = {Proc.~of the 26th ACM Joint Meeting on European Software Engineering
+ Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE)},
+ year = {2018},
+ pages = {246--256},
+ numpages = {11}
+}
\ No newline at end of file
--- a/lex_blex_Frankensteined.scala Wed May 08 22:09:59 2019 +0100
+++ b/lex_blex_Frankensteined.scala Tue Jun 25 18:56:52 2019 +0100
@@ -384,11 +384,12 @@
case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2)
case r1 :: rs2 => r1 :: flats(rs2)
}
+ /*
def remove(v: Val): Val = v match{
case Right(v1) => v1
case Left(v1) => v1
case _ => throw new Exception("Not removable")
- }
+ }*/
def augment(v: Val, i: Int): Val = if(i > 1) augment(Right(v), i - 1) else Right(v)
//an overly complex version
/*
@@ -448,24 +449,30 @@
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r))
case r => r
}
- def find_pos(v: Val, rs: List[Rexp]): Int = (v, rs) match{
- case (Right(v), r::Nil) => 1
- case (Left(v), r::rs) => 0
+ def find_pos(v: Val, rs: List[ARexp]): Int = (v, rs) match{
+ case (v, r::Nil) => 0
case (Right(v), r::rs) => find_pos(v, rs) + 1
- case (v, _) => 0
+ case (Left(v), r::rs) => 0
+ //case (v, _) => 0
+ }
+ def find_pos_aux(v: Val, r: ARexp): Int = r match {
+ case AALTS(bs, rs) => find_pos(v, rs)
+ case r => 0
}
- def remove(v: Val, rs: List[Rexp]) : Val = (v,rs) match {//remove the outmost layer of ALTS's Left and Right
- case (Right(v), r::Nil) => v
+ def remove(v: Val, rs: List[ARexp]) : Val = (v,rs) match {//remove the outmost layer of ALTS's Left and Right
+ //we have to use r to detect the bound of nested L/Rs
+ case (v, r::Nil) => v
+ case (Right(v), r::rs) => remove(v, rs)
case (Left(v), r::rs) => v
- case (Right(v), r::rs) => remove(v, rs)
+ //case (v, r::Nil) => v
}
def simple_end(v: Val): Boolean = v match {
case Left(v) => return false
case Right(v) => return simple_end(v)
case v => return true
}
- def isend(v: Val, rs: List[ARexp], position: Int): Boolean = {
- val rsbh = rs.slice(position, rs.length)
+ def isend(v: Val, rs: List[ARexp], position: Int): Boolean = {//TODO: here the slice api i am not familiar with so this call might be incorrect and crash the bsimp2
+ val rsbh = rs.slice(position + 1, rs.length)
val out_end = if(flats(rsbh) == Nil) true else false
val inner_end = simple_end(v)
inner_end && out_end
@@ -479,7 +486,72 @@
case 0 => v
case i => coat(Right(v), i - 1)
}
- /*
+ //This version takes a regex and a value, return a simplified regex and its corresponding simplified value
+ def bsimp2(r: ARexp, v: Val): (ARexp, Val) = (r,v) match{
+ case (ASEQ(bs1, r1, r2), Sequ(v1, v2)) => (bsimp2(r1, v1), bsimp2(r2, v2)) match {
+ case ((AZERO, _), (_, _) )=> (AZERO, undefined)
+ case ((_, _), (AZERO, _)) => (AZERO, undefined)
+ case ((AONE(bs2), v1s) , (r2s, v2s)) => (fuse(bs1 ++ bs2, r2s), v2s )//v2 tells how to retrieve bits in r2s, which is enough as the bits of the first part of the sequence has already been integrated to the top level of the second regx.
+ case ((r1s, v1s), (r2s, v2s)) => (ASEQ(bs1, r1s, r2s), Sequ(v1s, v2s))
+ }
+ case (AALTS(bs1, rs), v) => {
+ //phase 1 transformation so that aalts(bs1, rs) => aalts(bs1, rsf) and v => vf
+ val init_ind = find_pos(v, rs)
+ //println(rs)
+ //println(v)
+ val vs = bsimp2(rs(init_ind), remove(v, rs))//remove all the outer layers of left and right in v to match the regx rs[i]
+ //println(vs)
+ val rs_simp = rs.map(bsimp)
+ val vs_kernel = rs_simp(init_ind) match {
+ case AALTS(bs2, rs2) => remove(vs._2, rs2)//remove the secondary layer of left and right
+ case r => vs._2
+ }
+ val flat_res = flats(rs_simp)
+ //println(rs_simp)
+ //println(flat_res)
+ //println(init_ind)
+ val vs_for_coating = if(isend(vs._2, rs_simp, init_ind)||flat_res.length == 1) vs_kernel else Left(vs_kernel)
+ //println(vs_for_coating)
+ val r_s = rs_simp(init_ind)//or vs._1
+ val shift = flats_vsimp(rs_simp, init_ind) + find_pos_aux(vs._2, rs_simp(init_ind))
+ //println(shift)
+ val new_ind = init_ind + shift
+ //println("new ind:")
+ //println(new_ind)
+ val vf = coat(vs_for_coating, new_ind)
+ //println("vf:")
+ //println(vf)
+ //flats2 returns a list of regex and a single v
+ //now |- vf: ALTS(bs1, flat_res)
+
+ //phase 2 transformation so that aalts(bs1, rsf) => aalts(bs, rsdb) and vf => vdb
+ val dist_res = distinctBy(flat_res, erase)
+ val front_part = distinctBy(flat_res.slice(0, new_ind + 1), erase)
+ //val size_reduction = new_ind + 1 - front_part.length
+ //println(flat_res.length)
+ //println(dist_res)
+ //println(front_part)
+ val vdb = if(dist_res.length == front_part.length )//that means the regex we are interested in is at the end of the list
+ {
+ coat(vs_kernel, front_part.length - 1)
+ }
+ else{
+ coat(Left(vs_kernel), front_part.length - 1)
+ }
+ //println(vdb)
+ //we don't need to transform vdb as this phase will not make enough changes to the regex to affect value.
+ //the above statement needs verification. but can be left as is now.
+ dist_res match {
+ case Nil => (AZERO, undefined)
+ case s :: Nil => (fuse(bs1, s), vdb)
+ case rs => (AALTS(bs1, rs), vdb)
+ }
+ }
+ //case ASTAR(bs, r) => ASTAR(bs, bsimp(r))
+ case (r, v) => (r, v)
+ }
+ def vsimp(r: ARexp, v: Val): Val = bsimp2(r, v)._2
+ /*This version was first intended for returning a function however a value would be simpler.
def bsimp2(r: ARexp, v: Val): (ARexp, Val => Val) = (r,v) match{
case (ASEQ(bs1, r1, r2), v) => (bsimp2(r1), bsimp2(r2)) match {
case ((AZERO, _), (_, _) )=> (AZERO, undefined)
@@ -890,5 +962,6 @@
case class Right(v: Val) extends Val
case class Stars(vs: List[Val]) extends Val
case class Rec(x: String, v: Val) extends Val
+case object undefined extends Val
//case class Pos(i: Int, v: Val) extends Val
case object Prd extends Val