% $Header: /cvsroot/latex-beamer/latex-beamer/examples/beamerexample1.tex,v 1.47 2004/11/04 15:43:51 tantau Exp $

\documentclass{beamer}
%\documentclass{article}
%\usepackage[envcountsect]{beamerarticle}

% Do NOT take this file as a template for your own talks. Use a file
% in the directory solutions instead. They are much better suited.

% Try the class options [notes], [notes=only], [trans], [handout],
% [red], [compress], [draft] and see what happens!

% Copyright 2003 by Till Tantau <tantau@users.sourceforge.net>.
%
% This program can be redistributed and/or modified under the terms
% of the LaTeX Project Public License Distributed from CTAN
% archives in directory macros/latex/base/lppl.txt.

% For a green structure color use:
%\colorlet{structure}{green!50!black}

\mode<article> % only for the article version
{
  \usepackage{fullpage}
  \usepackage{hyperref}
}


\mode<presentation>
{
  \setbeamertemplate{background canvas}[vertical shading][bottom=red!10,top=blue!10]

  \usetheme{Warsaw}
  \usefonttheme[onlysmall]{structurebold}
}

%\setbeamercolor{math text}{fg=green!50!black}
%\setbeamercolor{normal text in math text}{parent=math text}

\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
\usepackage{amsmath,amssymb}
\usepackage[latin1]{inputenc}
\usepackage{colortbl}
\usepackage[english]{babel}

%\usepackage{lmodern}
%\usepackage[T1]{fontenc} 

\usepackage{times}

\setbeamercovered{dynamic}

%
% The following defintions are peculiar to this particular
% presetation. They have nothing to do with the beamer class
%

\newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}

