Commits

Till Tantau  committed e91e698

*** empty log message ***

  • Participants
  • Parent commits 5501575

Comments (0)

Files changed (16)

-2001-11-04 Till Tantau <tantau@users.sourceforge.net>
+2003-11-11 Till Tantau <tantau@users.sourceforge.net>
+
+	- Added part managment and documented it.
+	- Changed \appendix to use \part internally. Appendix can now
+	  contain numerous sections.
+	- Added \nameslide commands for inserting slides into the article
+	  version. 
+	- Added draft option.
+	- Fixed bug with \pause and notesonly
+	- Fixed problem with Chinese fonts in navigation bars.
+
+2003-11-04 Till Tantau <tantau@users.sourceforge.net>
 
 	Version 0.93:
 	- Added \article, \common, \presentation macros for creating an
 %
 % Stuff needed in both article and presentation version
 %
+\def\jobnamebeamerversion{}%
+
 \def\includeslide{\@ifnextchar[{\@includeslide}{\@includeslide[]}}
-\def\@includeslide[#1]#2#3{%
-  \edef\beamer@temp{#1 page \csname beamer@slide#2\endcsname}
-  \expandafter\pdfximage\beamer@temp{#3.pdf}\pdfrefximage\pdflastximage}
+\def\@includeslide[#1]#2{%
+  \ifx\jobnamebeamerversion\@empty%
+  \ClassError{beamer}{Invoke macro "setjobnamebeamerversion" first}{}%
+  \else%
+  \pgfimage[#1,page=\csname beamer@slide#2\endcsname]{\jobnamebeamerversion}
+  \fi}
+
+\def\setjobnamebeamerversion#1{%
+  \def\jobnamebeamerversion{#1}%
+  {\makeatletter
+  \@input{\jobnamebeamerversion.snm}}
+}
 
 
 
 
 \def\beamer@transfer{%
   % Prepare...
-  \def\beamer@slide##1##2{\expandafter\def\csname
+  \def\beamer@slide##1##2{\expandafter\gdef\csname
     beamer@slide##1\endcsname{##2}}
-  \@input{\jobname.snm}
 
   \beamer@inpresentationfalse
   \edef\beamer@classwhat{[\beamer@classoptions]{\beamer@classname}}
 
 \newif\ifbeamer@centered
 
+\newif\ifbeamer@draftmode
+\beamer@draftmodefalse
 
 %
 %
 \DeclareOption{bigger}{\def\beamer@size{{size12.clo}}}
 \DeclareOption{smaller}{\def\beamer@size{{size10.clo}}}
 
+\DeclareOption{draft}{\beamer@draftmodetrue}
+\AtBeginDocument{
+  \ifbeamer@draftmode
+  \gdef\@foottemplate{%
+    \color{black!25}%
+    \kern-\Gm@lmargin\vrule width\paperwidth
+    height\footheight\kern-\Gm@rmargin}
+  \gdef\@headtemplate{%
+    \color{black!25}%
+    \kern-\Gm@lmargin\vrule width\paperwidth
+    height\headheight\kern-\Gm@rmargin}
+  \gdef\beamer@leftsidebartemplate{%
+    \color{black!20}%
+    \vrule width \beamer@leftsidebar height\sidebarheight}
+  \gdef\beamer@rightsidebartemplate{%
+    \color{black!20}%
+    \vrule width \beamer@rightsidebar height\sidebarheight}
+  \gdef\beamer@leftsidebarbackground{}
+  \gdef\beamer@rightsidebarbackground{}
+  \fi
+  }
+\def\insertpagenumber{\thepage}
+
+\def\beamer@activecjk{}
+
+\DeclareOption{CJK}{\ExecuteOptions{cjk}}
+\DeclareOption{cjk}{
+  \hypersetup{CJKbookmarks=true}
+
+  \def\beamer@activecjk{
+    % Activate all >128 characters. 
+    \count@=127
+    \@whilenum\count@<255 \do{%
+      \advance\count@ by 1
+      \lccode`\~=\count@
+      \catcode\count@=\active
+      \lowercase{\def~{\kern1ex}}
+    }
+  }  
+}
+  
 %
 %
 % Process Options
 
 \expandafter\input\beamer@size
 
+
 %
 %
 % Declarations used by beamer
 % Empty test
 %
 %
-\long\def\@ifempty#1#2#3{\def\@shouldbeempty{#1}\ifx\@shouldbeempty\@empty#2\else#3\fi}
-
-
-
-%
-% Page where the appendix start. (Updated later)
-%
-\def\beamer@appendixstart{1}
+\long\def\@ifempty#1{\beamer@xifempty#1@@..\@nil}
+\long\def\beamer@xifempty#1#2@#3#4#5\@nil{%
+  \ifx#3#4\expandafter\@firstoftwo\else\expandafter\@secondoftwo\fi}
+
+
+
 
 % Calculate maximum number of sections/subsections per part
 \newcount\beamer@sectioncount
 \beamer@sectioncount=0\relax
 
 \newcount\totalheads
-\def\headcommand#1{\advance\totalheads by1\relax\expandafter\def\csname
+\def\headcommand#1{\global\advance\totalheads by1\relax\expandafter\gdef\csname
   head\the\totalheads\endcsname{#1}}
+\beamer@activecjk
 \@input{\jobname.head}
 \newcount\headcounter
 \def\dohead{\headcounter=0\loop\ifnum\headcounter<\totalheads%
 \def\sectionentry#1#2#3#4#5{\advance\beamer@sectioncount by1\relax%
   \ifnum\section@max<\beamer@sectioncount\section@max=\beamer@sectioncount\fi}
 \def\slideentry#1#2#3#4#5#6{\ifnum\subsection@max<#2\relax\subsection@max=#2\fi}
-\def\appendixslideentry#1#2#3#4#5#6{\ifnum\subsection@max<#2\relax\subsection@max=#2\fi}
-\def\appendixsectionentry#1#2#3#4#5{\gdef\beamer@appendixstart{#3}}
 \def\beamer@framepages#1#2{}
 \def\beamer@subsectionpages#1#2{}
 \def\beamer@sectionpages#1#2{}
 \def\beamer@appendixpages#1{\gdef\beamer@startpageofappendix{#1}}
 \def\beamer@documentpages#1{\gdef\beamer@endpageofdocument{#1}}
 \dohead
-
 \setlength\lineskip{1\p@}
 \setlength\normallineskip{1\p@}
 \renewcommand\baselinestretch{}
   \def\inserttitle{#2}%
   \def\insertshorttitle{\def\\{}%
     \ifnum\thepage=1%
-    \edef\beamer@def{{Navigation\beamer@appendixstart}}%
-    \expandafter\hyperlink\beamer@def{#1}%
+    \hyperlinkpresentationend{#1}%
     \else%
-    \hyperlink{Navigation1}{#1}%
-    \fi}%
+    \hyperlinkpresentationstart{#1}%
+    \fi}
   }
 \title{}
 
   \beamer@sectionstartpage=\c@page%
   \beamer@subsectionstartpage=\c@page%
   \def\insertpart{\expandafter\hyperlink\partlink}%
-  \def\insertpartshort{\expandafter\hyperlink\partlinkshort}}%
+  \def\insertshortpart{\expandafter\hyperlink\partlinkshort}}%
 \def\insertpart{}
-\def\insertpartshort{}
-
-
+\def\insertshortpart{}
+
+\def\insertromanpartnumber{\@Roman\c@part}
+\def\insertpartnumber{\@arabic\c@part}
 
 %
 % Section Definitions
   {%
     \long\def\subsecname{#2}%
     \long\def\lastsubsection{#1}%
-    \ifbeamer@inappendix%
-    \addtocontents{toc}{\protect\appendixsubsectionintoc{\thesection}{\thesubsection}{#2}{\thepage}{\thepart}}%
-    \else%
     \addtocontents{toc}{\protect\subsectionintoc{\thesection}{\thesubsection}{#2}{\thepage}{\thepart}}%
-    \fi%
   }%
   \beamer@tempcount=\c@page\advance\beamer@tempcount by -1%
   \addtocontents{head}{\protect\headcommand{\protect\beamer@subsectionpages{\the\beamer@subsectionstartpage}{\the\beamer@tempcount}}}%
   {%
     \def\sectionentry##1##2##3##4##5{}%
     \def\slideentry##1##2##3##4##5##6{}%
-    \def\appendixslideentry##1##2##3##4##5##6{}%
-    \def\appendixsectionentry##1##2##3##4##5{}%
     \dohead%
   }%
 }
 %
 % Appendix stuff
 %
-\newif\ifbeamer@inappendix
 \def\appendix{%
-  \beamer@inappendixtrue%
-  \refstepcounter{section}%
-  \long\edef\secname{\appendixname}%
-  \addtocontents{toc}{\protect\appendixtoc{\thesubsection}{\appendixname}{\thepage}{\thepart}}
-  \addtocontents{head}{\protect\headcommand{\protect\appendixsectionentry{\thesection}{\secname}{\thepage}{\secname}{\thepart}}}%
-  \addtocontents{head}{\protect\headcommand{\protect\beamer@appendixpages{\the\c@page}}}%
-  \beamer@tempcount=\c@page\advance\beamer@tempcount by -1%
-  \addtocontents{head}{\protect\headcommand{\protect\beamer@sectionpages{\the\beamer@sectionstartpage}{\the\beamer@tempcount}}}%
-  \addtocontents{head}{\protect\headcommand{\protect\beamer@subsectionpages{\the\beamer@subsectionstartpage}{\the\beamer@tempcount}}}%
-  \beamer@sectionstartpage=\c@page%
-  \beamer@subsectionstartpage=\c@page%
-  \xdef\sectionlink{{Navigation\thepage}{\noexpand\secname}}%
-  \def\insertsection{\expandafter\hyperlink\sectionlink}%
-  \def\insertsubsection{}%
-  \def\lastsubsection{}%
-  \Hy@writebookmark{\thesection}{\secname}{Outline\thesection}{1}{toc}%
-  \hyper@anchorstart{Outline\thesection}\hyper@anchorend}%
+  \part{\appendixname}
+  \addtocontents{head}{\protect\headcommand{\protect\beamer@appendixpages{\the\c@page}}}}
 
 
 
 \long\def\donoframe{%
   \serialnumber=1\relax%
   \@serialnumber=1\relax%
-  \setbox\tempbox\vbox\bgroup\leavevmode\afterassignment\@checknoslide\let\@next}
+  \setbox\tempbox\vbox\bgroup\leavevmode\def\pause{}\afterassignment\@checknoslide\let\@next}
 \def\@checknoslide{%
   \ifcat\bgroup\noexpand\@next%
   \let\@do\beamer@reseteecodes%
 \def\beamer@writeslidentry{%
   \expandafter\@ifempty\expandafter{\beamer@framestartpage}{}% nothing to do ...
   {%else
-    \ifbeamer@inappendix%
-      \addtocontents{head}%
-        {\protect\headcommand{% 
-            \protect\appendixslideentry{\thesection}{\thesubsection}{\thesubsectionslide}%
-            {\beamer@framestartpage/\beamer@frameendpage}{\lastsubsection}{\thepart}}}%
-      \addtocontents{head}%
-        {\protect\headcommand{% 
-          \protect\beamer@framepages{\beamer@framestartpage}{\beamer@frameendpage}}}%
-    \else%
-      \addtocontents{head}%
-        {\protect\headcommand{%
-            \protect\slideentry{\thesection}{\thesubsection}{\thesubsectionslide}%
-            {\beamer@framestartpage/\beamer@frameendpage}{\lastsubsection}{\thepart}}}%
-      \addtocontents{head}%
-        {\protect\headcommand{% 
-          \protect\beamer@framepages{\beamer@framestartpage}{\beamer@frameendpage}}}%
-    \fi%
+    \addtocontents{head}%
+      {\protect\headcommand{%
+          \protect\slideentry{\thesection}{\thesubsection}{\thesubsectionslide}%
+          {\beamer@framestartpage/\beamer@frameendpage}{\lastsubsection}{\thepart}}}%
+    \addtocontents{head}%
+      {\protect\headcommand{% 
+        \protect\beamer@framepages{\beamer@framestartpage}{\beamer@frameendpage}}}%
     \clearpage%
   }
 }
 
 \newoverlaycommand{\nameslide}{\@nameslide}{\gobble}
 
+
+
+%
+% Names slides
+%
+
 \def\@nameslide#1{%
-  \addtocontents{snm}{\protect\beamer@slide{#1}{\thepage}}}
-\def\beamer@slide#1#2{\expandafter\def\csname hyperlink#1\endcsname{%
+  \addtocontents{snm}{\protect\beamer@slide{#1}{\thepage}}%
+  \hypertarget{#1}{}}
+\def\beamer@slide#1#2{\expandafter\def\csname beamer@hyperlink#1\endcsname{%
   \hyperlink{Navigation#2}}}
 
-\@input{\jobname.snm}
-
 
 %
 % Alerting
   \let\@evenhead\@oddhead\let\@evenfoot\@oddfoot}
 
 \def\recalculatefoot{%
+  \beamer@activecjk%
   \setbox\tempbox=\hbox{\@foottemplate}%
   \footheight=\ht\tempbox%
   \advance\footheight by \dp\tempbox%
   \advance\sidebarheight by\headdp%
   \advance\sidebarheight by-\footheight}
 \def\recalculatehead{%
+  \beamer@activecjk%
   \setbox\tempbox=\hbox{\@headtemplate}%
   \headheight=\ht\tempbox%
   \headdp=\dp\tempbox%
 
 \def\insertnavigation#1{%
   \vbox{%
-    \ifbeamer@inappendix%
-    \def\sectionentry##1##2##3##4##5{}%
-    \def\slideentry{\fakeslideentry}%
-    \else%
-    \def\appendixsectionentry##1##2##3##4##5{}%
-    \def\appendixslideentry{\fakeslideentry}%
-    \fi%
     \beamer@xpos=0\relax%
     \beamer@ypos=1\relax%
     \hbox to #1{\hskip.3cm\tiny\setbox\sectionbox=\hbox{\kern1sp}%
   \dp\sectionbox=2pt%
   \fi\ignorespaces}
 
-\let\appendixsectionentry=\sectionentry
-
 \def\usesectionheadtemplate#1#2{\gdef\@sectionheadhilight{#1}\gdef\@sectionheadnohilight{#2}}
 \def\usesectionsidetemplate#1#2{\gdef\@sectionsidehilight{#1}\gdef\@sectionsidenohilight{#2}}
 
             \@subsectionsidenohilight%
           \fi}}%
       \fi\fi}%
-    \let\appendixsectionentry=\sectionentry%
-    \let\appendixslideentry=\slideentry%
-    \ifbeamer@inappendix%
-    \def\sectionentry##1##2##3##4##5{}%
-    \def\slideentry##1##2##3##4##5##6{}%
-    \else%
-    \def\appendixsectionentry##1##2##3##4##5{}%
-    \def\appendixslideentry##1##2##3##4##5##6{}%
-    \fi%
     \currentsubsection=1\relax%
     \dohead%
   }}
   \fakeslideentry{#1}{#2}{#3}{#4}{#5}{#6}%
   \fi\ignorespaces}
 
-\let\appendixslideentry=\slideentry
-
 \def\fakeslideentry#1#2#3#4#5#6{%
   \ifnum#2>0\ifnum#3>0%
   \ifbeamer@compress%
     \vbox{%
      \vskip1.5pt%
      \def\slideentry##1##2##3##4##5##6{}%
-     \def\appendixslideentry##1##2##3##4##5##6{}%
-     \def\appendixsectionentry##1##2##3##4##5{%
-       \ifnum##5=\c@part%
-       \def\insertsectionhead{##2}%
-       \setbox\tempbox=\hbox{%
-         \hyperlink{Navigation##3}{\hbox to #1{%
-           \hskip0.3cm\ifnum\thesection=##1%
-           \@sectionheadhilight\else\@sectionheadnohilight\fi\hskip0.3cm}}}%
-       \ht\tempbox=4.5pt\dp\tempbox=2pt%        
-       \box\tempbox\fi}%
      \def\sectionentry##1##2##3##4##5{%
        \ifnum##5=\c@part%
        \def\insertsectionhead{##2}%
            \@sectionheadhilight\else\@sectionheadnohilight\fi\hskip0.3cm}}}%
        \ht\tempbox=4.5pt\dp\tempbox=2pt%        
        \box\tempbox\fi}%
-     \ifbeamer@inappendix%
-     \def\sectionentry##1##2##3##4##5{}%
-     \else%
-     \def\appendixsectionentry##1##2##3##4##5{}%
-     \fi%
      \dohead\vskip1.5pt}\hfil}}
 
 \def\insertsectionnavigationhorizontal#1#2#3{%
   \hbox to #1{%
      \def\slideentry##1##2##3##4##5##6{}%
-     \def\appendixslideentry##1##2##3##4##5##6{}%
-     \ifbeamer@inappendix%
-     \def\sectionentry##1##2##3##4##5{}%
-     \else%
-     \def\appendixsectionentry##1##2##3##4##5{}%
-     \fi%
      #2\hskip.3cm\tiny\setbox\sectionbox=\hbox{}%
      \ht\sectionbox=5pt%
      \dp\sectionbox=2pt%
       \vskip1.5pt%
       \currentsubsection=1%
       \def\sectionentry##1##2##3##4##5{}%
-      \def\appendixsectionentry##1##2##3##4##5{}%
       \def\slideentry##1##2##3##4##5##6{\ifnum##6=\c@part\ifnum##1=\thesection%
         \ifnum##2=\currentsubsection%
         \advance\currentsubsection by1%
           \@subsectionheadhilight\else\@subsectionheadnohilight\fi\hfil\hskip0.3cm}}}%
         \ht\tempbox=4.5pt\dp\tempbox=2pt%
         \box\tempbox\fi\fi\fi}%
-      \def\appendixslideentry##1##2##3##4##5##6{\ifnum##6=\c@part%
-        \ifnum##2=\currentsubsection%
-        \advance\currentsubsection by1%
-        \def\insertsubsectionhead{##5}%
-        \setbox\tempbox=\hbox{\beamer@link(##4){%
-          \hbox to #1{\hskip0.3cm\ifnum\thesubsection=##2%
-          \@subsectionheadhilight\else\@subsectionheadnohilight\fi\hfil\hskip0.3cm}}}%
-        \ht\tempbox=4.5pt\dp\tempbox=2pt%
-        \box\tempbox\fi\fi}%
-      \ifbeamer@inappendix%
-      \def\slideentry##1##2##3##4##5##6{}%
-      \else%
-      \def\appendixslideentry##1##2##3##4##5##6{}%
-      \fi%
       \dohead\vskip1.5pt}\hfil}}
 
 \def\insertsubsectionnavigationhorizontal#1#2#3{%
   \hbox to #1{%
     \currentsubsection=1%
     \def\sectionentry##1##2##3##4##5{}%
-    \def\appendixsectionentry##1##2##3##4##5{}%
     \def\slideentry##1##2##3##4##5##6{\ifnum##6=\c@part\ifnum##1=\thesection%
       \ifnum##2=\currentsubsection%
       \advance\currentsubsection by1%
       \ht\sectionbox=5pt%
       \dp\sectionbox=2pt%
       \fi\fi\fi\ignorespaces}%
-    \def\appendixslideentry##1##2##3##4##5##6{\ifnum##6=\c@part%
-      \ifnum##2=\currentsubsection%
-      \advance\currentsubsection by1%
-      \box\sectionbox\hskip5pt plus1fill%
-      \setbox\sectionbox=
-      \hbox{\def\insertsubsectionhead{##5}%
-        \ifnum\thesubsection=##2%
-        \beamer@link(##4){\@subsectionheadhilight}\else%
-        \beamer@link(##4){\@subsectionheadnohilight}\fi}%
-      \ht\sectionbox=5pt%
-      \dp\sectionbox=2pt%
-      \fi\fi\ignorespaces}%
-    \ifbeamer@inappendix%
-      \def\slideentry##1##2##3##4##5##6{}%
-    \else%
-      \def\appendixslideentry##1##2##3##4##5##6{}%
-    \fi%
     #2\hskip.3cm\tiny\setbox\sectionbox=\hbox{}%
     \hskip-5pt plus-1fill\dohead%
     \box\sectionbox\hfil\hskip.3cm%
   \@subsectionsshadedfalse%
   \setkeys{beamertoc}{#1}%
   \vspace*{-.5em}{\makeatletter%
-    \ifbeamer@inappendix
-    \def\sectionintoc##1##2##3##4{}%
-    \def\subsectionintoc##1##2##3##4##5{}%
-    \else%
-    \def\appendixtoc##1##2##3##4{}%
-    \def\appendixsubsectionintoc##1##2##3##4##5{}%
-    \fi%
     \begin{pauses}[0]%
       \@input{\jobname.toc}%
     \end{pauses}\vfill}%
     \fi
     \par\fi}
 
-\def\appendixtoc#1#2#3#4{%
-  \ifnum#4=\beamer@showpartnumber%
-  \def\inserttocsection{\hyperlink{Navigation#3}{#2}}%
-  \vfill
-  \hbox{\vbox{\sectiontemplate}}%
-  \par%
-  \fi%
-}
-
 \def\usetemplatetocsection{\@ifnextchar[\@@usetemplatetocsection\@usetemplatetocsection}
 \long\def\@@usetemplatetocsection[#1]#2{
   \@usetemplatetocsection{#2}{\begin{colormixin}{#1}#2\end{colormixin}}}
   \fi%  
 }
 
-\long\def\appendixsubsectionintoc#1#2#3#4#5{%
-  \ifnum#5=\beamer@showpartnumber%
-  \if@pausesubsections\pause\fi%
-  \def\inserttocsubsection{\hyperlink{Navigation#4}{#3}}%
-  {\@subsectiontemplate}
-  \fi%
-}
-
 \def\usetemplatetocsubsection{\@ifnextchar[\@@usetemplatetocsubsection\@usetemplatetocsubsection}
 \long\def\@@usetemplatetocsubsection[#1]#2{
   \@usetemplatetocsubsection{#2}{\begin{colormixin}{#1}#2\end{colormixin}}}
   \gdef\thirdblocktemplate{#3}%
   \gdef\otherblocktemplate{#4}}
 
-\pgfdeclareimage{beamericonarticle}{11pt}{14pt}{beamericonarticle}
-\pgfdeclareimage{beamericonarticleshaded}{11pt}{14pt}{beamericonarticle.20}
+\pgfdeclareimage[width=11pt,height=14pt]{beamericonarticle}{beamericonarticle}
+\pgfdeclareimage[width=11pt,height=14pt]{beamericonarticleshaded}{beamericonarticle.20}
 \pgfaliasimage{beamericonarticle!20!averagebackgroundcolor}{beamericonarticleshaded}
 \pgfaliasimage{beamericonarticle!15!averagebackgroundcolor}{beamericonarticleshaded}
 \pgfaliasimage{beamericonarticle!10!averagebackgroundcolor}{beamericonarticleshaded}
                                 % Part page  
 \usepartpagetemplate{
   \begin{centering}
-    \Large\structure{\partname~\@Roman\c@part}
+    \Large\structure{\partname~\insertromanpartnumber}
     \vskip1em\par
     \insertpart\par
   \end{centering}
   \hbox{\insertsectionnavigationsymbol}
   \hbox{\insertdocnavigationsymbol}
   \hbox{\insertbackfindforwardnavigationsymbol}}}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: doc/beamerexample.tex
+%%% End: 

File beamertemplates.sty

 % Bibliography templates
 %
 
-\pgfdeclareimage{beamericonbook}{14pt}{12pt}{beamericonbook}
-\pgfdeclareimage{beamericonbookshaded}{14pt}{12pt}{beamericonbook.20}
+\pgfdeclareimage[width=14pt,height=12pt]{beamericonbook}{beamericonbook}
+\pgfdeclareimage[width=14pt,height=12pt]{beamericonbookshaded}{beamericonbook.20}
 \pgfaliasimage{beamericonbook!20!averagebackgroundcolor}{beamericonbookshaded}
 \pgfaliasimage{beamericonbook!15!averagebackgroundcolor}{beamericonbookshaded}
 \pgfaliasimage{beamericonbook!10!averagebackgroundcolor}{beamericonbookshaded}

File doc/beamerexample.pdf

Binary file removed.

File doc/beamerexample.tex

-\documentclass{beamer}
-
-% Try the class options [notes], [notesonly], [trans], [handout],
-% [red], [compress], [class=article] and see what happens!
-
-% Copyright 2003 by Till Tantau <tantau@cs.tu-berlin.de>.
-%
-% 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.
-
-
-\common
-
-\usepackage[english]{babel}
-
-\article
-
-\usepackage{fullpage}
-
-\presentation
-
-% For a green structure color use:
-%\colorlet{structure}{green!50!black}
-
-\usepackage{beamertemplates}
-\usepackage{beamerthemesplit}
-\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
-\usepackage{amsmath,amssymb}
-\usepackage[latin1]{inputenc}
-\usepackage{colortbl}
-
-
-% Use some nice templates
-
-\beamertemplateshadingbackground{red!10}{structure!10}
-\beamertemplatetransparentcovereddynamic
-\beamertemplateballitem
-\beamertemplatesolidbuttons
-
-%
-% 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{\small #1}}
-  {\text{\small #1}}
-  {\text{#1}}
-  {\text{#1}}}}
-
-\newcommand{\DOF}{\Class{DOF}}
-\newcommand{\NOF}{\Class{NOF}}
-\newcommand{\DOFpoly}{\Class{DOF}_{\mathsf{poly}}}
-\newcommand{\NOFpoly}{\Class{NOF}_{\mathsf{poly}}}
-
-
-\newcommand{\Nat}{\mathbb{N}}
-\newcommand{\Set}[1]{\{#1\}}
-
-\pgfdeclareimage{computerimage}{1.8361cm}{2cm}{computer}
-\pgfdeclareimage{computerworkingimage}{1.8361cm}{2cm}{computerred}
-\pgfdeclareimage{apple}{1.625cm}{2cm}{g4}
-\pgfdeclareimage{appleworking}{1.625cm}{2cm}{g4red}
-\pgfdeclareimage{ram}{3.811cm}{1cm}{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]{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]{#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]{#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]{#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]{#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:
-%
-
-\hypersetup{%
-  pdftitle={Computation with Absolutely No Space Overhead},%
-  pdfauthor={Lane Hemaspaandra, Proshanto Mukherji, and Till Tantau},
-  pdfsubject={Theoretical Computer Science},
-  pdfkeywords={overhead-free, context-free, linear space}}
-
-\title[Computation with Absolutely No~Space~Overhead]{Computation~with Absolutely~No~Space~Overhead}
-\author[Hemaspaandra et al.]{%
-  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}
-
-
-\begin{document}
-
-\presentation
-
-\frame{\titlepage}
-
-\section[Outline]{}
-
-\subsection{Part I: Review of Last Lecture}
-
-\frame{
-  \nameslide{outline}
-  \frametitle{Part I: Review of Last Lecture}
-  \tableofcontents[pausesections,part=1]}
-
-\subsection{Part II: Today's Lecture}
-\frame{
-  \frametitle{Part II: Today's Lecture}
-  \tableofcontents[pausesections,part=2]}
-\note{At most 1 minute for the outline.}
-
-\part{Review of Last Lecture}
-\frame{\partpage}
-
-\section[Results]{Results of Last Lecture}
-
-\subsection[First]{First Result}
-
-\frame{Some results.}
-
-\subsection[Second]{Second Result}
-
-\frame{Some results.}
-
-\part{Today's Lecture}
-\frame{\partpage}
-
-\section[Models]{The Model of Overhead-Free Computation}
-
-\frame[handout:0]{\tableofcontents[current]}
-
-\subsection[Standard Model]{The Standard Model of Linear Space}
-
-\frame
-{
-  \frametitle{The Standard Model of Linear Space}
-
-  \begin{columns}
-    \begin{column}{4.5cm}
-      \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm}
-        \pgfonly<1| trans:1>{
-          \putmachine{\pgfxy(1.75,3)}{Turing machine}
-          \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0}
-          \selectpos{1}}
-        \pgfonly<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}}        
-        \pgfonly<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}}        
-        \pgfonly<4| handout:0| trans:4>{
-          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
-          \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{\$}
-          \selectpos{7}}      
-        \pgfonly<5| handout:0| trans:0>{
-          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
-          \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{\$}
-          \selectpos{2}}      
-        \pgfonly<6| handout:0| trans:0>{
-          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
-          \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{0}{\$}
-          \selectpos{3}}      
-        \pgfonly<7| handout:0| trans:0>{
-          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
-          \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{0}{\$}
-          \selectpos{7}}      
-        \pgfonly<8| handout:0| trans:0>{
-          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
-          \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{\$}{\$}
-          \selectpos{6}}      
-        \pgfonly<9| handout:0| trans:0>{
-          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
-          \tape{\pgfxy(0,5)}{\$}{\$}{\$}{\$}{\$}{\$}{\$}{\$}
-          \selectpos{5}}      
-        \pgfonly<10| handout:0| trans:5>{
-          \putmachine{\pgfxy(1.75,3)}{Turing machine}
-          \tape{\pgfxy(0,5)}{\$}{\$}{\$}{\$}{\$}{\$}{\$}{\$}
-          \selectpos{5}}      
-     \end{pgfpicture}
-    \end{column}
-    \begin{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
-      \end{itemize}
-      \end{block}
-    \end{column}
-  \end{columns}
-} 
-\noteitems{
-\item Stress the large tape alphabet.    
-\item Point out that \$ is a marker symbol.}
-
-\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}$}
-
-    \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}$-hard}}%      
-  \end{pgfpicture}
-}
-\noteitems{
-\item Explain CSL.
-\item Point out the connections to formal language theory.}
-
-\subsection[Our Model]{Our Model of Absolutely No Space Overhead}
-
-\frame
-{
-  \frametitle{Our Model of ``Absolutely No Space Overhead''}
-
-  \begin{columns}
-    \begin{column}{4.5cm}
-      \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm}
-        \pgfonly<1| trans:1>{%
-          \putmachinea{\pgfxy(1.75,3)}{Turing machine}%
-          \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0}%
-          \selectpos{1}}%
-        \pgfonly<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}}%      
-        \pgfonly<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}}%      
-        \pgfonly<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}}%      
-        \pgfonly<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}}%      
-        \pgfonly<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}}%      
-        \pgfonly<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}
-    \end{column}
-    \begin{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{block}{Intuition}
-          \begin{itemize}
-          \item
-            Tape is used like a RAM module.
-          \end{itemize}
-        \end{block}
-      \end{overprint}
-    \end{column}
-  \end{columns}
-}
-\note{Point out that no markers are used.}
-
-
-\frame
-{
-  \frametitle{Definition of Overhead-Free Computations}
-
-  \begin{Definition}
-    A Turing machine is \alert{overhead-free} if
-    \begin{itemize}
-    \item
-      it has only a single tape,
-    \item
-      writes only on input cells,
-    \item
-      writes only symbols drawn from the input alphabet.
-    \end{itemize}
-  \end{Definition}
-}
-
-\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$}]
-      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$,
-      \pause
-    \item[\alert<4| handout:0| trans:0>{$\NOFpoly$}]
-      is the nondeterministic version of $\DOFpoly$. 
-    \end{description}
-  \end{Definition}
-}
-\noteitems{
-\item Joke about German pronunciation.
-\item Stress meaning of D and N.}
-
-
-\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}
-}
-
-
-\section[Power of the Model]{The Power of Overhead-Free Computation}
-
-\frame[handout:0]{\tableofcontents[current]}
-
-\subsection{Palindromes}
-
-\frame
-{
-  \frametitle{Palindromes Can be Accepted in an Overhead-Free Way}
-
-  \begin{columns}
-    \begin{column}{4.5cm}
-      \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm}
-        \pgfonly<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}}
-        \pgfonly<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}}      
-        \pgfonly<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}}
-        \pgfonly<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}}      
-        \pgfonly<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}}      
-        \pgfonly<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}}      
-        \pgfonly<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}}      
-        \pgfonly<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}}      
-        \pgfonly<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}}      
-        \pgfonly<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}}      
-        \pgfonly<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}}      
-        \pgfonly<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}}      
-        \pgfonly<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}}      
-        \pgfonly<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}}      
-        \pgfonly<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}}      
-        \pgfonly<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}
-    \end{column}
-    \begin{column}{6cm}
-      \begin{block}{Algorithm}
-        \vskip1em
-
-        \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{column}
-  \end{columns}
-}
-\note{Use 3 minutes.}
-
-
-\frame
-{
-  \frametitle{Relationships among Overhead-Free Computation Classes}
-
-  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6.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}
-}
-
-\subsection{Linear Languages}
-
-\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$.
-    
-    $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.''
-  \end{Definition}
-
-  \begin{Example}<2->
-    $G_1$ is deterministic.
-    
-    $G_2$ is \alert{not} deterministic.
-  \end{Example}  
-}
-\note{Just explain intuition using the example.}
-
-\frame
-{
-  \frametitle{Deterministic Linear Languages\\ Can Be Accepted in an
-    Overhead-Free Way}
-
-  \begin{Theorem}
-    Every deterministic linear language is in $\DOFpoly$.
-  \end{Theorem}
-}
-
-\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}
-
-  \pause
-  \begin{Example}
-    $\Lang{triple-palindrome} = \Set{uvw \mid \text{$u$, $v$, and $w$ are palindromes}}$.
-  \end{Example}  
-
-  \pause
-  \begin{Theorem}
-    Every metalinear language is in $\NOFpoly$.
-  \end{Theorem}
-}
-
-\frame
-{
-  \frametitle{Relationships among Overhead-Free Computation Classes}
-
-  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6.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{Skip next subsection if more than 18 minutes have passed.}
-
-
-\subsection[Forbidden Subword]{Context-Free Languages with a Forbidden Subword}
-
-\frame
-{
-  \frametitle{Definition of Almost-Overhead-Free Computations}
-
-  \begin{Definition}
-    A Turing machine is \alert{almost-overhead-free} if
-    \begin{itemize}
-    \item
-      it has only a single tape,
-      \pause
-    \item
-      writes only on input cells,
-      \pause
-    \item
-      writes only symbols drawn from the input alphabet\\
-      \alert{plus one special symbol}.
-    \end{itemize}
-  \end{Definition}
-}
-
-
-\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>
-    \hfill\hyperlinkframestartnext{\beamerskipbutton{Skip proof}}
-  \onslide<2>
-    \begin{proof}
-      Every context-free language can be accepted by a nondeterministic
-      almost-overhead-free machine in polynomial time.
-    \end{proof}
-  \end{overprint}
-}
-
-\frame
-{
-  \frametitle{Relationships among Overhead-Free Computation Classes}
-  
-  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6.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}
-}
-
-\subsection[Complete Languages]{Languages Complete for Polynomial Space}
-
-\frame
-{
-  \frametitle{Some PSPACE-complete Languages\\ Can Be
-    Accepted in an Overhead-Free Way} 
-
-  \begin{Theorem}
-    $\DOF$ contains languages that are complete for
-    $\Class{PSPACE}$. 
-  \end{Theorem}
-  \vskip1em
-
-  \hyperlink{proofdetails}{\beamergotobutton{Proof details}}
-  \nameslide{backfromproofdetails}
-}
-
-
-\frame
-{
-  \frametitle{Relationships among Overhead-Free Computation Classes}
-
-  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6.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$}
-
-    \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}
-}
-
-
-
-\section[Limitations of the Model]{Limitations of Overhead-Free Computation}
-
-\frame[handout:0]{\tableofcontents[current]}
-
-\subsection[Strict Inclusion]{Linear Space is Strictly More Powerful}
-
-\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.  
-}
-
-
-\frame
-{
-  \frametitle{Relationships among Overhead-Free Computation Classes}
-
-  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6.5cm}
-    \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}
-}
-
-
-
-\frame
-{
-  \frametitle{Candidates for Languages that\\
-    Cannot be Accepted in an Overhead-Free Way}
-
-  \begin{block}{Conjecture}
-    $\Lang{double-palindromes} \notin \Class{DOF}$.
-  \end{block}
-
-  \begin{block}{Conjecture}
-    $\Set{ww \mid w\in \Set{0,1}^*} \notin \Class{NOF}$. 
-  \end{block}
-
-  \vskip1em
-  Proving the first conjecture would show $\Class{DOF} \subsetneq
-  \Class{NOF}$. 
-}
-
-
-\section[Summary]{}
-
-\subsection[Summary]{}
-\frame
-{
-  \frametitle{Summary}
-
-  \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}
-}
-\noteitems{
-\item Point out result concerning all context-free languages.
-\item Relationship to restart automata.}
-
-
-\subsection[Further Reading]{}
-
-\frame{
-  \frametitle{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}
-}
-
-
-%
-% The following appendix material is not shown in the normal course of
-% the presentation 
-%
-
-\appendix
-
-\frame{\tableofcontents}
-
-\subsection{Overhead Freeness and Completeness}
-
-\frame{
-  \frametitle{Overhead-Free Languages can be PSPACE-Complete}
-
-  \hypertarget{proofdetails}{}
-  \begin{Theorem}
-    $\DOF$ contains languages that are complete for
-    $\Class{PSPACE}$. 
-  \end{Theorem}
-
-  \begin{proof}
-    \begin{itemize}
-    \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. 
-    \end{itemize}
-  \end{proof}
-
-  \hfill\hyperlinkbackfromproofdetails{\beamerreturnbutton{Return}}
-}
-
-\subsection{Improvements for Context-Free Languages}
-
-\frame{
-  \frametitle{Improvements}
-
-  \begin{theorem}
-    \begin{enumerate}
-    \item
-      $\Class{DCFL} \subseteq \DOFpoly$.
-    \item
-      $\Class{CFL} \subseteq \NOFpoly$.
-    \end{enumerate}
-  \end{theorem}
-}
-
-\subsection{Abbreviations}
-
-\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}
-}
-
-
-\article
-
-\title{{\Large\textbf{Computation with\\ Absolutely No Space Overhead}}}
-\date{September 23, 2003}
-
-\author{
-  Lane A. Hemaspaandra\footnote{Supported in part by grants
-    NSF-CCR-9322513 and
-    NSF-INT-9815095\,/\penalty0\,DAAD-315-PPP-g{\"u}-ab.}
-{}\\
-Department of Computer Science\\
-  University of Rochester\\
-  Rochester, NY 14627, USA\\
-  \texttt{lane@cs.rochester.edu}
-  \and Proshanto Mukherji \\
-Department of Computer Science\\
-  University of Rochester\\
-  Rochester, NY 14627, USA\\
-  \texttt{mukherji@cs.rochester.edu}
-  \and
-  Till Tantau\thanks{Supported in part by an Erwin-Stephan-Prize grant
-    of the Technical University of Berlin and a postdoc research
-    fellowship grant of the German Academic Exchange Service
-    (DAAD). Work done in part while working at the Technical
-    University of Berlin and while visiting the University of
-    Rochester.} 
-\\
-  International Computer Science Institute\\
-  1947 Center Street\\
-  Berkeley, CA, USA\\
-  \texttt{tantau@icsi.berkeley.edu}
-    }
-
-\maketitle
-
-\begin{abstract}
-  We study Turing machines that are allowed absolutely no space
-  overhead. The only work space the machines have, beyond the fixed
-  amount of memory implicit in their finite-state control, is that
-  which they can create by cannibalizing the input bits' own space. 
-  This model more closely reflects the fixed-sized memory of real
-  computers than does the standard complexity-theoretic model of linear
-  space. Though some context-sensitive languages cannot
-  be accepted by such machines, we show that all deterministic 
-  context-free languages can be accepted deterministically in
-  polynomial time with absolutely no space overhead. Similarly, all
-  context-free languages can be accepted nondeterministically without
-  space overhead.
-
-  \vskip1em
-  \noindent\emph{Keywords.} \sloppy Space overhead,  space reuse,
-  overhead-free computation, con\-text-sensitive
-  languages, context-free languages, linear space, in-place
-  algorithms. 
-\end{abstract}
-
-
-\section{Introduction}
-
-Complexity theory studies which problems can be solved
-\emph{realistically} using a computer. Since it depends on
-context what resources are deemed ``realistic,'' different resource
-bounds on various models have been studied. For example, deterministic
-linear space is a possible formalization of the limited memory of
-computers. Unfortunately, the standard complexity-theoretic
-formalizations may be too ``rough'' in realistic contexts, as most
-have hidden constants tucked away inside their definitions.
-Polynomial-time algorithms with a time bound of $n^{100}$ and
-linear-space algorithms that need one megabyte of extra memory per
-input bit will typically be unhelpful from a practical point of view.
-
-\begin{figure}
-  \begin{centering}
-    \leavevmode\includeslide{outline}{beamerexample.presentation}\par
-  \end{centering}
-  \caption{The outline.}
-\end{figure}
-
-\begin{figure}
-  \begin{centering}
-    \leavevmode\includeslide[height 5cm]{backfromproofdetails}{beamerexample.presentation}\par
-  \end{centering}
-  \caption{A jump back.}
-\end{figure}
-
-\dots
-
-\end{document}
-
-

File doc/beamerexample1.pdf

Binary file added.

File doc/beamerexample1.tex

+\documentclass{beamer}
+
+% Try the class options [notes], [notesonly], [trans], [handout],
+% [red], [compress], [draft] and see what happens!
+
+% Copyright 2003 by Till Tantau <tantau@cs.tu-berlin.de>.
+%
+% 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}
+
+\usepackage{beamertemplates}
+\usepackage{beamerthemebars}
+\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
+\usepackage{amsmath,amssymb}
+\usepackage[latin1]{inputenc}
+\usepackage{colortbl}
+\usepackage[english]{babel}
+
+
+% Use some nice templates
+
+\beamertemplateshadingbackground{red!10}{structure!10}
+\beamertemplatetransparentcovereddynamic
+\beamertemplateballitem
+\beamertemplatesolidbuttons
+
+%
+% 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{\small #1}}
+  {\text{\small #1}}
+  {\text{#1}}
+  {\text{#1}}}}
+
+\newcommand{\DOF}{\Class{DOF}}
+\newcommand{\NOF}{\Class{NOF}}
+\newcommand{\DOFpoly}{\Class{DOF}_{\mathsf{poly}}}
+\newcommand{\NOFpoly}{\Class{NOF}_{\mathsf{poly}}}
+
+
+\newcommand{\Nat}{\mathbb{N}}
+\newcommand{\Set}[1]{\{#1\}}
+
+\pgfdeclareimage[width=1.8361cm,height=2cm]{computerimage}{computer}
+\pgfdeclareimage[width=1.8361cm,height=2cm]{computerworkingimage}{computerred}
+\pgfdeclareimage[width=1.625cm,height=2cm]{apple}{g4}
+\pgfdeclareimage[width=1.625cm,height=2cm]{appleworking}{g4red}
+\pgfdeclareimage[width=3.811cm,height=1cm]{ram}{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]{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]{#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]{#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]{#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]{#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:
+%
+
+\hypersetup{%
+  pdftitle={Computation with Absolutely No Space Overhead},%
+  pdfauthor={Lane Hemaspaandra, Proshanto Mukherji, and Till Tantau},
+  pdfsubject={Theoretical Computer Science},
+  pdfkeywords={overhead-free, context-free, linear space}}
+
+\title[Computation with Absolutely No~Space~Overhead]{Computation~with Absolutely~No~Space~Overhead}
+\author[Hemaspaandra et al.]{%
+  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}
+
+
+\begin{document}
+
+\frame{\titlepage}
+
+
+\section[Outline]{}
+
+\frame{\tableofcontents[pausesections]}
+
+
+\section[Models]{The Model of Overhead-Free Computation}
+
+\frame[handout:0]{\tableofcontents[current]}
+
+
+\subsection[Standard Model]{The Standard Model of Linear Space}
+
+\frame
+{
+  \frametitle{The Standard Model of Linear Space}
+
+  \begin{columns}
+    \begin{column}{4.5cm}
+      \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm}
+        \pgfonly<1| trans:1>{
+          \putmachine{\pgfxy(1.75,3)}{Turing machine}
+          \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0}
+          \selectpos{1}}
+        \pgfonly<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}}        
+        \pgfonly<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}}        
+        \pgfonly<4| handout:0| trans:4>{
+          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
+          \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{\$}
+          \selectpos{7}}      
+        \pgfonly<5| handout:0| trans:0>{
+          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
+          \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{\$}
+          \selectpos{2}}      
+        \pgfonly<6| handout:0| trans:0>{
+          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
+          \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{0}{\$}
+          \selectpos{3}}      
+        \pgfonly<7| handout:0| trans:0>{
+          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
+          \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{0}{\$}
+          \selectpos{7}}      
+        \pgfonly<8| handout:0| trans:0>{
+          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
+          \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{\$}{\$}
+          \selectpos{6}}      
+        \pgfonly<9| handout:0| trans:0>{
+          \putmachineworking{\pgfxy(1.75,3)}{Turing machine}
+          \tape{\pgfxy(0,5)}{\$}{\$}{\$}{\$}{\$}{\$}{\$}{\$}
+          \selectpos{5}}      
+        \pgfonly<10| handout:0| trans:5>{
+          \putmachine{\pgfxy(1.75,3)}{Turing machine}
+          \tape{\pgfxy(0,5)}{\$}{\$}{\$}{\$}{\$}{\$}{\$}{\$}
+          \selectpos{5}}      
+     \end{pgfpicture}
+    \end{column}
+    \begin{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
+      \end{itemize}
+      \end{block}
+    \end{column}
+  \end{columns}
+} 
+\noteitems{
+\item Stress the large tape alphabet.    
+\item Point out that \$ is a marker symbol.}
+
+\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}$}
+
+    \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}$-hard}}%      
+  \end{pgfpicture}
+}
+\noteitems{
+\item Explain CSL.
+\item Point out the connections to formal language theory.}
+
+
+\subsection[Our Model]{Our Model of Absolutely No Space Overhead}
+
+\frame
+{
+  \frametitle{Our Model of ``Absolutely No Space Overhead''}
+
+  \begin{columns}
+    \begin{column}{4.5cm}
+      \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm}
+        \pgfonly<1| trans:1>{%
+          \putmachinea{\pgfxy(1.75,3)}{Turing machine}%
+          \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0}%
+          \selectpos{1}}%
+        \pgfonly<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}}%      
+        \pgfonly<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}}%      
+        \pgfonly<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}}%      
+        \pgfonly<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}}%      
+        \pgfonly<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}}%      
+        \pgfonly<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}
+    \end{column}
+    \begin{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{block}{Intuition}
+          \begin{itemize}
+          \item
+            Tape is used like a RAM module.
+          \end{itemize}
+        \end{block}
+      \end{overprint}
+    \end{column}
+  \end{columns}
+}
+\note{Point out that no markers are used.}
+
+\frame
+{
+  \frametitle{Definition of Overhead-Free Computations}
+
+  \begin{Definition}
+    A Turing machine is \alert{overhead-free} if
+    \begin{itemize}
+    \item
+      it has only a single tape,
+    \item
+      writes only on input cells,
+    \item
+      writes only symbols drawn from the input alphabet.
+    \end{itemize}
+  \end{Definition}
+}
+
+\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$}]
+      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$,
+      \pause
+    \item[\alert<4| handout:0| trans:0>{$\NOFpoly$}]
+      is the nondeterministic version of $\DOFpoly$. 
+    \end{description}
+  \end{Definition}
+}
+\noteitems{
+\item Joke about German pronunciation.
+\item Stress meaning of D and N.}
+
+\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}
+}
+
+
+\section[Power of the Model]{The Power of Overhead-Free Computation}
+
+\frame[handout:0]{\tableofcontents[current]}
+
+
+\subsection{Palindromes}
+
+\frame
+{
+  \frametitle{Palindromes Can be Accepted in an Overhead-Free Way}
+
+  \begin{columns}
+    \begin{column}{4.5cm}
+      \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm}
+        \pgfonly<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}}
+        \pgfonly<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}}      
+        \pgfonly<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}}
+        \pgfonly<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}}      
+        \pgfonly<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}}      
+        \pgfonly<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}}      
+        \pgfonly<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}}      
+        \pgfonly<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}}      
+        \pgfonly<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}}      
+        \pgfonly<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}}      
+        \pgfonly<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}}      
+        \pgfonly<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}}      
+        \pgfonly<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}}      
+        \pgfonly<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}}      
+        \pgfonly<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}}      
+        \pgfonly<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}
+    \end{column}
+    \begin{column}{6cm}
+      \begin{block}{Algorithm}
+        \vskip1em
+
+        \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{column}
+  \end{columns}
+}
+\note{Use 3 minutes.}
+
+\frame
+{
+  \frametitle{Relationships among Overhead-Free Computation Classes}
+
+  \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6.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}
+}
+
+
+\subsection{Linear Languages}
+
+\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$.
+    
+    $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.''
+  \end{Definition}
+
+  \begin{Example}<2->
+    $G_1$ is deterministic.
+    
+    $G_2$ is \alert{not} deterministic.
+  \end{Example}  
+}
+\note{Just explain intuition using the example.}
+
+\frame
+{
+  \frametitle{Deterministic Linear Languages\\ Can Be Accepted in an
+    Overhead-Free Way}