% \begin{frame}
%   \frametitle{Complement of Context-Sensitive Languages}
%   
%   \begin{block}{Theorem}
%     For context-sensitive $L$, also $\overline{L}$ is context-sensitive.
%   \end{block}
%   
%   \begin{block}{Idea of Immerman and Szelepcs\'enyi (1987)}
%     Let $M$ be an LBA that accepts $L$.
%     \pause\medskip
% 
%     \emph{Goal:} construct LBA $N$ such that $w \in L(N) \iff w \not\in L(M)$.
%     \pause\medskip
%     
%     Nondeterministic computation of $M$ for $w$ can be seen as a tree.\\
%     The nodes are the program states (configurations).
%     \pause\medskip
%     
%     Idea: when \alert{$N$ is started on input $w$}, then $N$ does
%     \begin{itemize}\setlength{\itemsep}{0pt}
%       \item breadth-first search through computation tree of $M$ for $w$
%       \item if tree contains no accepting configuration, then \alert{$N$ accepts}
%     \end{itemize}
%     \pause
%     \emph{Problem:} how to do this search with linear-bounded memory?
%   \end{block}
% \end{frame}

\themex{Context-Sensitive vs. Recursive Languages}