\newcommand{\Class}[1]{\operatorname{\mathchoice
  {\text{\normalfont\small #1}}
  {\text{\normalfont\small #1}}
  {\text{\normalfont#1}}
  {\text{\normalfont#1}}}}

\newcommand{\DOF}{\Class{DOF}}
\newcommand{\NOF}{\Class{NOF}}
\newcommand{\DOFpoly}{\Class{DOF}_{\operatorname{poly}}}
\newcommand{\NOFpoly}{\Class{NOF}_{\operatorname{poly}}}


\newcommand{\Nat}{\mathbb{N}}
\newcommand{\Set}[1]{\{#1\}}

\pgfdeclaremask{computer}{beamer-computer-mask}
\pgfdeclaremask{apple}{beamer-g4-mask}
\pgfdeclaremask{ram}{beamer-ram-mask}

\pgfdeclareimage[interpolate=true,mask=computer,%
                 width=1.8361cm,height=2cm]{computerimage}{beamer-computer}
\pgfdeclareimage[interpolate=true,mask=computer,%
                 width=1.8361cm,height=2cm]{computerworkingimage}{beamer-computerred}
\pgfdeclareimage[interpolate=true,mask=apple,%
                 width=1.625cm,height=2cm]{apple}{beamer-g4}
\pgfdeclareimage[interpolate=true,mask=apple,%
                 width=1.625cm,height=2cm]{appleworking}{beamer-g4red}
\pgfdeclareimage[interpolate=true,mask=ram,%
                 width=3.811cm,height=1cm]{ram}{beamer-ram}

\newcommand{\tape}[9]{%
  \pgfputat{#1}{%
  \pgfsetlinewidth{0.8pt}%
  \pgfrect[stroke]{\pgfxy(0,0)}{\pgfxy(4,0.5)}%
  \pgfsetlinewidth{0.4pt}%
  \pgfline{\pgfxy(0.5,0)}{\pgfxy(0.5,0.5)}%
  \pgfline{\pgfxy(1.0,0)}{\pgfxy(1.0,0.5)}%
  \pgfline{\pgfxy(1.5,0)}{\pgfxy(1.5,0.5)}%
  \pgfline{\pgfxy(2.0,0)}{\pgfxy(2.0,0.5)}%
  \pgfline{\pgfxy(2.5,0)}{\pgfxy(2.5,0.5)}%
  \pgfline{\pgfxy(3.0,0)}{\pgfxy(3.0,0.5)}%
  \pgfline{\pgfxy(3.5,0)}{\pgfxy(3.5,0.5)}%
  %
  \pgfputat{\pgfxy(0.25,0.25)}{\pgfbox[center,center]{#2}}%
  \pgfputat{\pgfxy(0.75,0.25)}{\pgfbox[center,center]{#3}}%
  \pgfputat{\pgfxy(1.25,0.25)}{\pgfbox[center,center]{#4}}%
  \pgfputat{\pgfxy(1.75,0.25)}{\pgfbox[center,center]{#5}}%
  \pgfputat{\pgfxy(2.25,0.25)}{\pgfbox[center,center]{#6}}%
  \pgfputat{\pgfxy(2.75,0.25)}{\pgfbox[center,center]{#7}}%
  \pgfputat{\pgfxy(3.25,0.25)}{\pgfbox[center,center]{#8}}%
  \pgfputat{\pgfxy(3.75,0.25)}{\pgfbox[center,center]{#9}}%
  %
  \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{\structure{tape}}}%
  }%
  %
  \pgfnodecircle{n1}[virtual]{\pgfrelative{#1}{\pgfxy(0.25,0)}}{2pt}%
  \pgfnodecircle{n2}[virtual]{\pgfrelative{#1}{\pgfxy(0.75,0)}}{2pt}%
  \pgfnodecircle{n3}[virtual]{\pgfrelative{#1}{\pgfxy(1.25,0)}}{2pt}%
  \pgfnodecircle{n4}[virtual]{\pgfrelative{#1}{\pgfxy(1.75,0)}}{2pt}%
  \pgfnodecircle{n5}[virtual]{\pgfrelative{#1}{\pgfxy(2.25,0)}}{2pt}%
  \pgfnodecircle{n6}[virtual]{\pgfrelative{#1}{\pgfxy(2.75,0)}}{2pt}%
  \pgfnodecircle{n7}[virtual]{\pgfrelative{#1}{\pgfxy(3.25,0)}}{2pt}%
  \pgfnodecircle{n8}[virtual]{\pgfrelative{#1}{\pgfxy(3.75,0)}}{2pt}%
}

\newcommand{\putmachine}[2]{%
  \pgfputat{#1}{\pgfbox[center,center]{\pgfuseimage{computerimage}}}%
  \pgfputat{\pgfrelative{#1}{\pgfxy(0,-1.4)}}{\pgfbox[center,base]{\structure{#2}}}%
  \pgfnodecircle{machine}[virtual]{\pgfrelative{#1}{\pgfxy(0,1)}}{2pt}%
}
\newcommand{\putmachineworking}[2]{%
  \pgfputat{#1}{\pgfbox[center,center]{\pgfuseimage{computerworkingimage}}}%
  \pgfputat{\pgfrelative{#1}{\pgfxy(0,-1.4)}}{\pgfbox[center,base]{\structure{#2}}}%
  \pgfnodecircle{machine}[virtual]{\pgfrelative{#1}{\pgfxy(0,1)}}{2pt}%
}

\newcommand{\putmachinea}[2]{%
  \pgfputat{#1}{\pgfbox[center,center]{\pgfuseimage{apple}}}%
  \pgfputat{\pgfrelative{#1}{\pgfxy(0,-1.4)}}{\pgfbox[center,base]{\structure{#2}}}%
  \pgfnodecircle{machine}[virtual]{\pgfrelative{#1}{\pgfxy(0,1)}}{2pt}%
}
\newcommand{\putmachineworkinga}[2]{%
  \pgfputat{#1}{\pgfbox[center,center]{\pgfuseimage{appleworking}}}%
  \pgfputat{\pgfrelative{#1}{\pgfxy(0,-1.4)}}{\pgfbox[center,base]{\structure{#2}}}%
  \pgfnodecircle{machine}[virtual]{\pgfrelative{#1}{\pgfxy(0,1)}}{2pt}%
}

\newcommand{\selectpos}[1]{%
   \pgfsetlinewidth{0.6pt}%
   \color{structure}%
   \pgfsetendarrow{\pgfarrowto}%
   \pgfnodeconncurve{machine}{n#1}{90}{-90}{.5cm}{.5cm}%
}

%
% The following info should normally be given in you main file:
%

\title[Computation with Absolutely No~Space~Overhead]{Computation~with Absolutely~No~Space~Overhead}
\author[Hemaspaandra, Mukherji, Tantau]{%
  Lane~Hemaspaandra\inst{1} \and
  Proshanto~Mukherji\inst{1} \and
  Till~Tantau\inst{2}}
\institute[Universities of Rochester and Berlin]{
  \inst{1}%
  Department of Computer Science\\
  University of Rochester
  \and
  \inst{2}%
  Fakultät für Elektrotechnik und Informatik\\
  Technical University of Berlin}
\date[DLT 2003]{Developments in Language Theory Conference, 2003}
\subject{Theoretical Computer Science}

\pgfdeclaremask{tu}{beamer-tu-logo-mask}
\pgfdeclaremask{ur}{beamer-ur-logo-mask}
\pgfdeclareimage[mask=tu,width=0.6cm]{tu-logo}{beamer-tu-logo}
\pgfdeclareimage[mask=ur,width=1cm]{ur-logo}{beamer-ur-logo}

\logo{\vbox{\hbox to 1cm{\hfil\pgfuseimage{tu-logo}}\vskip0.1cm\hbox{\pgfuseimage{ur-logo}}}}


\begin{document}

\frame{\titlepage}

\section<presentation>*{Outline}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents[part=1,pausesections]
\end{frame}

\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[current,currentsubsection]
  \end{frame}
}

\part<presentation>{Main Talk}

\section[Models]{The Model of Overhead-Free Computation}

\subsection[Standard Model]{The Standard Model of Linear Space}

\begin{frame}
  \frametitle{The Standard Model of Linear Space}

  \begin{columns}
    
    \column{4.5cm}
      \note[item]<1>{Point out that \$ is a marker symbol.}
      \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm}
        \only<1| trans:1>{
          \putmachine{\pgfxy(1.75,3)}{Turing machine}
          \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0}
          \selectpos{1}}
        \only<2| handout:0| trans:2>{
          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
          \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{0}
          \selectpos{2}}        
        \only<3| handout:0| trans:3>{
          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
          \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{0}
          \selectpos{8}}        
        \only<4| handout:0| trans:4>{
          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
          \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{\$}
          \selectpos{7}}      
        \only<5| handout:0| trans:0>{
          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
          \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{\$}
          \selectpos{2}}      
        \only<6| handout:0| trans:0>{
          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
          \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{0}{\$}
          \selectpos{3}}      
        \only<7| handout:0| trans:0>{
          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
          \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{0}{\$}
          \selectpos{7}}      
        \only<8| handout:0| trans:0>{
          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
          \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{\$}{\$}
          \selectpos{6}}      
        \only<9| handout:0| trans:0>{
          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
          \tape{\pgfxy(0,5)}{\$}{\$}{\$}{\$}{\$}{\$}{\$}{\$}
          \selectpos{5}}      
        \only<10| handout:0| trans:5>{
          \putmachine{\pgfxy(1.75,3)}{Turing machine}
          \tape{\pgfxy(0,5)}{\$}{\$}{\$}{\$}{\$}{\$}{\$}{\$}
          \selectpos{5}}      
     \end{pgfpicture}
    
    \column{6cm}
      \begin{block}{Characteristics}
      \begin{itemize}
      \item
        Input fills \alert{fixed-size tape}
      \item
        Input may be \alert{modified}
      \item
        Tape alphabet \alert{is larger than}\\ input alphabet
        \note[item]<1>{Stress the larger tape alphabet.}
      \end{itemize}
      \end{block}
  \end{columns}
\end{frame}


\begin{frame}
  \frametitle{Linear Space is a Powerful Model}

  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6cm}
    \pgfsetlinewidth{0.8pt}
    \pgfxyline(-5,0)(5,0)
    
    \pgfsetlinewidth{0.4pt}

    \pgfheaplabeledcentered{2cm}{2.5cm}{$\Class{CFL}$}
    \pgfheaplabeledcentered{3.5cm}{3cm}{\raise10pt\hbox{}$\Class{DLINSPACE}$}
    \pgfheaplabeledcentered{5cm}{4cm}{\raise13pt\hbox{}$\Class{NLINSPACE} = \Class{CSL}$}
    \pgfheaplabeledcentered{6cm}{5cm}{$\Class{PSPACE}$}
    \note[item]{Explain CSL.}
    
    \pgfsetdash{{3pt}{3pt}}{0pt}
    \pgfheaplabeled{\pgfxy(0,3.3)}{\pgfxy(-5,6)}{\pgfxy(5,6)}{}%
    \pgfputat{\pgfxy(-4.6,5.75)}{\pgfbox[left,base]{$\Class{PSPACE}\!\text{-hard}$}}%      
  \end{pgfpicture}
  \note[item]{Point out the connections to formal language theory.}
\end{frame}


\subsection[Our Model]{Our Model of Absolutely No Space Overhead}

\begin{frame}
  \frametitle{Our Model of ``Absolutely No Space Overhead''}

  \transdissolve<7>[duration=0.2]
  
  \begin{columns}

    \column{4.5cm}
      \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm}
        \only<1| trans:1>{%
          \putmachinea{\pgfxy(1.75,3)}{Turing machine}%
          \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0}%
          \selectpos{1}}%
        \only<2| handout:0| trans:2>{%
          \putmachineworkinga{\pgfxy(1.75,3)}{Turing machine}%
          \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{0}%
          \selectpos{2}}%      
        \only<3| handout:0| trans:3>{%
          \putmachineworkinga{\pgfxy(1.75,3)}{Turing machine}%
          \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{0}%
          \selectpos{8}}%      
        \only<4| handout:0| trans:0>{%
          \putmachineworkinga{\pgfxy(1.75,3)}{Turing machine}%
          \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{1}%
          \selectpos{7}}%      
        \only<5| handout:0| trans:0>{%
          \putmachineworkinga{\pgfxy(1.75,3)}{Turing machine}%
          \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{1}%
          \selectpos{2}}%      
        \only<6| handout:0| trans:0>{%
          \putmachineworkinga{\pgfxy(1.75,3)}{Turing machine}%
          \tape{\pgfxy(0,5)}{1}{1}{1}{0}{0}{1}{0}{1}%
          \selectpos{3}}%      
        \only<7| handout:0| trans:4>{%
          \putmachinea{\pgfxy(1.75,3)}{Turing machine}%
          \pgfputat{\pgfxy(1.75,5.5)}{\pgfbox[center,center]{\pgfuseimage{ram}}}%
          \pgfnodecircle{n3}[virtual]{\pgfxy(1.25,5)}{2pt}%
          \selectpos{3}}%      
      \end{pgfpicture}

    \column{6cm}
      \begin{overprint}
      \onslide<1-6| trans:1-3| handout:1>
        \begin{block}{Characteristics}
          \begin{itemize}
          \item
            Input fills \alert{fixed-size tape}
          \item
            Input may be \alert{modified}
          \item
            Tape alphabet \alert{equals}\\
            input alphabet
          \end{itemize}
        \end{block}
      \onslide<7-| trans:4| handout:2>
        \begin{alertblock}{Intuition}
          \begin{itemize}
          \item
            Tape is used like a\\ RAM module.
          \end{itemize}
        \end{alertblock}
      \end{overprint}
  \end{columns}
  \note[item]<6>{Point out that no markers are used.}
\end{frame}


\begin{frame}
  \frametitle{Definition of Overhead-Free Computations}

  \begin{Definition}
    A Turing machine is \alert{overhead-free} if
    \begin{enumerate}
    \item
      it has only a single tape,
    \item
      writes only on input cells,
    \item
      writes only symbols drawn from the input alphabet.
    \end{enumerate}
  \end{Definition}
\end{frame}

\begin{frame}
  \frametitle{Overhead-Free Computation Complexity Classes}

  \begin{Definition}
    A language $L \subseteq \Sigma^*$ is in
    \begin{description}
    \item[\alert<1| handout:0| trans:0>{$\DOF$}%
      {\note[item]<1>{Joke about German pronunciation}}]
      if $L$ is accepted by a deterministic overhead-free machine with
      input alphabet~$\Sigma$,
      \pause
    \item[\alert<2| handout:0| trans:0>{$\DOFpoly$}]
      if $L$ is accepted by a deterministic overhead-free machine with
      input alphabet~$\Sigma$ in polynomial time.
      \pause
    \item[\alert<3| handout:0| trans:0>{$\NOF$}]
      is the nondeterministic  version of $\DOF$,
      \note[item]<3>{Stress meaning of D and N.}
      \pause
    \item[\alert<4| handout:0| trans:0>{$\NOFpoly$}]
      is the nondeterministic version of $\DOFpoly$. 
    \end{description}
  \end{Definition}
\end{frame}

\begin{frame}
  \frametitle{Simple Relationships among\\ Overhead-Free Computation Classes}

  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6cm}
    \pgfsetlinewidth{0.8pt}
    \pgfxyline(-5,0)(5,0)
    
    \pgfsetlinewidth{0.4pt}

    \pgfheaplabeledcentered{1.75cm}{2cm}{$\DOFpoly$}
    \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOF$}
    \pgfheaplabeledcentered{2.5cm}{3.5cm}{$\NOFpoly$}
    \pgfheaplabeledcentered{5cm}{4cm}{$\NOF$}

    \pgfheaplabeledcentered{6cm}{5cm}{\raise10pt\hbox{}$\Class{NLINSPACE}$}
  \end{pgfpicture}
\end{frame}


\section[Power of the Model]{The Power of Overhead-Free Computation}


\subsection{Palindromes}

\begin{frame}
  \frametitle{Palindromes Can be Accepted in an Overhead-Free Way}

  \begin{columns}

    \column{4.5cm}
      \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm}
        \only<1| trans:1>{
          \putmachinea{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0}
          \selectpos{1}}
        \only<2| handout:0| trans:0>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{0}
          \selectpos{2}}      
        \only<3| handout:0| trans:0>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{0}
          \selectpos{8}}
        \only<4| handout:0| trans:2>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{1}
          \selectpos{7}}      
        \only<5| handout:0| trans:0>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{1}
          \selectpos{1}}      
        \only<6| handout:0| trans:3>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{1}{1}{0}{0}{1}{0}{1}
          \selectpos{2}}      
        \only<7| handout:0| trans:0>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{1}{1}{0}{0}{1}{0}{1}
          \selectpos{8}}      
        \only<8| handout:0| trans:4>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{1}{1}{0}{0}{1}{1}{0}
          \selectpos{7}}      
        \only<9| handout:0| trans:0>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{1}{1}{0}{0}{1}{1}{0}
          \selectpos{2}}      
        \only<10| handout:0| trans:0>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{1}{0}
          \selectpos{3}}      
        \only<11| handout:0| trans:0>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{1}{0}
          \selectpos{7}}      
        \only<12| handout:0| trans:5>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0}
          \selectpos{6}}      
        \only<13| handout:0| trans:0>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0}
          \selectpos{3}}      
        \only<14| handout:0| trans:0>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{0}{0}{1}{0}{1}{0}{0}
          \selectpos{4}}      
        \only<15| handout:0| trans:0>{
          \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{0}{0}{1}{0}{1}{0}{0}
          \selectpos{6}}      
        \only<16| handout:0| trans:6>{
          \putmachinea{\pgfxy(1.75,3)}{overhead-free machine}
          \tape{\pgfxy(0,5)}{0}{0}{0}{1}{1}{0}{0}{0}
          \selectpos{5}}      
      \end{pgfpicture}

    \column{6cm}
      \begin{block}{Algorithm}
        \alert<1| handout:0| trans:1>{Phase 1:\\
        Compare first and last bit}

        \quad \alert<2| handout:0| trans:2>{Place left end marker}

        \quad \alert<3| handout:0| trans:2>{Place right end marker}
        \vskip1em

        \alert<4| handout:0| trans:3->{Phase 2:\\
        Compare bits next to end markers}
        
        \quad \alert<5,9,13| handout:0| trans:0>{Find left end marker}

        \quad \alert<6,10,14| handout:0| trans:0>{Advance left end marker}

        \quad \alert<7,11,15| handout:0| trans:0>{Find right end marker}

        \quad \alert<8,12,16| handout:0| trans:0>{Advance right end marker}
        
      \end{block}
  \end{columns}
  \note<1>{Use 3 minutes.}
\end{frame}

\begin{frame}
  \frametitle{Relationships among Overhead-Free Computation Classes}

  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5cm}
    \pgfsetlinewidth{0.8pt}
    \pgfxyline(-5,0)(5,0)
    
    \pgfsetlinewidth{0.4pt}

    \pgfheaplabeledcentered{1.75cm}{2cm}{$\DOFpoly$}
    \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOF$}
    \pgfheaplabeledcentered{2.5cm}{3.5cm}{$\NOFpoly$}
    \pgfheaplabeledcentered{5cm}{4cm}{$\NOF$}

    \pgfputat{\pgfxy(0,0.25)}{\pgfbox[center,base]{\alert{Palindromes}}}
  \end{pgfpicture}
\end{frame}


\subsection{Linear Languages}

\begin{frame}
  \frametitle{A Review of Linear Grammars}

  \begin{Definition}<1>
    A grammar is \alert{linear} if it is context-free and\\ there is
    only one nonterminal per right-hand side.
  \end{Definition}

  \begin{Example}<1>
    $G_1\colon S \to 00S0 \mid 1$ and $G_2\colon S \to 0S10 \mid 0$.
  \end{Example}

  \begin{Definition}<2->
    A grammar is \alert{deterministic} if\\ ``there is always only one
    rule that can be applied.''
    \note<2>{Just explain intution.}
  \end{Definition}

  \begin{Example}<2->
    $G_1\colon S \to 00S0 \mid 1$ is deterministic.
    
    $G_2\colon S \to 0S10 \mid 0$ is \alert{not} deterministic.
  \end{Example} 
\end{frame}


\begin{frame}
  \frametitle{Deterministic Linear Languages\\ Can Be Accepted in an
    Overhead-Free Way}

  \begin{Theorem}
    Every deterministic linear language is in $\DOFpoly$.
  \end{Theorem}
\end{frame}

\begin{frame}[<+->]
  \frametitle{Metalinear Languages\\ Can Be Accepted in an
    Overhead-Free Way}

  \begin{Definition}
    A language is \alert{metalinear} if it is the concatenation\\ of
    linear languages.
  \end{Definition}

  \begin{Example}
    $\Lang{triple-palindrome} = \Set{uvw \mid \text{$u$, $v$, and $w$ are palindromes}}$.
  \end{Example}  

  \begin{Theorem}
    Every metalinear language is in $\NOFpoly$.
  \end{Theorem}
\end{frame}

\begin{frame}
  \frametitle{Relationships among Overhead-Free Computation Classes}

  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5cm}
    \pgfsetlinewidth{0.8pt}
    \pgfxyline(-5,0)(5,0)
    
    \pgfsetlinewidth{0.4pt}

    \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOFpoly$}
    \pgfheaplabeledcentered{4.25cm}{4cm}{$\NOFpoly$}
    \pgfheaplabeledcentered{5cm}{5cm}{$\NOF$}

    \color{red}%
    \pgfheaplabeledcentered{1.75cm}{2cm}{\raise10pt\hbox{}deterministic}
    \pgfheaplabeledcentered{2.5cm}{3.5cm}{metalinear}

    \pgfputat{\pgfxy(0,0.6)}{\pgfbox[center,base]{linear}}
  \end{pgfpicture}
  \note[item]{Skip next subsection if more than 18 minutes have passed.}
\end{frame}


\subsection[Forbidden Subword]{Context-Free Languages with a Forbidden Subword}

\begin{frame}
  \frametitle{Definition of Almost-Overhead-Free Computations}

  \begin{Definition}
    A Turing machine is \alert{almost-overhead-free} if
    \begin{enumerate}[<+-| alert@+>]
    \item it has only a single tape,
    \item writes only on input cells,
    \item writes only symbols drawn from the input alphabet\\
      plus one special symbol.
    \end{enumerate}
  \end{Definition}
\end{frame}

\begin{frame}
  \frametitle{Context-Free Languages with a Forbidden Subword\\ Can Be
    Accepted in an Overhead-Free Way}

  \begin{Theorem}
    Let $L$ be a context-free language with a forbidden word.\\
    Then $L  \in \NOFpoly$.
  \end{Theorem}

  \begin{overprint}
  \onslide<1| handout:0| trans:0| article:0>
    \hfill\hyperlinkframestartnext{\beamerskipbutton{Skip proof}}
  \onslide<2| handout:1| trans:1>
    \begin{proof}
      Every context-free language can be accepted by a nondeterministic
      almost-overhead-free machine in polynomial time.
    \end{proof}
  \end{overprint}
\end{frame}

\begin{frame}
  \frametitle{Relationships among Overhead-Free Computation Classes}

  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5cm}
    \pgfsetlinewidth{0.8pt}
    \pgfxyline(-5,0)(5,0)
    
    \pgfsetlinewidth{0.4pt}

    \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOFpoly$}
    \pgfheaplabeledcentered{4.25cm}{4cm}{$\NOFpoly$}
    \pgfheaplabeledcentered{5cm}{5cm}{$\NOF$}

    \color{red}%
    \pgfheaplabeledcentered{2.5cm}{3.5cm}{CFL with}

    \pgfputat{\pgfxy(0,1.6)}{\pgfbox[center,base]{forbidden subwords}}
  \end{pgfpicture}
\end{frame}



\subsection[Complete Languages]{Languages Complete for Polynomial Space}

\begin{frame}<1>[label=pspacecomplete]
  \frametitle{Overhead-Free Languages can be PSPACE-Complete}

  \begin{Theorem}
    $\DOF$ contains languages that are complete for
    $\Class{PSPACE}$. 
  \end{Theorem}

  \only<1| article:0| trans:0| handout:0>
  {
    \vskip1em

    \hyperlink{pspacecomplete<2>}{\beamergotobutton{Proof details}}
  }
  \only<2>
  {% this is only shown in the appendix, where this frame is resumed.
    \begin{proof}
      \begin{enumerate}
      \item
        Let $A \in \Class{DLINSPACE}$ be $\Class{PSPACE}$-complete.\\
        Such languages are known to exist.
      \item
        Let $M$ be a linear space machine that accepts~$A \subseteq
        \Set{0,1}^*$ with tape alphabet~$\Gamma$.
      \item
        Let $h \colon \Gamma \to \Set{0,1}^*$ be an isometric, injective
        homomorphism.
      \item
        Then $h(L)$ is in $\Class{DOF}$ and it is
        $\Class{PSPACE}$-complete. \qedhere
      \end{enumerate}
    \end{proof}

    \only<beamer>{\hfill\hyperlink{pspacecomplete<1>}{\beamerreturnbutton{Return}}}
  }
\end{frame}

\begin{frame}
  \frametitle{Relationships among Overhead-Free Computation Classes}

  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6cm}
    \pgfsetlinewidth{0.8pt}
    \pgfxyline(-5,0)(5,0)
    
    \pgfsetlinewidth{0.4pt}

    \pgfheaplabeledcentered{1.75cm}{2cm}{$\DOFpoly$}
    \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOF$}
    \pgfheaplabeledcentered{2.5cm}{3.5cm}{$\NOFpoly$}
    \pgfheaplabeledcentered{5cm}{4cm}{$\NOF$}

    \pgfsetdash{{3pt}{3pt}}{0pt}
    \pgfheaplabeled{\pgfxy(0,2.9)}{\pgfxy(-5,6)}{\pgfxy(5,6)}{}%
    \pgfputat{\pgfxy(-4.6,5.75)}{\pgfbox[left,base]{$\Class{PSPACE}\!\text{-hard}$}}%      
  \end{pgfpicture}
\end{frame}


\section[Limitations of the Model]{Limitations of Overhead-Free Computation}


\subsection[Strict Inclusion]{Linear Space is Strictly More Powerful}

\begin{frame}
  \frametitle{Some Context-Sensitive Languages\\
    Cannot be Accepted in an Overhead-Free Way}

  \begin{Theorem}
    $\DOF \subsetneq \Class{DLINSPACE}$.    
  \end{Theorem}
  
  \begin{Theorem}
    $\NOF \subsetneq \Class{NLINSPACE}$.    
  \end{Theorem}

  \vskip1em
  The proofs are based on old diagonalisations due to Feldman, Owings,
  and Seiferas.  
\end{frame}

\begin{frame}
  \frametitle{Relationships among Overhead-Free Computation Classes}

  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6cm}
    \pgfsetlinewidth{0.8pt}
    \pgfxyline(-5,0)(5,0)
    
    \pgfsetlinewidth{0.4pt}

    \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOF$}
    \pgfheaplabeledcentered{5cm}{4cm}{$\NOF$}

    \pgfheaplabeledcentered{4.3cm}{4.5cm}{\raise8pt\hbox{}$\Class{DLINSPACE}$}
    \pgfheaplabeledcentered{6cm}{5cm}{\raise10pt\hbox{}$\Class{NLINSPACE}$}

    \pgfsetdash{{3pt}{3pt}}{0pt}
    \pgfheaplabeled{\pgfxy(0,2.9)}{\pgfxy(-5,6)}{\pgfxy(5,6)}{}%
    \pgfputat{\pgfxy(-4.6,5.75)}{\pgfbox[left,base]{$\Class{PSPACE}$-hard}}%      
  \end{pgfpicture}
\end{frame}

\begin{frame}
  \frametitle{Candidates for Languages that\\
    Cannot be Accepted in an Overhead-Free Way}

  \begin{overprint}
  \onslide<all:1>
    \begin{block}{Conjecture}
      \strut
      $\Lang{double-palindromes} \notin \Class{DOF}$.
    \end{block}

  \onslide<all:2>
    \begin{alertblock}{Theorem\vphantom{j}}
      \strut
      $\Lang{double-palindromes} \in \Class{DOF}$.
    \end{alertblock}
  \end{overprint}
 
  \begin{block}{Conjecture}
    $\Set{ww \mid w\in \Set{0,1}^*} \notin \Class{NOF}$. 
  \end{block}

  \vskip1em
  \uncover<1>{Proving the first conjecture would show $\Class{DOF} \subsetneq
  \Class{NOF}$.}
\end{frame}


\section*{Summary}

\subsection<presentation>*{Summary}

\begin{frame}
  \frametitle<presentation>{Summary}

  \begin{block}{}
    \begin{itemize}
    \item
      Overhead-free computation is a more faithful\\
      \alert{model of fixed-size memory}.
    \item
      Overhead-free computation is \alert{less powerful} than linear space.
    \item
      \alert{Many} context-free languages can be accepted\\
      by overhead-free machines.
    \item
      We conjecture that \alert{all} context-free languages are in
      $\NOFpoly$.
    \item
      Our results can be seen as new results on the power of\\
      \alert{linear bounded automata with fixed alphabet} size.
    \end{itemize}
  \end{block}

  \note[item]{Point out result concerning all context-free languages.}
  \note[item]{Relationship to restart automata.}
\end{frame}



\subsection<presentation>*{Further Reading}

\begin{frame}
  \frametitle<presentation>{For Further Reading}
  
  \beamertemplatebookbibitems
  
  \begin{thebibliography}{10}
    
  \bibitem{sal:b:formal-languages}
    A.~Salomaa.
    \newblock {\em Formal Languages}.
    \newblock Academic Press, 1973.
    \pause

  \beamertemplatearticlebibitems
  \bibitem{dij:j:smoothsort}
    E.~Dijkstra.
    \newblock Smoothsort, an alternative for sorting in situ.
    \newblock {\em Science of Computer Programming}, 1(3):223--233,
    1982.
    \pause

  \bibitem{FeldmanO1973}
    E.~Feldman and J.~Owings, Jr.
    \newblock A class of universal linear bounded automata.
    \newblock {\em Information Sciences}, 6:187--190, 1973.
    \pause

  \bibitem{JancarMPV1995}
    P.~Jan{\v c}ar, F.~Mr{\'a}z, M.~Pl{\'a}tek, and J.~Vogel.
    \newblock Restarting automata.
    \newblock {\em FCT Conference 1995}, LNCS 985, pages
    282--292. 1995.
  \end{thebibliography}
\end{frame}


%
% The following appendix material is not shown in the normal course of
% the presentation 
%

\appendix

\AtBeginSubsection{}


\section{\appendixname}

\frame{\frametitle{Appendix Outline}\tableofcontents}


\subsection{Complete Languages}

\againframe<beamer| beamer:2>{pspacecomplete}


\subsection{Improvements for Context-Free Languages}

\begin{frame}
  \frametitle{Improvements}

  \begin{theorem}
    \begin{enumerate}
    \item
      $\Class{DCFL} \subseteq \DOFpoly$.
    \item
      $\Class{CFL} \subseteq \NOFpoly$.
    \end{enumerate}
  \end{theorem}
\end{frame}


\subsection{Abbreviations}

\begin{frame}
  \frametitle{Explanation of Different Abbreviations}

  \begin{table}
    \rowcolors[]{1}{structure!25!averagebackgroundcolor}{structure!10!averagebackgroundcolor}
    \begin{tabular}{ll}
      \structure{$\DOF$} & \structure{D}eterministic \structure{O}verhead-\structure{F}ree.\\
      \structure{$\NOF$} & \structure{N}ondeterministic \structure{O}verhead-\structure{F}ree.\\
      \structure{$\DOFpoly$} & \structure{D}eterministic
      \structure{O}verhead-\structure{F}ree, \structure{poly}nomial time.\\
      \structure{$\DOFpoly$} & \structure{N}ondeterministic \structure{O}verhead-\structure{F}ree, \structure{poly}nomial time.
    \end{tabular}
    \caption{Explanation of what different abbreviations mean.}
  \end{table}
\end{frame}

\end{document}