\documentclass[online,helvetica]{chaksem}

\usepackage[T1]{fontenc}
\usepackage[fleqn]{amsmath}
\usepackage{alltt}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{pstricks,pst-node,pst-plot}
\usepackage{graphics}
\usepackage{haskell}
%\usepackage{grammar}

% misc
%

\renewcommand{\ttdefault}{cmtt}

\newcommand{\code}[1]{\texttt{#1}}
\hsmargin0pt

% names
%
\newcommand{\Haskell}{\textsc{\bfseries Haskell}}
\newcommand{\CToHS}{\textsc{c${\to}$hs}}

% hacks
%
\makeatletter
\newcommand{\fstoversnd}[2]{%
  \newif\ifouterm@th
  \ifmmode\outerm@thtrue\else\outerm@thfalse\fi
  \setbox0=\hbox{\ifouterm@th$#1$\else#1\fi}%
%  \unhcopy0\hskip-\wd0%  % doesn't work in math mode
  #1\hskip-\wd0%          % this does
  \hbox to\wd0{\hfil\ifouterm@th$#2$\else#2\fi\hfil}%
  }
\makeatother


% symbols
%
\newcommand{\reepsilon}{\epsilon}
\newcommand{\reconc}{\mathbin{\triangleright}}
\newcommand{\reor}{\mathbin{\fstoversnd{{\bowtie}}{|}}}
\newcommand{\realt}{\mathbin{\fstoversnd{{\bowtie}}{\|}}}
\newcommand{\restar}{\mathbin{\varoast}}
\newcommand{\replus}{\mathbin{\varoplus}}
\newcommand{\request}{\mathbin{\textsf{?}}}

% PSTricks stuff

\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=3,gridlabels=5pt}
\psset{unit=1ex,                        % scale with font
       linewidth=.6pt}                  % lines shouldn't be too heavy

\newgray{dgray}{.5}
\newgray{fglightgray}{.8}
%\newgray{fglightgray}{.65} % value for ETL's projector
\newgray{bggray}{.8}
\newcmykcolor{lightgreen}{.25 0 .25 0}
\newcmykcolor{ultralightgreen}{.12 0 .12 0}
\newcmykcolor{lightmag}{.05 .25 0 0}
\newcmykcolor{altlightgreen}{.3 0 .1 0}
\newcmykcolor{lightyellow}{0 0 .5 0}
\newcmykcolor{magg}{.3 1 0 0}
\newcmykcolor{dgreen}{1 0 .6 .3}
\newcmykcolor{dblue}{1 1 0 .3}
\newcmykcolor{lightblue}{.5 .5 0 .1}
\newcmykcolor{ultralightblue}{.12 .12 0 0}
\newcmykcolor{dorange}{0 .6 .8 .3}

\newcommand{\bgcolbox}[2]{%
  \psframebox[fillcolor=#1,linestyle=none,fillstyle=solid]{#2}}

\let\emcol=\dorange
\let\headcol=\dblue

% chaksem config
%
\let\toprulecol=\emcol
\let\botrulecol=\headcol


\begin{document}
\begin{slide}
  \vspace*{-.9\bigskipamount}
  \begin{center}
    \vspace*{\fill}
    \huge
    {\dblue Lazy Lexing is Fast}
    \\[1.2em]      
    \Large
    Manuel M. T. \textsc{Chakravarty}\\%[.9em]
    {\dgreen University of Tsukuba, Japan}\\
%    Institute of Information Sciences and Electronics\\
    \texttt{chak@is.tsukuba.ac.jp}\\
    \par\vfill
    \rule{.25\textwidth}{.5pt}
    \par\vfill\bigskip
        \hspace*{\fill}\begin{minipage}{.85\textwidth}
        \begin{slumerate}\large
        \item Combinators Versus Generators
        \item Regular Expressions as Combinators
        \item On-the-fly Transition Graph Construction
        \item A Demonstration
        \end{slumerate}
      \end{minipage}\hspace*{\fill}
  \end{center}%
  \vspace*{-.5\bigskipamount}
\setfooter{%
  \bgcolbox{bggray}{{\upshape Produced with \LaTeX\ seminar style \& PSTricks}}}
\end{slide}

% 30 min (incl discussion)


\begin{slide}
  \heading{Lexical Analysers: Combinators Versus Generators}

  {\headcol Scanner Generators}
  %
  \begin{slitemize}
  \item Special-purpose language translated into functional language
  \item Deterministic, table-driven automata for recognition
  \item High efficiency
  \end{slitemize}

  {\headcol Lexer Combinators}
  %
  \begin{slitemize}
  \item Library of combinators for describing regular expressions etc.
  \item Neither an extra language nor a special tool needed
  \item Lexical syntax can be configured at runtime
  \end{slitemize}

  \begin{center}\emcol
    Can a combinator library employ\\ deterministic table-driven automata?
  \end{center}
\end{slide}

\begin{slide}
%  \subheading{Overview}
%  \resizebox{.4\textwidth}{!}{\includegraphics{overview.eps}}
  \begin{center}\small
    \hskip0pt
    \vspace*{-2.5ex}
    \psset{xunit=5ex, yunit=2.5ex}
    \begin{pspicture}(3,7)(16,27)%\showgrid
%      \rput(3,7.3){\psframe[framearc=0.18,linestyle=none,fillstyle=solid,fillcolor=fglightgray](0,0)(12,7.8)}

      \rput(9.1,26.2){\textsf{\large
          From {\dblue automata construction}
          \snd{to \emcol self-optimising combinators}}}
      \rput(4.1,23.8){\psframe[framearc=0.15,shadow=true](5.8,1.4)}

      \rput(7,24.4){{\sf{Regular expressions \& actions}}}

      \rput(7,23.5){\psline[linewidth=1.5pt,linecolor=dgray]{->}(0,-2.2)}
      \rput[r](6.2,22.4){\dblue \small Thompson's construction}

      \rput(4.7,19.8){\psframe[framearc=0.15,shadow=true](4.6,1.4)}
      \rput(7,20.4){{\sf{Finite automata (FAs)}}}

      \rput(7,19.5){\psline[linewidth=1.5pt,linecolor=dgray]{->}(0,-2.2)}
      \rput[r](6.2,18.4){\dblue \small Merging}

      \rput(3.5,15.8){\psframe[framearc=0.15,shadow=true](7.0,1.4)}
      \rput(7,16.4){{\sf{Combined DFAs (multiple final states)}}}

      \rput(7,15.5){\psline[linewidth=1.5pt,linecolor=dgray]{->}(0,0)(0,-2.2)}
      \rput[r](6.2,14.4){\dblue \small Subset construction}

%      \rput(10,12){\psarc[linecolor=dgreen,linewidth=1.6pt]{->}(0,0){4.5}{190}{125}}
%      \rput[l](10.5,11.1){\psframe[linestyle=none,fillstyle=solid,fillcolor=fglightgray](1,1)}
%      \rput[l](10.5,11.5){%
%        \fstsnd{\magg Calculational Fusion}{\dorange Calculational Fusion}}
      \rput(3.7,11.8){\psframe[framearc=0.15,shadow=true](6.6,1.4)}
      \rput(7,12.4){{\sf{Deterministic finite automaton (DFA)}}}

      \rput(7,11.5){\psline[linewidth=1.5pt,linecolor=dgray]{->}(0,-2.2)}
      \rput[r](6.2,10.4){\dblue \small Optimisation}

      \rput(4.4,7.8){\psframe[framearc=0.15,shadow=true](5.2,1.4)}
      \rput(7,8.4){{\sf{Minimised, compressed DFA}}}

      \begin{second}
%        \rput(9.5,26){\textsf{\large\emcol Self-optimising combinators}}
        \rput(4.0,7.4){\psline[linecolor=dorange,linewidth=1.0pt]{c-c}%
          (6.0,2.2)}
        \rput(4.0,9.6){\psline[linecolor=dorange,linewidth=1.0pt]{c-c}%
          (6.0,-2.2)}
        \pscurve[linecolor=dorange,linewidth=1.0pt]{->}%
          (7.1,23.4)(7.8,20.4)(7.8,16.4)(7.1,13.4)
      \end{second}
      %Oberhack!!!
%      \rput(15.5,7.1){\psframe[linestyle=none,fillstyle=solid,fillcolor=white]%
%        (3,1.1)}

      \begin{third}
        \rput[lt](11,24){%
          \begin{minipage}{.4\textwidth}\flushleft
            \begin{slitemize}
            \item suitable representation of DFA transition tables\smallskip
            \item combinators create, merge, and refine tables\smallskip
            \item lazy table construction (short inputs)
            \end{slitemize}
            \medskip

            \begin{center}\emcol
              We choose a direct representation of the transition graph.
            \end{center}
          \end{minipage}%
          }
      \end{third}
    \end{pspicture}
  \end{center}
\end{slide}

\begin{slide}
  \heading{Regular Expressions as Combinators}

  The usual regular expression for integers{\fglightgray:}
  {\headcol\(\texttt{-}{?}[\texttt{0}\ldots\texttt{9}]{+}\)}
  
  In Haskell, where \verb|quest| and \verb|plus| are \emph{infix}
  operators:
  %
  \begin{quote}\headcol
\begin{verbatim}
(char '-')`quest` (alt ['0'..'9'])`plus` epsilon
\end{verbatim}
  \end{quote}

  With improved type setting:
  {\headcol
    \<(char \hschar{-})\request 
    (alt [\hschar{0}..\hschar{9}])\replus \reepsilon\>}

  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,-2)(69.5,-17)%
  \begin{haskell}
    \hskwd{type} Regexp s t\\
    \reepsilon &:: Regexp s t\\
    char    &:: Char \to Regexp s t\\
    (\reconc), (\reor), (\restar), (\replus), (\request)
    &:: Regexp s t \to Regexp s t \to Regexp s t
  \end{haskell}
  \vspace*{-1.4\bigskipamount}%
  %
  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,2)(69.5,-6)%
  \begin{haskell}
    alt                       &:: [Char] \to Regexp s t\\
    alt [c_1, \ldots, c_n]    &= char c_1 \reor \cdots \reor char c_n
  \end{haskell}
\end{slide}

\begin{slide}[\slidewidth,1.04\slideheight]
  {\headcol An example: A lexer for identifiers}
  \vskip-2.2\bigskipamount

  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,-2.4)(69.5,-19.5)%
  \begin{haskell}
    ident &:: Regexp s t\\
    ident &= letter \reconc (letter \reor digit)\restar \reepsilon
    \hswhere{
      letter &= alt ([\hschar{a}..\hschar{z}] \hsapp [\hschar{A}..\hschar{Z}])\\
      digit  &= alt [\hschar{0}..\hschar{9}]
      }
  \end{haskell}
  %
  \begin{second}%
  \vskip-1.3\bigskipamount
  {\headcol Actions}
  \vskip-2.2\bigskipamount

  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,-2.4)(69.5,-13)%
  \begin{haskell}
    type Lexer s t\\
    type Action t &= String \to Position \to Maybe t\\
    lexaction &:: Regexp s t \to Action t \to Lexer s t
  \end{haskell}%
  \end{second}%
  %
  \begin{third}%
  \vskip-1.9\bigskipamount
  {\headcol The example continued}
  \vskip-2.2\bigskipamount
  
  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,-2.4)(69.5,-16)%
  \begin{haskell*}
    data Token &=& IdentTok String Position\\
    &|& \cdots
  \end{haskell*}
  \vskip-1.5\bigskipamount
  \begin{haskell}
    lexident &:: Lexer s Token\\
    lexident &=  ident \hsifix{lexaction} 
                 (\lambda{}str pos\to Just (IdentTok str pos))%
  \end{haskell}%
  \end{third}%
\end{slide}

\begin{slide}
  {\headcol \ldots and finally}
  \vskip-2.2\bigskipamount
  
  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,-2.4)(69.5,-13.5)%
  \begin{haskell}
    lexer &:: Lexer s Token\\
    lexer &=  \hsalign{%
             & lexident\\
      \realt & char \hschar{~} \hsifix{lexaction} (\lambda{}\_ \_ \to Nothing)
      }
  \end{haskell}

  {\headcol Other features}
  %
  \begin{slitemize}
  \item \<ActionErr\> can flag error conditions
  \item The lexical analyser maintains a user-definable state component
  \item Meta actions can manipulate the current position and the
    user-definable state
  \end{slitemize}
