diff -r 1af5ec39d006 -r a6aa52ecc1c5 slides/slides02.tex
--- a/slides/slides02.tex	Thu Sep 28 19:07:37 2017 +0100
+++ b/slides/slides02.tex	Tue Oct 03 23:01:06 2017 +0100
@@ -104,6 +104,26 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Evil Regular Expressions}
+
+\begin{itemize}
+\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip
+\item Evil regular expressions\medskip
+\begin{itemize}
+\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}
+\item \bl{$(a^*)^*$}
+\item \bl{$([a$\,-\,$z]^+)^*$}
+\item \bl{$(a + a \cdot a)^*$}
+\item \bl{$(a + a?)^*$}
+\end{itemize}
+
+\item sometimes also called \alert{catastrophic backtracking}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -143,7 +163,7 @@
 \frametitle{The Power Operation}
 
 \begin{itemize}
-\item The \alert{\bf Power} of a language:
+\item The \alert{\textbf{\boldmath$n$th Power}} of a language:
 
 \begin{center}
 \begin{tabular}{lcl}
@@ -155,9 +175,9 @@
 \item[] For example
 
 \begin{center}
-\begin{tabular}{lcl}
-\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$}\\
-\bl{$A^1$} & \bl{$=$} & \bl{$A$}\\
+\begin{tabular}{lcll}
+\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(\{[]\})$}\\
+\bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(\{[]\})$}\\
 \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\
 \end{tabular}
 \end{center}
@@ -244,28 +264,7 @@
 \end{textblock}
 
 \end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Specification\\ of Matching\end{tabular}}
-
-\begin{bubble}[10cm]
-\large
-A regular expression \bl{$r$} matches a string~\bl{$s$} 
-provided
-
-\begin{center}
-\bl{$s \in L(r)$}\\ 
-\end{center}
-\end{bubble}\bigskip\bigskip
-
-\ldots and the point of the this lecture is 
-to decide this problem as fast as possible 
-(unlike Python, Ruby, Java etc)
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -301,6 +300,29 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}The Specification\\ of Matching\end{tabular}}
+
+\begin{bubble}[10cm]
+\large
+A regular expression \bl{$r$} matches a string~\bl{$s$} 
+provided
+
+\begin{center}
+\bl{$s \in L(r)$}\\ 
+\end{center}
+\end{bubble}\bigskip\bigskip
+
+\ldots and the point of the this lecture is 
+to decide this problem as fast as possible 
+(unlike Python, Ruby, Java etc)
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \frametitle{Regular Expressions}
@@ -397,101 +419,6 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%\newcommand{\YES}{\textcolor{gray}{yes}}
-%\newcommand{\NO}{\textcolor{gray}{no}}
-%\newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}}
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Specification\\[-1mm] for Matching\end{tabular}}
-
-\large
-A regular expression \bl{$r$} matches a string \bl{$s$}\\ if and only if
-
-\begin{center}
-\bl{$s \in L(r)$}\\ 
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} and \bl{$(a^*)^* \cdot b$}}
-
-\begin{center}\footnotesize
-\begin{tabular}{@{}c@{\hspace{-2mm}}c@{}}
-\begin{tikzpicture}
-\begin{axis}[
-    xlabel={$n$},
-    x label style={at={(1.05,0.0)}},
-    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=5.5cm,
-    height=4.5cm, 
-    legend entries={Python,Ruby},  
-    legend pos=north west,
-    legend cell align=left  
-]
-\addplot[blue,mark=*, mark options={fill=white}] 
-  table {re-python.data};
-\addplot[brown,mark=pentagon*, mark options={fill=white}] 
-  table {re-ruby.data};  
-\end{axis}
-\end{tikzpicture}
-&
-\begin{tikzpicture}
-\begin{axis}[
-    xlabel={$n$},
-    x label style={at={(1.05,0.0)}},
-    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=5.5cm,
-    height=4.5cm, 
-    legend entries={Java},  
-    legend pos=north west,
-    legend cell align=left]
-\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
-\end{axis}
-\end{tikzpicture}
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Evil Regular Expressions}
-
-\begin{itemize}
-\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip
-\item Evil regular expressions\medskip
-\begin{itemize}
-\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}
-\item \bl{$(a^*)^*$}
-\item \bl{$([a$\,-\,$z]^+)^*$}
-\item \bl{$(a + a \cdot a)^*$}
-\item \bl{$(a + a?)^*$}
-\end{itemize}
-
-\item sometimes also called \alert{catastrophic backtracking}
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]