\begin{frame}{Basic Properties of Context-Sensitive Languages}
  \begin{goal}{Theorem}
    If $L_1$ and $L_2$ are context-sensitive, then so are
    \begin{talign}
      L_1 \cup L_2 && L_1 \cap L_2 && L_1^R && L_1 L_2 && L_1^* && \overline{L_1} && L_1 \setminus L_2
    \end{talign}
  \end{goal}
  \pause
  
  \begin{proof}
    \begin{itemize}
    \pause
      \item \alert{$L_1 \cup L_2$}, \alert{$L_1^R$}, \alert{$L_1 L_2$}: proof via grammars (same as before)
    \pause
      \item \alert{$L_1^*$}: $S \to S_1 S \mid S_1$ where $S$ is the fresh starting variable
    \pause
      \item \alert{$L_1 \cap L_2$}: run both linear bounded automata in sequence
    \pause
      \item \alert{$L_1 \setminus L_2 = L_1 \cap \overline{L_2}$}
    \pause
      \item \alert{$\overline{L_1}$}: proven by Immerman and Szelepcs\'enyi (1987) \qedhere
    \end{itemize}
  \end{proof}
  \pause\medskip
  
  \begin{goal}{}
    It is \alert{unknown} whether \emph{deterministic} LBA's
    are equally expressive as \emph{nondeterministic} LBA's.
  \end{goal}  
\end{frame}