\end{slide}

\begin{slide}
  \heading{On-the-fly Transition Graph Construction}

%  {\headcol The idea:}
  {\headcol Representation of the transition table}{\fglightgray:}
%  {\emcol The idea:}
  %
  \begin{slitemize}
  \item A value of type \<Lexer s t\> is a transition table or state
  \item A value of type \<Regexp s t\> is a transition table {\headcol
      continuation} or an {\headcol open} transition table
%  \item A value of type \<Regexp s t\> is a transition table {
%      continuation} or an { open} transition table
  \item We represent a transition table as a cyclic transition graph of a DFA
    (incremental \& sparse)
  \item The final states are graph nodes associated with an action
  \end{slitemize}
  \vskip-2.2\bigskipamount

  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,-2.4)(69.5,-20)%
  \begin{haskell*}
    data Lexer s t &=& State (LexAction s t) [(Char, Lexer s t)]\\
    data LexAction s t &=& Action   (Action t)\\
                       &|& Meta     (Meta s t)\\
                       &|& NoAction\\
    type Regexp s t &=& Lexer s t \to Lexer s t
  \end{haskell*}

  \<\lambda l \to State ac [(\hschar{a}, l), 
            (\hschar{c}, l), 
            (\hschar{d}, l)]\>
  \psset{unit=1.5ex}
  \begin{pspicture}(-3,-0.8)(5,1.6)
    \pnode(0,0){start}
    \pnode(5,2){a}
    \pnode(5,0){c}
    \pnode(5,-2){d}
    \ncline[linewidth=1pt]{**-oo}{start}{a}\naput{a}
    \ncline[linewidth=1pt]{**-oo}{start}{c}\nput{135}{c}{c}
    \ncline[linewidth=1pt]{**-oo}{start}{d}\nbput{d}
  \end{pspicture}
