17 \newcommand*{\mybox}[1]{\framebox{\strut #1}} |
17 \newcommand*{\mybox}[1]{\framebox{\strut #1}} |
18 |
18 |
19 %\newcommand{\sflataux}[1]{\textit{sflat}\_\textit{aux} \, #1} |
19 %\newcommand{\sflataux}[1]{\textit{sflat}\_\textit{aux} \, #1} |
20 \newcommand\sflat[1]{\llparenthesis #1 \rrparenthesis } |
20 \newcommand\sflat[1]{\llparenthesis #1 \rrparenthesis } |
21 \newcommand{\ASEQ}[3]{\textit{ASEQ}_{#1} \, #2 \, #3} |
21 \newcommand{\ASEQ}[3]{\textit{ASEQ}_{#1} \, #2 \, #3} |
22 \newcommand{\bderssimp}[2]{#1 \backslash_{bsimp} #2} |
22 \newcommand{\bderssimp}[2]{#1 \backslash_{bsimps} #2} |
23 \newcommand{\rderssimp}[2]{#1 \backslash_{rsimp} #2} |
23 \newcommand{\rderssimp}[2]{#1 \backslash_{rsimp} #2} |
24 \newcommand{\bders}[2]{#1 \backslash #2} |
24 \newcommand{\bders}[2]{#1 \backslash #2} |
25 \newcommand{\bsimp}[1]{\textit{bsimp}(#1)} |
25 \newcommand{\bsimp}[1]{\textit{bsimp}(#1)} |
26 \newcommand{\rsimp}[1]{\textit{rsimp}(#1)} |
26 \newcommand{\rsimp}[1]{\textit{rsimp}(#1)} |
27 \newcommand{\sflataux}[1]{\llparenthesis #1 \rrparenthesis'} |
27 \newcommand{\sflataux}[1]{\llparenthesis #1 \rrparenthesis'} |
28 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
28 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
29 \newcommand{\denote}{\stackrel{\mbox{\scriptsize denote}}{=}}% |
29 \newcommand{\denote}{\stackrel{\mbox{\scriptsize denote}}{=}}% |
30 \newcommand{\ZERO}{\mbox{\bf 0}} |
30 \newcommand{\ZERO}{\mbox{\bf 0}} |
31 \newcommand{\ONE}{\mbox{\bf 1}} |
31 \newcommand{\ONE}{\mbox{\bf 1}} |
32 \newcommand{\AALTS}[2]{\oplus {\scriptstyle #1}\, #2} |
32 \newcommand{\AALTS}[2]{\oplus {\scriptstyle #1}\, #2} |
33 \newcommand{\rdistinct}[2]{\textit{distinct} \; \textit{#1} \; #2} |
33 \newcommand{\rdistinct}[2]{\textit{rdistinct} \; \textit{#1} \; #2} |
34 \newcommand\hflat[1]{\llparenthesis #1 \rrparenthesis_*} |
34 \newcommand\hflat[1]{\llparenthesis #1 \rrparenthesis_*} |
35 \newcommand\hflataux[1]{\llparenthesis #1 \rrparenthesis_*'} |
35 \newcommand\hflataux[1]{\llparenthesis #1 \rrparenthesis_*'} |
36 \newcommand\createdByStar[1]{\textit{createdByStar}(#1)} |
36 \newcommand\createdByStar[1]{\textit{createdByStar}(#1)} |
37 |
37 |
38 \newcommand\myequiv{\mathrel{\stackrel{\makebox[0pt]{\mbox{\normalfont\tiny equiv}}}{=}}} |
38 \newcommand\myequiv{\mathrel{\stackrel{\makebox[0pt]{\mbox{\normalfont\tiny equiv}}}{=}}} |
39 |
39 |
40 \def\bnullable{\textit{bnullable}} |
40 \def\bnullable{\textit{bnullable}} |
|
41 \def\bnullables{\textit{bnullables}} |
41 \def\Some{\textit{Some}} |
42 \def\Some{\textit{Some}} |
42 \def\None{\textit{None}} |
43 \def\None{\textit{None}} |
43 \def\code{\textit{code}} |
44 \def\code{\textit{code}} |
44 \def\decode{\textit{decode}} |
45 \def\decode{\textit{decode}} |
45 \def\internalise{\textit{internalise}} |
46 \def\internalise{\textit{internalise}} |
58 \def\ALTS{\textit{ALTS}} |
59 \def\ALTS{\textit{ALTS}} |
59 \def\ASTAR{\textit{ASTAR}} |
60 \def\ASTAR{\textit{ASTAR}} |
60 \def\DFA{\textit{DFA}} |
61 \def\DFA{\textit{DFA}} |
61 \def\NFA{\textit{NFA}} |
62 \def\NFA{\textit{NFA}} |
62 \def\bmkeps{\textit{bmkeps}} |
63 \def\bmkeps{\textit{bmkeps}} |
|
64 \def\bmkepss{\textit{bmkepss}} |
63 \def\retrieve{\textit{retrieve}} |
65 \def\retrieve{\textit{retrieve}} |
64 \def\blexer{\textit{blexer}} |
66 \def\blexer{\textit{blexer}} |
65 \def\flex{\textit{flex}} |
67 \def\flex{\textit{flex}} |
66 \def\inj{\mathit{inj}} |
68 \def\inj{\mathit{inj}} |
67 \def\Empty{\mathit{Empty}} |
69 \def\Empty{\mathit{Empty}} |
79 %\def\bderssimp{\mathit{bders}\_\mathit{simp}} |
81 %\def\bderssimp{\mathit{bders}\_\mathit{simp}} |
80 \def\distinctWith{\textit{distinctWith}} |
82 \def\distinctWith{\textit{distinctWith}} |
81 \def\lf{\textit{lf}} |
83 \def\lf{\textit{lf}} |
82 \def\PD{\textit{PD}} |
84 \def\PD{\textit{PD}} |
83 \def\suffix{\textit{Suffix}} |
85 \def\suffix{\textit{Suffix}} |
84 |
86 \def\distinctBy{\textit{distinctBy}} |
85 |
87 |
86 \def\size{\mathit{size}} |
88 \def\size{\mathit{size}} |
87 \def\rexp{\mathbf{rexp}} |
89 \def\rexp{\mathbf{rexp}} |
88 \def\simp{\mathit{simp}} |
90 \def\simp{\mathit{simp}} |
89 \def\simpALTs{\mathit{simp}\_\mathit{ALTs}} |
91 \def\simpALTs{\mathit{simp}\_\mathit{ALTs}} |
95 %\def\sflataux{\textit{sflat}\_\textit{aux}} |
97 %\def\sflataux{\textit{sflat}\_\textit{aux}} |
96 \def\rrexp{\textit{rrexp}} |
98 \def\rrexp{\textit{rrexp}} |
97 \newcommand\rnullable[1]{\textit{rnullable}(#1)} |
99 \newcommand\rnullable[1]{\textit{rnullable}(#1)} |
98 \newcommand\rsize[1]{\llbracket #1 \rrbracket_r} |
100 \newcommand\rsize[1]{\llbracket #1 \rrbracket_r} |
99 \newcommand\asize[1]{\llbracket #1 \rrbracket} |
101 \newcommand\asize[1]{\llbracket #1 \rrbracket} |
100 \newcommand\rerase[1]{ (#1)\downarrow_r} |
102 \newcommand\rerase[1]{ (#1)_{\downarrow_r}} |
|
103 |
101 \newcommand\ChristianComment[1]{\textcolor{blue}{#1}\\} |
104 \newcommand\ChristianComment[1]{\textcolor{blue}{#1}\\} |
|
105 |
|
106 |
|
107 \def\rflts{\textit{rflts}} |
|
108 \def\rrewrite{\textit{rrewrite}} |
|
109 \def\bsimpalts{\textit{bsimp}_{ALTS}} |
102 |
110 |
103 \def\erase{\textit{erase}} |
111 \def\erase{\textit{erase}} |
104 \def\STAR{\textit{STAR}} |
112 \def\STAR{\textit{STAR}} |
105 \def\flts{\textit{flts}} |
113 \def\flts{\textit{flts}} |
106 |
114 |
328 They are popular and programming languages' library functions |
336 They are popular and programming languages' library functions |
329 for them are very fast on non-catastrophic cases. |
337 for them are very fast on non-catastrophic cases. |
330 But there are problems with current practical implementations. |
338 But there are problems with current practical implementations. |
331 First thing is that the running time might blow up. |
339 First thing is that the running time might blow up. |
332 The second problem is that they might be error-prone on certain |
340 The second problem is that they might be error-prone on certain |
333 cases that are very easily spotted by a human. |
341 very simple cases. |
334 In the next part of the chapter, we will look into reasons why |
342 In the next part of the chapter, we will look into reasons why |
335 certain regex engines are running horribly slow on the "catastrophic" |
343 certain regex engines are running horribly slow on the "catastrophic" |
336 cases and propose a solution that addresses both of these problems |
344 cases and propose a solution that addresses both of these problems |
337 based on Brzozowski and Sulzmann and Lu's work. |
345 based on Brzozowski and Sulzmann and Lu's work. |
338 |
346 |