\end{slide}

\begin{slide}
  {\headcol Basic combinators:}%{\fglightgray:}
  \vskip-2.2\bigskipamount

  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,-2.4)(50,-24)%
  \begin{haskell}
    \reepsilon &:: Regexp s t\\
    \reepsilon &= id\\
    char   &:: Char \to Regexp s t\\
    char c & = \lambda{}l \to State NoAction [(c, l)]\\
    (\reconc) &:: Regexp s t \to Regexp s t \to Regexp s t\\
    (\reconc) &= (\circ)
  \end{haskell}
  %
  {\psset{unit=1.5ex,linewidth=1pt}%
%  \begin{pspicture}(0,-0.8)(5,1.6)
  \begin{pspicture}(0,0)
    \rput(29,13){\dotnode[dotstyle=o](0,0){epshole}}%
  \end{pspicture}%
  %
  \begin{pspicture}(0,0)%
    \rput(29,9){%
      \dotnode(0,0){charhole}%
      \dotnode[dotstyle=o](5,0){charstate}%
      \ncline{-}{charstate}{charhole}\naput{$c$}%
      }
  \end{pspicture}%
  %
  \begin{pspicture}(0,0)%
    \rput(29,5){%
      \dotnode[dotstyle=o](0,0){conchole}%
      \dotnode(5,0){concstate}%
      \ncarc[arcangle=20,linestyle=dashed]{->}{concstate}{conchole}%
      }
  \end{pspicture}}
  \vskip-1.2\bigskipamount
  
  {\headcol Ex:} 
  {\psset{unit=1.5ex,linewidth=1pt}%
  \<char \hschar{a} \reconc char \hschar{b}\>:
  %
  \begin{pspicture}(-2,-.5)(15,.5)
    \dotnode(0,0){exstatea}%
    \dotnode[dotstyle=o](05,0){exholea}%
    \ncline{-}{exstatea}{exholea}\naput{\<\hschar{a}\>}%
    %
    \dotnode(10,0){exstateb}%
    \dotnode[dotstyle=o](15,0){exholeb}%
    \ncline{-}{exstateb}{exholeb}\naput{\<\hschar{b}\>}%
    %
    \ncarc[arcangle=20,linestyle=dashed]{->}{exstateb}{exholea}%
  \end{pspicture}}%
  \vskip-1.2\bigskipamount

  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,-2.4)(69.5,-10)%
  \begin{haskell}
    lexaction &:: Regexp s t \to Action t \to Lexer s t\\
    lexaction re a &= re (State (Action a) [])
  \end{haskell}
  %
  \mbox{{\headcol Ex:} {\psset{unit=1.5ex,linewidth=1pt}%
  \<(char\hsap \hschar{a} \hsap\reconc\hsap char\hsap \hschar{b}) 
  \hsap\hsifix{lexaction}\hsap ac\>:
  %
  \begin{pspicture}(-2,-.5)(15,.5)
    \dotnode(0,0){exstateaa}%
    \dotnode(05,0){exholeaa}%
    \ncline{-}{exstateaa}{exholeaa}\naput{\<\hschar{a}\>}%
    %
    \dotnode[dotstyle=square*](10,0){exstatebb}%
    \ncline{-}{exholeaa}{exstatebb}\naput{\<\hschar{b}\>}%
  \end{pspicture}}}%
\end{slide}

\begin{slide}
  \vspace*{-2.2\bigskipamount}
  {\headcol Disjunction:}%{\fglightgray:}
  \vskip-2.2\bigskipamount

  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,-2.4)(69.5,-10)%
  \begin{haskell}
    (\reor)      &:: Regexp s t \to Regexp s t \to Regexp s t\\
    re \reor re' & = \lambda{}l \to re l \realt re' l
  \end{haskell}
  \vskip-2.8\bigskipamount

  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,-2.4)(69.5,-13)%
  \begin{haskell}
    (\realt) &:: Lexer s t \to Lexer s t \to Lexer s t\\
    (State a c) \realt (State a' c') &= 
      \hsbody{State (joinActions a a') (accum (\realt) (c \hsapp c'))}
  \end{haskell}
  \vskip-0.2\bigskipamount
  %
  \mbox{{\headcol Ex:}
  \<(char\hsap \hschar{a} \hsap\hsifix{lexaxtion}\hsap ac_1) \hsap\realt\hsap
  (char\hsap \hschar{a} \hsap\reconc\hsap char\hsap \hschar{b} 
  \hsap\hsifix{lexaxtion}\hsap ac_2)\>}
  %
  {\psset{unit=1.5ex,linewidth=1pt}%
  \begin{pspicture}(-2,-4)(15,3.5)
    \dotnode(0,0){exstatea}%
    \dotnode[dotstyle=square*](05,0){exholea}%
    \ncline{-}{exstatea}{exholea}\naput{\<\hschar{a}\>}%
    \nput{90}{exholea}{\<ac_1\>}
    %
    \dotnode(0,-2){exstateaa}%
    \dotnode(05,-2){exholeaa}%
    \ncline{-}{exstateaa}{exholeaa}\nbput{\<\hschar{a}\>}%
    %
    \dotnode[dotstyle=square*](10,-2){exstatebb}%
    \ncline{-}{exholeaa}{exstatebb}\nbput{\<\hschar{b}\>}%
    \nput{270}{exstatebb}{\<ac_2\>}
    %
    \ncline[linestyle=dashed]{-}{exstatea}{exstateaa}
    % ->
    \rput(15,-1){$\Longrightarrow$}
    %
    \dotnode(20,-1){exstateaaa}%
    \dotnode[dotstyle=square*](25,-1){exholeaaa}%
    \ncline{-}{exstateaaa}{exholeaaa}\nbput{\<\hschar{a}\>}%
    %
    \dotnode[dotstyle=square*](30,-1){exstatebbb}%
    \ncline{-}{exholeaaa}{exstatebbb}\nbput{\<\hschar{b}\>}%
    \nput{90}{exholeaaa}{\<ac_1\>}
    \nput{90}{exstatebbb}{\<ac_2\>}
  \end{pspicture}}%

  We apply the {\emcol principle of the longest match.}
\end{slide}

\begin{slide}
  {\headcol Repetition:}%{\fglightgray:}
  \vskip-2.2\bigskipamount

  \psframe[framearc=0.15,linestyle=none,fillstyle=solid,fillcolor=fglightgray]%
    (-1,-2.4)(69.5,-10)%
  \begin{haskell}
    (\restar) &:: Regexp s t \to Regexp s t \to Regexp s t\\
    re1\restar re2 &= \hskwd{let} self = (re1 \reconc self \realt \reepsilon) \hskwd{in} self \reconc re2
%    re1\restar re2 &= \lambda{}l' \to 
%    \hskwd{let} self = re1 self \realt (re2 l') \hskwd{in} self
  \end{haskell}

  {\psset{unit=1.5ex,linewidth=1pt}%
  \begin{pspicture}(-2,-3)(15,3)
    \dotnode(0,0){exstatea}%
    \dotnode[dotstyle=o](05,0){exholea}%
    \ncline{-}{exstatea}{exholea}\nbput{\<re_1\>}
    %
    \dotnode(10,0){exstateb}%
    \dotnode[dotstyle=o](15,0){exholeb}%
    \ncline{-}{exstateb}{exholeb}\nbput{\<re_2\>}%
    %
    \ncarc[arcangle=20,linestyle=dashed]{->}{exstateb}{exholea}%
    \ncloop[angleA=90,angleB=90,linestyle=dashed]{->}{exstatea}{exholea}%
    \naput{\small\<self\>}
    % ->
    \rput(20,0){$\Longrightarrow$}
    \dotnode(25,0){exstateaa}%
    \nccircle{->}{exstateaa}{1}\nbput{\<re_1\>}
    %
    \dotnode[dotstyle=o](30,0){exholebb}%
    \ncline{-}{exstateaa}{exholebb}\nbput{\<re_2\>}%
  \end{pspicture}}%

  {\headcol Remarks:}
  %
  \begin{slitemize}
  \item A cyclic graph is constructed
  \item Disjunction of two cyclic structures is problematic
  \item More details are in the paper
  \end{slitemize}
\end{slide}

\begin{slide}
  \heading{Implementation}
  %
  \begin{slitemize}
  \item Implementation as a \Haskell\ module \texttt{Lexers}
  \item Lexer for ANSI C is 220 lines (includes positions and \verb|#line|,
    but no preprocessor)
  \item Naiv\'e input strings (list of \texttt{Char})
  \item {\emcol Demo} \snd{(around 75\% of the efficiency of a handcoded
      lexer)} 
    % * In `CLexers' show `identOrKW', `constant', `intconst' & `opsep'
    % > ll gtkext.h
    % > /tmp/hipar/c gtkext.h
    % (faster than in the paper)
  \end{slitemize}

  \begin{second}
    \begin{slitemize}
    \item \texttt{Lexers} is part of the \Haskell\ Compiler Toolkit (CTK)---a
      library for compiler writers
    \item CTK is, for example, used in the \Haskell\ Interface Generator \CToHS
    \item Webpage of the Compiler Toolkit:
      \begin{center}
        \texttt{http://www.score.is.tsukuba.ac.jp/\string~chak/ctk/}
      \end{center}
    \end{slitemize}
  \end{second}
\end{slide}

\begin{slide}
  \heading{Conclusions}

  {\headcol Lazy evaluation is important in two ways:}
  %
  \begin{slitemize}
  \item We construct cyclic graphs
  \item Partial computation of the transition table for short inputs
  \end{slitemize}

  {\headcol Final remarks:}
  %
  \begin{slitemize}
  \item Swierstra \& Duponcheel use a related technique for parsers
  \item How much would we gain from a more efficient representation of the
    input? 
  \item Could this method be derived from automata theory?
  \end{slitemize}

\end{slide}


\end{document}