doc 4

git-svn-id: svn://tug.org/texlive/trunk@80 c570f23f-e606-0410-a88d-b1316a301751

27 files changed, 2322 insertions, 0 deletions

diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-computer-mask.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-computer-mask.jpg
new file mode 100644
index 00000000000..b459c8fa099
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-computer-mask.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-computer.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-computer.jpg
new file mode 100644
index 00000000000..f48e2ae106f
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-computer.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-computerred.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-computerred.jpg
new file mode 100644
index 00000000000..4e691bd2c58
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-computerred.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4-mask.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4-mask.jpg
new file mode 100644
index 00000000000..fe82742d707
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4-mask.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4.jpg
new file mode 100644
index 00000000000..cea4d4c2177
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4red.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4red.jpg
new file mode 100644
index 00000000000..77be392fa11
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4red.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-ram-mask.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-ram-mask.jpg
new file mode 100644
index 00000000000..56556cfa7d9
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-ram-mask.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-ram.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-ram.jpg
new file mode 100644
index 00000000000..a8768667840
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-ram.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-tu-logo-mask.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-tu-logo-mask.jpg
new file mode 100644
index 00000000000..693877d65b7
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-tu-logo-mask.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-tu-logo.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-tu-logo.jpg
new file mode 100644
index 00000000000..84d4fd4f228
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-tu-logo.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-ur-logo-mask.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-ur-logo-mask.jpg
new file mode 100644
index 00000000000..a1ce12cdff0
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-ur-logo-mask.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-ur-logo.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-ur-logo.jpg
new file mode 100644
index 00000000000..29dc62f5a9f
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamer-ur-logo.jpg
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.pdf b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.pdf
new file mode 100644
index 00000000000..e766318d174
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.pdf
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.tex
new file mode 100644
index 00000000000..eaa7e9b642c
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.tex
@@ -0,0 +1,941 @@
+% $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鋞 f黵 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}
+
+
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.pdf b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.pdf
new file mode 100644
index 00000000000..3d5099be798
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.pdf
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.tex
new file mode 100644
index 00000000000..a94cc306cac
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.tex
@@ -0,0 +1,11 @@
+% $Header: /cvsroot/latex-beamer/latex-beamer/examples/beamerexample2.article.tex,v 1.4 2004/10/07 20:53:07 tantau Exp $
+
+\documentclass[11pt]{article}
+\usepackage{beamerarticle}
+
+\input{beamerexample2.tex}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "beamerexample2.article"
+%%% End: 
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.beamer.pdf b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.beamer.pdf
new file mode 100644
index 00000000000..2121e2eceae
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.beamer.pdf
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.beamer.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.beamer.tex
new file mode 100644
index 00000000000..96a868c6da7
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.beamer.tex
@@ -0,0 +1,10 @@
+% $Header: /cvsroot/latex-beamer/latex-beamer/examples/beamerexample2.beamer.tex,v 1.3 2004/10/07 20:53:07 tantau Exp $
+
+\documentclass[ignorenonframetext]{beamer}
+
+\input{beamerexample2.tex}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "beamerexample2.beamer"
+%%% End: 
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.tex
new file mode 100644
index 00000000000..ffcb103d965
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.tex
@@ -0,0 +1,95 @@
+% $Header: /cvsroot/latex-beamer/latex-beamer/examples/beamerexample2.tex,v 1.8 2004/10/11 16:10:11 tantau Exp $
+
+% This file is included by beamerexample2.article.tex and
+% beamerexample2.beamer.tex 
+
+% 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.
+
+%
+% The purpose of this example is to demonstrate the usage of the
+% nameslide command
+%
+
+\mode<article>
+{
+  \usepackage{fullpage}
+  \usepackage{pgf}
+  \usepackage{hyperref}
+  \setjobnamebeamerversion{beamerexample2.beamer}
+}
+
+\mode<presentation>
+{
+  \usetheme{Dresden}
+
+  \setbeamercovered{transparent}
+}
+
+\usepackage[latin1]{inputenc}
+\usepackage[english]{babel}
+
+
+\title{Second Beamer Example}
+\author{Till~Tantau}
+\subject{Presentation Programs}
+
+\institute[TU Berlin]{
+  Fakult鋞 f黵 Elektrotechnik und Informatik\\
+  Technical University of Berlin}
+
+
+\begin{document}
+
+\frame{\maketitle}
+
+\section{The first section}
+
+This is the first section of the article version. In the
+presentation, there is a frame containing an overlay. The exact two
+slides of this overlay are shown in Figures~\ref{figure-example1}
+and~\ref{figure-example2}.
+
+\begin{figure}[ht]
+  \begin{center}
+    \includeslide{exampleframe<1>}
+  \end{center}
+  \caption{The first slide. Note the partly covered second item.}
+  \label{figure-example1}
+\end{figure}
+
+\begin{figure}[ht]
+  \begin{center}
+    \includeslide{exampleframe<2>}
+  \end{center}
+  \caption{The second slide. Now the second item is also shown.}
+  \label{figure-example2}
+\end{figure}
+
+We can also include the frame in the article version ``just like
+this'': 
+
+\frame[label=exampleframe]{
+  \frametitle{This is a frame with two overlays.}
+
+  \begin{itemize}
+  \item The first item$\dots$
+    \pause
+  \item $\dots$ and the second one.
+  \end{itemize}
+}
+
+We could have suppressed the frame in the article version by adding
+the overlay specification \verb!<presentation>!.
+
+\end{document}
+
+
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "beamerexample2.article"
+%%% End: 
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample3.pdf b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample3.pdf
new file mode 100644
index 00000000000..abbea370d9c
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample3.pdf
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample3.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample3.tex
new file mode 100644
index 00000000000..3e79726310d
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample3.tex
@@ -0,0 +1,130 @@
+% $Header: /cvsroot/latex-beamer/latex-beamer/examples/beamerexample3.tex,v 1.8 2004/10/07 20:53:07 tantau Exp $
+
+\documentclass{beamer}
+
+% 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.
+
+%
+% The purpose of this example is to show how \part can be used to
+% organize a lecture.
+%
+
+\usetheme{Warsaw}
+\usepackage[english]{babel}
+\usepackage[latin1]{inputenc}
+
+\setbeamercovered{transparent}
+
+
+%
+% The following info should normally be given in you main file:
+%
+
+
+\title{Beamer Example on Parts}
+\author{Till~Tantau}
+\institute{
+  Fakult鋞 f黵 Elektrotechnik und Informatik\\
+  Technical University of Berlin}
+
+
+\begin{document}
+
+
+\frame{\titlepage}
+
+
+\section*{Outlines}
+
+\subsection{Part I: Review of Previous Lecture}
+
+\frame{
+  \nameslide{outline}
+  \frametitle{Outline of Part I}
+  \tableofcontents[pausesections,part=1]
+}
+
+
+\subsection{Part II: Today's Lecture}
+
+\frame{
+  \frametitle{Outline of Part II}
+  \tableofcontents[pausesections,part=2]
+  \note{At most 1 minute for the outline.}
+}
+
+
+
+\part{Review of Previous Lecture}
+
+\frame{\partpage}
+
+
+\section[Previous Lecture]{Summary of the Previous Lecture}
+
+
+\subsection{Topics}
+
+\frame{
+  \frametitle{This frame shows the topics treated in the last
+    lecture.}
+
+  \begin{itemize}
+  \item This
+    \pause
+  \item and that.    
+  \end{itemize}
+}
+
+
+\subsection{Learning Objectives}
+
+\frame{
+  \frametitle{This frame shows the last lecture's learning objectives.}
+
+  \begin{itemize}
+  \item An objective.
+    \pause
+  \item And another one.
+  \end{itemize}
+}
+
+
+
+\part{Today's Lecture}
+
+\frame{\partpage}
+
+
+\section[Models]{The Model of Overhead-Free Computation}
+
+\frame<beamer>{\tableofcontents[current]}
+
+
+\subsection[Standard Model]{The Standard Model of Linear Space}
+
+\frame
+{
+  \frametitle{A frame.}
+}
+
+
+\section[Limitations]{Limitations of Overhead-Free Computation}
+
+\frame<beamer>{\tableofcontents[current]}
+
+
+\subsection[Linear Space]{Linear Space versus Overhead-Free Computation}
+
+\frame
+{
+  \frametitle{A frame.}
+}
+
+\end{document}
+
+
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample4.pdf b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample4.pdf
new file mode 100644
index 00000000000..75b331a7c4e
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample4.pdf
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample4.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample4.tex
new file mode 100644
index 00000000000..7864d58473b
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample4.tex
@@ -0,0 +1,45 @@
+% $Header: /cvsroot/latex-beamer/latex-beamer/examples/beamerexample4.tex,v 1.4 2004/10/07 20:53:07 tantau Exp $
+
+\documentclass[cjk]{beamer}
+
+% 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.
+%
+% Many thanks to Huang Yushuo for helping me with this file
+% (I don't speak Chinese...)
+
+\usepackage{CJK}
+\usetheme{Warsaw}
+
+\begin{document}
+  \begin{CJK}{GB}{kai}
+
+    \title[用 Beamer 制作的幻灯片]{
+      Example Presentation Created\\
+      with the Beamer Package\\
+      (用 Beamer 制作的幻灯片)}
+    \author{作者 Till Tantau}
+    \date{\today}
+
+    \frame{\titlepage}
+    
+    \section*{Outline}
+    \frame{\tableofcontents}
+    
+    \section{Introduction (简介)}
+    \subsection{Overview of the Beamer Class (Beamer 类的概要)}
+    \frame{
+      \frametitle{Features of the Beamer Class (Beamer 类的特点)}
+      
+      \begin{itemize}
+      \item<1-> Normal LaTeX class (标准的 LaTeX 类).        
+      \item<2-> Easy overlays (重构简单).
+      \item<3-> No external programs needed (无需额外的程序).
+      \end{itemize}
+    }
+  \end{CJK}
+\end{document}
+
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample5.pdf b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample5.pdf
new file mode 100644
index 00000000000..06d7196ad2e
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample5.pdf
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample5.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample5.tex
new file mode 100644
index 00000000000..23ef834d70e
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample5.tex
@@ -0,0 +1,1021 @@
+% $Header: /cvsroot/latex-beamer/latex-beamer/examples/beamerexample5.tex,v 1.22 2004/10/08 14:02:33 tantau Exp $
+
+\documentclass[11pt]{beamer}
+
+\usetheme{Darmstadt}
+
+\usepackage{times}
+\usefonttheme{structurebold}
+
+\usepackage[english]{babel}
+\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps}
+\usepackage{amsmath,amssymb}
+\usepackage[latin1]{inputenc}
+
+\setbeamercovered{dynamic}
+
+\newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
+
+\newcommand{\Class}[1]{\operatorname{\mathchoice
+  {\text{\sf \small #1}}
+  {\text{\sf \small #1}}
+  {\text{\sf #1}}
+  {\text{\sf #1}}}}
+
+\newcommand{\NumSAT}      {\text{\small\#SAT}}
+\newcommand{\NumA}        {\#_{\!A}}
+
+\newcommand{\barA}        {\,\bar{\!A}}
+
+\newcommand{\Nat}{\mathbb{N}}
+\newcommand{\Set}[1]{\{#1\}}
+
+\pgfdeclaremask{tu}{beamer-tu-logo-mask}
+\pgfdeclaremask{computer}{beamer-computer-mask}
+\pgfdeclareimage[interpolate=true,mask=computer,height=2cm]{computerimage}{beamer-computer}
+\pgfdeclareimage[interpolate=true,mask=computer,height=2cm]{computerworkingimage}{beamer-computerred}
+\pgfdeclareimage[mask=tu,height=.5cm]{logo}{beamer-tu-logo}
+
+\logo{\pgfuseimage{logo}}
+
+\title{Weak Cardinality Theorems for First-Order Logic}
+\author{Till Tantau}
+\institute[Technische Universit\"at Berlin]{%
+  Fakult鋞 f黵 Elektrotechnik und Informatik\\
+  Technische Universit\"at Berlin}
+\date{Fundamentals of Computation Theory 2003}
+
+\colorlet{redshaded}{red!25!bg}
+\colorlet{shaded}{black!25!bg}
+\colorlet{shadedshaded}{black!10!bg}
+\colorlet{blackshaded}{black!40!bg}
+
+\colorlet{darkred}{red!80!black}
+\colorlet{darkblue}{blue!80!black}
+\colorlet{darkgreen}{green!80!black}
+
+\def\radius{0.96cm}
+\def\innerradius{0.85cm}
+
+\def\softness{0.4}
+\definecolor{softred}{rgb}{1,\softness,\softness}
+\definecolor{softgreen}{rgb}{\softness,1,\softness}
+\definecolor{softblue}{rgb}{\softness,\softness,1}
+
+\definecolor{softrg}{rgb}{1,1,\softness}
+\definecolor{softrb}{rgb}{1,\softness,1}
+\definecolor{softgb}{rgb}{\softness,1,1}
+
+\newcommand{\Bandshaded}[2]{
+  \color{shadedshaded}
+  \pgfmoveto{\pgfxy(-0.5,0)}
+  \pgflineto{\pgfxy(-0.6,0.1)}
+  \pgflineto{\pgfxy(-0.4,0.2)}
+  \pgflineto{\pgfxy(-0.6,0.3)}
+  \pgflineto{\pgfxy(-0.4,0.4)}
+  \pgflineto{\pgfxy(-0.5,0.5)}
+  \pgflineto{\pgfxy(4,0.5)}
+  \pgflineto{\pgfxy(4.1,0.4)}
+  \pgflineto{\pgfxy(3.9,0.3)}
+  \pgflineto{\pgfxy(4.1,0.2)}
+  \pgflineto{\pgfxy(3.9,0.1)}
+  \pgflineto{\pgfxy(4,0)}
+  \pgfclosepath
+  \pgffill
+
+  \color{black}  
+  \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
+  \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
+}
+
+\newcommand{\Band}[2]{
+  \color{shaded}
+  \pgfmoveto{\pgfxy(-0.5,0)}
+  \pgflineto{\pgfxy(-0.6,0.1)}
+  \pgflineto{\pgfxy(-0.4,0.2)}
+  \pgflineto{\pgfxy(-0.6,0.3)}
+  \pgflineto{\pgfxy(-0.4,0.4)}
+  \pgflineto{\pgfxy(-0.5,0.5)}
+  \pgflineto{\pgfxy(4,0.5)}
+  \pgflineto{\pgfxy(4.1,0.4)}
+  \pgflineto{\pgfxy(3.9,0.3)}
+  \pgflineto{\pgfxy(4.1,0.2)}
+  \pgflineto{\pgfxy(3.9,0.1)}
+  \pgflineto{\pgfxy(4,0)}
+  \pgfclosepath
+  \pgffill
+
+  \color{black}  
+  \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
+  \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
+}
+
+\newcommand{\BaenderNormal}
+{%
+  \pgfsetlinewidth{0.4pt}
+  \color{black}
+  \pgfputat{\pgfxy(0,5)}{\Band{input tapes}{}}
+  \pgfputat{\pgfxy(0.35,4.6)}{\pgfbox[center,base]{$\vdots$}}
+  \pgfputat{\pgfxy(0,4)}{\Band{}{}}
+
+  \pgfxyline(0,5)(0,5.5)
+  \pgfxyline(1.2,5)(1.2,5.5)
+  \pgfputat{\pgfxy(0.25,5.25)}{\pgfbox[left,center]{$w_1$}}
+
+  \pgfxyline(0,4)(0,4.5)
+  \pgfxyline(1.8,4)(1.8,4.5)        
+  \pgfputat{\pgfxy(0.25,4.25)}{\pgfbox[left,center]{$w_n$}}
+  \ignorespaces}
+
+\newcommand{\BaenderZweiNormal}
+{%
+  \pgfsetlinewidth{0.4pt}
+  \color{black}
+  \pgfputat{\pgfxy(0,5)}{\Band{Zwei Eingabeb鋘der}{}}
+  \pgfputat{\pgfxy(0,4.25)}{\Band{}{}}
+
+  \pgfxyline(0,5)(0,5.5)
+  \pgfxyline(1.2,5)(1.2,5.5)
+  \pgfputat{\pgfxy(0.25,5.25)}{\pgfbox[left,center]{$u$}}
+
+  \pgfxyline(0,4.25)(0,4.75)
+  \pgfxyline(1.8,4.25)(1.8,4.75)        
+  \pgfputat{\pgfxy(0.25,4.5)}{\pgfbox[left,center]{$v$}}
+  \ignorespaces}
+
+\newcommand{\BaenderHell}
+{%
+  \pgfsetlinewidth{0.4pt}
+  \color{black}
+  \pgfputat{\pgfxy(0,5)}{\Bandshaded{input tapes}{}}
+  \color{shaded}
+  \pgfputat{\pgfxy(0.35,4.6)}{\pgfbox[center,base]{$\vdots$}}
+  \pgfputat{\pgfxy(0,4)}{\Bandshaded{}{}}
+
+  \color{blackshaded}
+  \pgfxyline(0,5)(0,5.5)
+  \pgfxyline(1.2,5)(1.2,5.5)
+  \pgfputat{\pgfxy(0.25,5.25)}{\pgfbox[left,center]{$w_1$}}
+
+  \pgfxyline(0,4)(0,4.5)
+  \pgfxyline(1.8,4)(1.8,4.5)        
+  \pgfputat{\pgfxy(0.25,4.25)}{\pgfbox[left,center]{$w_n$}}
+  \ignorespaces}
+
+\newcommand{\BaenderZweiHell}
+{%
+  \pgfsetlinewidth{0.4pt}
+  \color{black}
+  \pgfputat{\pgfxy(0,5)}{\Bandshaded{Zwei Eingabeb鋘der}{}}%
+  \color{blackshaded}
+  \pgfputat{\pgfxy(0,4.25)}{\Bandshaded{}{}}
+  \pgfputat{\pgfxy(0.25,4.5)}{\pgfbox[left,center]{$v$}}
+  \pgfputat{\pgfxy(0.25,5.25)}{\pgfbox[left,center]{$u$}}%
+
+  \pgfxyline(0,5)(0,5.5)
+  \pgfxyline(1.2,5)(1.2,5.5)
+
+  \pgfxyline(0,4.25)(0,4.75)
+  \pgfxyline(1.8,4.25)(1.8,4.75)        
+  \ignorespaces}
+
+\newcommand{\Slot}[1]{%
+  \begin{pgftranslate}{\pgfpoint{#1}{0pt}}%
+    \pgfsetlinewidth{0.6pt}%
+    \color{structure}%
+    \pgfmoveto{\pgfxy(-0.1,5.5)}%
+    \pgfbezier{\pgfxy(-0.1,5.55)}{\pgfxy(-0.05,5.6)}{\pgfxy(0,5.6)}%
+    \pgfbezier{\pgfxy(0.05,5.6)}{\pgfxy(0.1,5.55)}{\pgfxy(0.1,5.5)}%
+    \pgflineto{\pgfxy(0.1,4.0)}%
+    \pgfbezier{\pgfxy(0.1,3.95)}{\pgfxy(0.05,3.9)}{\pgfxy(0,3.9)}%
+    \pgfbezier{\pgfxy(-0.05,3.9)}{\pgfxy(-0.1,3.95)}{\pgfxy(-0.1,4.0)}%
+    \pgfclosepath%
+    \pgfstroke%
+  \end{pgftranslate}\ignorespaces}
+
+\newcommand{\SlotZwei}[1]{%
+  \begin{pgftranslate}{\pgfpoint{#1}{0pt}}%
+    \pgfsetlinewidth{0.6pt}%
+    \color{structure}%
+    \pgfmoveto{\pgfxy(-0.1,5.5)}%
+    \pgfbezier{\pgfxy(-0.1,5.55)}{\pgfxy(-0.05,5.6)}{\pgfxy(0,5.6)}%
+    \pgfbezier{\pgfxy(0.05,5.6)}{\pgfxy(0.1,5.55)}{\pgfxy(0.1,5.5)}%
+    \pgflineto{\pgfxy(0.1,4.25)}%
+    \pgfbezier{\pgfxy(0.1,4.25)}{\pgfxy(0.05,4.15)}{\pgfxy(0,4.15)}%
+    \pgfbezier{\pgfxy(-0.05,4.15)}{\pgfxy(-0.1,4.2)}{\pgfxy(-0.1,4.25)}%
+    \pgfclosepath%
+    \pgfstroke%
+  \end{pgftranslate}\ignorespaces}
+
+\newcommand{\ClipSlot}[1]{%
+  \pgfrect[clip]{\pgfrelative{\pgfxy(-0.1,0)}{\pgfpoint{#1}{4cm}}}{\pgfxy(0.2,1.5)}\ignorespaces}
+
+\newcommand{\ClipSlotZwei}[1]{%
+  \pgfrect[clip]{\pgfrelative{\pgfxy(-0.1,0)}{\pgfpoint{#1}{4.25cm}}}{\pgfxy(0.2,1.25)}\ignorespaces}
+
+
+\AtBeginSection[]{\frame{\frametitle{Outline}\tableofcontents[current]}}
+
+\begin{document}
+
+\frame{\titlepage}
+
+%\section*{Outline}
+\part{Main Part}
+\frame{\frametitle{Outline}\tableofcontents[part=1]}
+
+\section{History}
+
+\subsection{Enumerability in Recursion and Automata Theory}
+
+\frame
+{
+  \frametitle{Motivation of Enumerability}
+
+  \begin{block}{Problem}
+    Many functions are not computable or not efficiently computable.
+  \end{block}
+  \vskip-1em
+  \begin{overprint}
+  \onslide<1-2>
+  \begin{example}
+    \begin{overprint}
+    \onslide<1>
+      \vskip0.5em
+      \begin{itemize}
+      \item
+        $\NumSAT$:\\
+        How many satisfying assignments does a formula have?
+      \end{itemize}
+
+    \onslide<2>
+      \vskip0.5em
+        For difficult languages~$A$:
+        \begin{itemize}
+        \item
+          Cardinality function $\NumA^n$:\\
+          \alert{How many} input words are in~$A$?
+        \item
+          Characteristic function $\chi_A^n$:\\
+          \alert{Which} input words are in~$A$?
+        \end{itemize}
+      \begin{pgfpicture}{-9cm}{0.75cm}{-9cm}{2cm}
+        
+        \pgfnodebox{words}[virtual]{\pgfxy(0,3.5)}{$(w_1, \alert{w_2},
+          w_3, w_4, \alert{w_5})$}{2pt}{5pt}
+
+        \color{red}
+        \pgfputat{\pgfxy(0.75,4.5)}{\pgfbox[center,base]{in $A$}}
+        \pgfxyline(0.75,4.4)(-0.6,3.7)
+        \pgfxyline(0.75,4.4)(1.2,3.7)
+        \color{black}
+
+        \pgfnodebox{number}[virtual]{\pgfxy(-1,1)}{2}{2pt}{2pt}
+        \pgfnodebox{string}[virtual]{\pgfxy(1,1)}{0\alert{1}00\alert{1}}{2pt}{2pt}
+
+        \pgfsetstartarrow{\pgfarrowbar}
+        \pgfsetendarrow{\pgfarrowto}
+
+        \pgfnodeconnline{words}{string}%{-60}{120}{1cm}{1cm}
+        \pgfnodeconnline{words}{number}%{-120}{60}{1cm}{1cm}
+
+        \pgfputat{\pgfxy(-0.9,2.3)}{\pgfbox[center,base]{$\NumA^5$}}
+        \pgfputat{\pgfxy(0.9,2.3)}{\pgfbox[center,base]{$\chi_A^5$}}
+      \end{pgfpicture}
+    \end{overprint}
+  \end{example}
+
+  \onslide<3>
+    \begin{block}{Solutions}
+      Difficult functions can be 
+      \begin{itemize}
+      \item
+        computed using probabilistic algorithms,
+      \item
+        computed efficiently on average,
+      \item
+        approximated, or
+      \item<alert@1->
+        enumerated.
+      \end{itemize}
+    \end{block}
+  \end{overprint}
+}
+
+\frame
+{
+  \frametitle{Enumerators Output Sets of Possible Function Values}
+  \begin{columns}
+    \begin{column}{4.5cm}
+      \begin{pgfpicture}{-0.5cm}{0cm}{4cm}{6cm}
+
+        \pgfputat{\pgfxy(0,0.5)}{\Band{}{output tape}}
+
+        \BaenderHell
+
+        \color{black}
+
+        \only<1-4,6->{\pgfputat{\pgfxy(1.75,2.5)}{\pgfbox[center,center]{\pgfuseimage{computerimage}}}}
+        \only<5>{\pgfputat{\pgfxy(1.75,2.5)}{\pgfbox[center,center]{\pgfuseimage{computerworkingimage}}}}
+
+        \begin{pgfscope}
+          \only<1>{\ClipSlot{0cm}}
+          \only<2>{\ClipSlot{0.6cm}}
+          \only<3>{\ClipSlot{1.2cm}}
+          \only<4->{\ClipSlot{1.8cm}}
+          \BaenderNormal
+        \end{pgfscope}        
+
+        \only<1>{\Slot{0cm}}
+        \only<2>{\Slot{0.6cm}}
+        \only<3>{\Slot{1.2cm}}
+        \only<4->{\Slot{1.8cm}}
+        
+        \only<6->{
+          \pgfxyline(0,0.5)(0,1)
+          \pgfxyline(1,0.5)(1,1)
+          \pgfputat{\pgfxy(0.5,0.75)}{\pgfbox[center,center]{$u_1$}}}
+        \only<7->{
+          \pgfxyline(2,0.5)(2,1)
+          \pgfputat{\pgfxy(1.5,0.75)}{\pgfbox[center,center]{\alert<9>{$u_2$}}}}
+        \only<8->{
+          \pgfxyline(3,0.5)(3,1)
+          \pgfputat{\pgfxy(2.5,0.75)}{\pgfbox[center,center]{$u_3$}}}
+        
+        \pgfsetlinewidth{0.6pt}
+        \color{structure}
+        \pgfsetendarrow{\pgfarrowto}
+        
+        \pgfsetlinewidth{0.6pt}
+        \color{structure}
+        \pgfsetendarrow{\pgfarrowto}
+        \only<-5>{\pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
+        \only<6>{\pgfxycurve(1.75,1.5)(1.75,1)(1,1.5)(1,1.05)}
+        \only<7>{\pgfxycurve(1.75,1.5)(1.75,1)(2,1.5)(2,1.05)}
+        \only<8->{\pgfxycurve(1.75,1.5)(1.75,1)(3,1.5)(3,1.05)}
+        
+        \only<1>{\pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)}
+        \only<2>{\pgfxycurve(1.75,3.5)(1.75,3.75)(0.6,3.5)(0.6,3.85)}
+        \only<3>{\pgfxycurve(1.75,3.5)(1.75,3.75)(1.2,3.5)(1.2,3.85)}
+        \only<4->{\pgfxycurve(1.75,3.5)(1.75,3.75)(1.8,3.5)(1.8,3.85)}
+      \end{pgfpicture}
+    \end{column}
+    \begin{column}{6.5cm}
+      \begin{definition}[1987, 1989, 1994, 2001]
+        An \alert{$m$-enumerator} for a function~$f$
+        \begin{enumerate}
+        \item<alert@1-4>
+          reads $n$ input words $w_1$, \dots, $w_n$,
+        \item<alert@5>
+          does a computation,
+        \item<alert@6-8>
+          outputs at most $m$ values,
+        \item<alert@9>
+          one of which is $f(w_1,\dots,w_n)$.
+        \end{enumerate}
+      \end{definition}
+    \end{column}
+  \end{columns}
+}
+
+\subsection{Known Weak Cardinality Theorem}
+
+\frame
+{
+  \frametitle{How Well Can the Cardinality Function Be Enumerated?}
+
+  \begin{block}{Observation}
+    For fixed~$n$, the cardinality function $\NumA^n$
+    \begin{itemize}
+    \item
+      can be \alert{$1$}-enumerated by Turing machines only for \alert{recursive}~$A$,~but\hskip-0.5cm\hbox{}
+    \item
+      can be \alert{$(n+1)$}-enumerated for \alert{every} language~$A$.
+    \end{itemize}
+  \end{block}
+
+  \begin{alertblock}{Question}<2->
+    What about $2$-, $3$-, $4$-, \dots, $n$-enumerability?
+  \end{alertblock}
+}
+
+\newtheorem{card}{Cardinality Theorem}[theorem]
+\newtheorem{weakcard}{Weak Cardinality Theorems}[theorem]
+
+\frame
+{
+  \frametitle{How Well Can the Cardinality Function\\ Be Enumerated
+    by Turing Machines?}
+
+  \begin{card}[Kummer, 1992]
+    If $\NumA^n$ is $n$-enumerable by a Turing machine, then $A$ is
+    recursive.
+  \end{card}
+
+  \begin{weakcard}[\uncover<2->{\alert<1-2>{1987},} \uncover<3->{\alert<3>{1989},}
+      \uncover<4->{\alert<4>{1992}}]<2-> 
+    \begin{enumerate}
+    \item<2-| alert@2>
+      If $\chi_A^n$ is $n$-enumerable by a Turing machine, then $A$ is
+        recursive.
+    \item<3-| alert@3>
+      If $\NumA^2$ is $2$-enumerable by a Turing machine, then $A$ is
+        recursive.
+    \item<4-| alert@4>
+      If $\NumA^n$ is $n$-enumerable by a Turing machine that never
+        enumerates both $0$ and~$n$, then $A$ is recursive.
+    \end{enumerate}
+  \end{weakcard}
+}
+
+
+\frame
+{
+  \frametitle{How Well Can the Cardinality Function\\ Be Enumerated
+    by Finite Automata?}
+
+  \begin{alertblock}{Conjecture}
+    If $\NumA^n$ is $n$-enumerable by a \alert{finite automaton}, then $A$ is
+    \alert{regular}.
+  \end{alertblock}
+
+  \begin{weakcard}[2001, 2002]
+    \begin{enumerate}
+    \item
+      If $\chi_A^n$ is $n$-enumerable by a \alert{finite automaton}, then $A$ is
+      \alert{regular}.
+    \item
+      If $\NumA^2$ is $2$-enumerable by a \alert{finite automaton}, then $A$ is
+      \alert{regular}.
+    \item
+      If $\NumA^n$ is $n$-enumerable by a \alert{finite automaton} that never
+      enumerates both $0$ and~$n$, then $A$ is \alert{regular}.
+    \end{enumerate}
+  \end{weakcard}
+}
+
+
+\subsection{Why Do Cardinality Theorems Hold Only for Certain Models?}
+
+\frame
+{
+  \frametitle{Cardinality Theorems Do Not Hold for All Models}
+
+  \begin{pgfpicture}{-2.5cm}{0.3cm}{0.5cm}{6.5cm}
+    \pgfsetlinewidth{0.6pt}
+    
+    \pgfsetendarrow{\pgfarrowto}
+    \pgfxyline(0,0.5)(0,6.5)
+    \pgfclearendarrow
+
+    \pgfputat{\pgfxy(-0.2,5.75)}{\pgfbox[right,base]{Turing machines}}
+
+    \only<2>{
+    \pgfputat{\pgfxy(-0.2,3.75)}{\pgfbox[right,base]{\alert{resource-bounded}}}
+    \pgfputat{\pgfxy(-0.2,3.25)}{\pgfbox[right,base]{\alert{machines}}}
+    \pgfcircle[fill]{\pgfxy(0,3.6)}{2pt}
+    \pgfputat{\pgfxy(0.4,3.5)}{\pgfbox[left,base]{Weak cardinality
+        theorems do \alert{not} hold.}}}
+    
+    \pgfputat{\pgfxy(-0.2,1.5)}{\pgfbox[right,base]{finite}}
+    \pgfputat{\pgfxy(-0.2,1)}{\pgfbox[right,base]{automata}}
+
+    \pgfcircle[fill]{\pgfxy(0,5.85)}{2pt}
+    \pgfcircle[fill]{\pgfxy(0,1.35)}{2pt}
+
+    \pgfputat{\pgfxy(0.4,5.75)}{\pgfbox[left,base]{Weak cardinality
+        theorems hold.}}
+    \pgfputat{\pgfxy(0.4,1.25)}{\pgfbox[left,base]{Weak cardinality
+        theorems hold.}}
+  \end{pgfpicture}
+}
+
+\frame
+{
+  \frametitle{Why?}
+
+  \begin{block}{First Explanation}<1>
+    The weak cardinality theorems hold both for recursion and automata
+    theory \alert{by coincidence}.
+  \end{block}
+
+  \begin{block}{Second Explanation}<1-2>
+    The weak cardinality theorems hold both for
+    recursion and automata theory, \alert{because they are
+      instantiations of\\ single, unifying theorems}.
+  \end{block}
+  
+  \vskip1em
+  \visible<2->{
+    The second explanation is correct.\\
+    The theorems can (almost) be unified using first-order logic.
+    }
+}
+   
+    
+
+\section[Unification by Logic]{Unification by First-Order Logic}
+
+\subsection{Elementary Definitions}
+
+\frame
+{
+  \frametitle{What Are Elementary Definitions?}
+
+  \begin{definition}
+    A relation~$R$ is \alert{elementarily definable in a
+    logical structure~$\mathcal S$} if
+    \begin{enumerate}
+    \item
+      there exists a first-order formula~$\phi$,
+    \item
+      that is true exactly for the elements of~$R$.
+    \end{enumerate}    
+  \end{definition}
+
+  \begin{example}
+    The set of even numbers is elementarily definable in $(\Nat, +)$
+    via the formula $\phi(x) \equiv \exists z \centerdot z+z=x$.
+  \end{example}
+
+  \begin{example}
+    The set of powers of 2 is not elementarily definable in $(\Nat, +)$.
+  \end{example}
+}
+
+
+\frame
+{
+  \frametitle{Characterisation of Classes by Elementary Definitions}
+
+  \begin{theorem}[B\"uchi, 1960]
+    There exists a logical structure~$(\Nat, +, \mathrm e_2)$
+    such that a set $A \subseteq \Nat$ is\\ \alert{regular} iff it is 
+    \alert{elementarily definable in~$(\Nat, +, \mathrm e_2)$}.
+  \end{theorem}
+
+  \begin{theorem}
+    There exists a logical structure~$\mathcal R$ such that a set $A
+    \subseteq \Nat$ is \alert{recursively enumerable} iff it is \alert{positively
+    elementarily definable in~$\mathcal R$}.\hskip-0.5cm\hbox{}
+  \end{theorem}
+}
+
+
+
+\frame
+{
+  \frametitle{Characterisation of Classes by Elementary Definitions} 
+
+  \begin{pgfpicture}{-5.4cm}{0.3cm}{5.4cm}{6.5cm}
+    \pgfsetlinewidth{0.6pt}
+    
+    \pgfsetendarrow{\pgfarrowto}
+    \pgfxyline(0,0.3)(0,6.5)
+    \pgfclearendarrow
+
+    \only<2->{
+    \pgfputat{\pgfxy(-0.3,0.5)}{\pgfbox[right,base]{Presburger arithmetic}}
+    \pgfcircle[fill]{\pgfxy(0,0.6)}{2pt}
+    \pgfputat{\pgfxy(0.3,0.5)}{\pgfbox[left,base]{$(\Nat, +)$}}
+    }
+    \pgfputat{\pgfxy(-0.3,1.5)}{\pgfbox[right,base]{regular sets}}
+    \pgfcircle[fill]{\pgfxy(0,1.6)}{2pt}
+    \pgfputat{\pgfxy(0.3,1.5)}{\pgfbox[left,base]{$(\Nat, +, \mathrm e_2)$}}
+
+    \pgfputat{\pgfxy(-0.3,2.5)}{\pgfbox[right,base]{\alert{resource-bounded classes}}}
+    \pgfcircle[fill]{\pgfxy(0,2.6)}{2pt}
+    \pgfputat{\pgfxy(0.3,2.5)}{\pgfbox[left,base]{\alert{none}}}
+
+    \pgfputat{\pgfxy(-0.3,3.5)}{\pgfbox[right,base]{recursively enumerable sets}}
+    \pgfcircle[fill]{\pgfxy(0,3.6)}{2pt}
+    \pgfputat{\pgfxy(0.3,3.5)}{\pgfbox[left,base]{positively in $\mathcal R$}}
+
+    \only<2->{
+    \pgfputat{\pgfxy(-0.3,4.5)}{\pgfbox[right,base]{arithmetic hierarchy}}
+    \pgfcircle[fill]{\pgfxy(0,4.6)}{2pt}
+    \pgfputat{\pgfxy(0.3,4.5)}{\pgfbox[left,base]{$(\Nat, +, \cdot)$}}
+
+    \pgfputat{\pgfxy(-0.3,5.5)}{\pgfbox[right,base]{ordinal number arithmetic}}
+    \pgfcircle[fill]{\pgfxy(0,5.6)}{2pt}
+    \pgfputat{\pgfxy(0.3,5.5)}{\pgfbox[left,base]{$(\mathrm{On}, +, \cdot)$}}}
+  \end{pgfpicture}
+}
+
+
+\subsection{Enumerability for First-Order Logic}
+
+\frame
+{
+  \frametitle{Elementary Enumerability is a Generalisation of\\ Elementary Definability}
+
+  \begin{columns}
+    \begin{column}{3.25cm}
+      \begin{pgfpicture}{-0.25cm}{0cm}{3cm}{4cm}
+
+        \color{shaded}
+        \pgfmoveto{\pgfxy(0,1.3)}
+        \pgfcurveto{\pgfxy(0.5,2.3)}{\pgfxy(2,1.5)}{\pgfxy(2.5,2.3)}
+        \pgflineto{\pgfxy(2.5,1.7)}
+        \pgfcurveto{\pgfxy(2,0.7)}{\pgfxy(1,1.7)}{\pgfxy(0,0.5)}
+        \pgfclosepath
+        \pgffill
+
+        \pgfsetlinewidth{0.8pt}
+        \color{black}
+        \pgfmoveto{\pgfxy(0,1)}
+        \pgflineto{\pgfxy(0.25,1.15)}
+        \pgflineto{\pgfxy(0.5,1.5)}
+        \pgflineto{\pgfxy(1,1.7)}
+        \pgflineto{\pgfxy(1.5,1.5)}
+        \pgflineto{\pgfxy(2,1.4)}
+        \pgflineto{\pgfxy(2.25,1.5)}
+        \pgflineto{\pgfxy(2.5,2)}
+        \pgfstroke          
+
+        \pgfsetlinewidth{0.4pt}
+        \pgfsetendarrow{\pgfarrowto}
+        \pgfxyline(0,0)(2.5,0)
+        \pgfxyline(0,0)(0,3)
+        \pgfputat{\pgfxy(0.5,1.9)}{\pgfbox[center,base]{$R$}}
+        \pgfputat{\pgfxy(2.6,0)}{\pgfbox[left,center]{$x$}}
+        \pgfputat{\pgfxy(0,3.2)}{\pgfbox[center,base]{$f(x)$}}
+        \pgfputat{\pgfxy(2.55,2)}{\pgfbox[left,center]{$f$}}
+      \end{pgfpicture}
+    \end{column}
+    \begin{column}{7.5cm}
+      \begin{definition}
+        A function~$f$ is\\
+        \alert{elementarily $m$-enumerable in a structure~$\mathcal S$} if
+        \begin{enumerate}
+        \item
+          its graph is contained in an\\
+          \alert{elementarily definable} relation~$R$,
+        \item
+          which is \alert{$m$-bounded}, i.\kern1pt e., for each~$x$
+          there are at most~$m$ different~$y$ with $(x,y) \in R$.
+        \end{enumerate}
+      \end{definition}
+    \end{column}
+  \end{columns}
+}
+
+\frame
+{
+  \frametitle{The Original Notions of Enumerability are Instantiations}
+
+  \begin{theorem}
+    A function is $m$-enumerable by a \alert{finite automaton} iff\\
+    it is elementarily $m$-enumerable in \alert{$(\Nat, +, \mathrm e_2)$}.
+  \end{theorem} 
+
+  \begin{theorem}
+    A function is $m$-enumerable by a \alert{Turing machine} iff\\
+    it is positively elementarily $m$-enumerable in \alert{$\mathcal R$}.
+  \end{theorem} 
+}
+
+%\subsection{Cross Product Theorem for First-Order Logic}
+
+\subsection{Weak Cardinality Theorems for First-Order Logic}
+
+\frame
+{
+  \frametitle{The First Weak Cardinality Theorem}
+  
+  \begin{theorem}
+    Let $\mathcal S$ be a logical structure with universe~$U$ and let
+    $A \subseteq U$. If
+    
+    \begin{enumerate}
+    \item
+      $\mathcal S$ is well-orderable and
+    \item
+      \alert{$\chi_A^n$} is elementarily \alert{$n$}-enumerable in~$\mathcal S$,
+    \end{enumerate}
+    
+    then \alert{$A$ is elementarily definable} in~$\mathcal S$.    
+  \end{theorem}
+  \begin{overprint}
+    \onslide<2>
+      \begin{corollary}
+        If $\chi_A^n$ is $n$-enumerable by a finite automaton, then
+        $A$ is regular.
+      \end{corollary}
+
+    \onslide<3>
+      \begin{corollary}[with more effort]
+        If $\chi_A^n$ is $n$-enumerable by a Turing machine, then $A$
+        is recursive.
+      \end{corollary}
+  \end{overprint}  
+}
+
+\frame
+{
+  \frametitle{The Second Weak Cardinality Theorem}
+  
+  \begin{theorem}
+    Let $\mathcal S$ be a logical structure with universe~$U$ and let
+    $A \subseteq U$. If
+    
+    \begin{enumerate}
+    \item
+      $\mathcal S$ is well-orderable,
+    \item
+      every finite relation on~$U$ is elementarily definable
+      in~$\mathcal S$, and
+    \item
+      \alert{$\NumA^2$} is elementarily \alert{$2$}-enumerable in~$\mathcal S$,
+    \end{enumerate}
+    
+    then \alert{$A$ is elementarily definable} in~$\mathcal S$.    
+  \end{theorem}
+%  \begin{overlayarea}{\textwidth}{2cm}
+%    \only<2>{
+%      \begin{corollary}
+%        If $\NumA^2$ is $2$-enumerable by a finite automaton, then
+%        $A$ is regular.
+%      \end{corollary}}%
+%    \only<3>{
+%      \begin{block}{Corollary}
+%        If $\NumA^2$ is $2$-enumerable by a Turing machine, then $A$
+%        is recursive in the halting problem.
+%      \end{block}
+%      }
+%  \end{overlayarea}
+}
+
+\frame
+{
+  \frametitle{The Third Weak Cardinality Theorem}
+  
+  \begin{theorem}
+    Let $\mathcal S$ be a logical structure with universe~$U$ and let
+    $A \subseteq U$. If
+    
+    \begin{enumerate}
+    \item
+      $\mathcal S$ is well-orderable,
+    \item
+      every finite relation on~$U$ is elementarily definable
+      in~$\mathcal S$, and
+    \item
+      \alert{$\NumA^n$} is elementarily \alert{$n$}-enumerable in~$\mathcal S$ via a
+      relation that \alert{never `enumerates' both $0$ and~$n$},
+    \end{enumerate}
+    
+    then \alert{$A$ is elementarily definable} in~$\mathcal S$.    
+  \end{theorem}
+%  \begin{overlayarea}{\textwidth}{2cm}
+%    \only<2>{
+%      \begin{corollary}
+%        If $\NumA^n$ is $n$-enumerable by a finite automaton that
+%        never enumerates both $0$ and~$n$, then $A$ is regular.
+%      \end{corollary}}%
+%    \only<3>{
+%      \begin{block}{Corollary}
+%        If $\NumA^n$ is $n$-enumerable by a Turing machine that never
+%        enumerates both $0$ and~$n$, then $A$ is recursive in the
+%        halting problem.
+%      \end{block}
+%      }
+%  \end{overlayarea}
+}
+
+
+
+\frame
+{
+  \frametitle{Relationships Between Cardinality Theorems (CT)}
+
+  \begin{pgfpicture}{0cm}{0cm}{10cm}{5cm}
+    \only<2>{%
+    \color{alert}
+    \pgfnodebox{autX}[virtual]{\pgfxy(2.2,4)}{CT}{2pt}{2pt}
+    \color{black}}%
+    \pgfnodebox{autA}[virtual]{\pgfxy(1,3)}{1st Weak CT}{2pt}{2pt}
+    \pgfnodebox{autB}[virtual]{\pgfxy(1,2)}{2nd Weak CT}{2pt}{2pt}
+    \pgfnodebox{autC}[virtual]{\pgfxy(1,1)}{3rd Weak CT}{2pt}{2pt}
+
+    \only<2>{%
+    \color{alert}
+    \pgfnodebox{logX}[virtual]{\pgfxy(6.2,4.5)}{CT}{2pt}{2pt}%
+    \color{black}}%
+    \pgfnodebox{logA}[virtual]{\pgfxy(5,3.5)}{1st Weak CT}{2pt}{2pt}
+    \pgfnodebox{logB}[virtual]{\pgfxy(5,2.5)}{2nd Weak CT}{2pt}{2pt}
+    \pgfnodebox{logC}[virtual]{\pgfxy(5,1.5)}{3rd Weak CT}{2pt}{2pt}
+
+    \pgfnodebox{recX}[virtual]{\pgfxy(10.2,4)}{CT}{2pt}{2pt}
+    \pgfnodebox{recA}[virtual]{\pgfxy(9,3)}{1st Weak CT}{2pt}{2pt}
+    \pgfnodebox{recB}[virtual]{\pgfxy(9,2)}{2nd Weak CT}{2pt}{2pt}
+    \pgfnodebox{recC}[virtual]{\pgfxy(9,1)}{3rd Weak CT}{2pt}{2pt}
+
+    \pgfputat{\pgfxy(1,4.5)}{\pgfbox[center,base]{\structure{automata theory}}}
+    \pgfputat{\pgfxy(5,5)}{\pgfbox[center,base]{\structure{first-order logic}}}
+    \pgfputat{\pgfxy(9,4.5)}{\pgfbox[center,base]{\structure{recursion
+          theory}}}
+
+    {%
+    \color{structure}%
+    \pgfxyline(3,0)(3,5)
+    \pgfxyline(7,0)(7,5)
+    }%
+    \pgfsetendarrow{\pgfarrowto}
+    \pgfnodeconnline{logA}{autA}
+    \pgfnodeconnline{logA}{recA}
+    \pgfnodeconnline{logB}{autB}
+    \pgfnodeconnline{logC}{autC}
+
+    \pgfnodeconncurve{recX}{recA}{-60}{5}{10pt}{10pt}
+    \pgfnodeconncurve{recX}{recB}{-55}{5}{10pt}{20pt}
+    \pgfnodeconncurve{recX}{recC}{-50}{5}{10pt}{30pt}
+
+    \only<2>{%
+      \alert{
+        \pgfnodeconnline{logX}{autX}
+        \pgfnodeconncurve{logX}{logA}{-60}{0}{10pt}{10pt}
+        \pgfnodeconncurve{logX}{logB}{-55}{0}{10pt}{20pt}
+        \pgfnodeconncurve{logX}{logC}{-50}{0}{10pt}{30pt}
+        \pgfnodeconncurve{autX}{autA}{-60}{11}{10pt}{10pt}
+        \pgfnodeconncurve{autX}{autB}{-55}{11}{10pt}{20pt}
+        \pgfnodeconncurve{autX}{autC}{-50}{11}{10pt}{30pt}
+      }
+    }
+
+    \pgfsetdash{{3pt}{3pt}}{0pt}
+    \pgfnodeconnline{logB}{recB}
+    \pgfnodeconnline{logC}{recC}
+
+    \only<2>{%
+    \alert{\pgfnodeconnline{logX}{recX}}}
+  \end{pgfpicture}
+}
+
+
+\section{Applications}
+
+\subsection{A Separability Result for First-Order Logic}
+
+%\frame
+%{
+%  \begin{columns}
+%    \begin{column}{2.4cm}
+%      \begin{pgfpicture}{-1.2cm}{-1.2cm}{1cm}{1cm}
+%        \color{shaded}
+%        \pgfrect[fill]{\pgfxy(-1.4,-1)}{\pgfxy(2.8,2)}
+
+%        \color{white}
+%        \pgfcircle[fill]{\pgfxy(-0.6,0)}{0.5cm}
+%        \pgfcircle[fill]{\pgfxy(0.6,0)}{0.5cm}
+%        \only<2->{%      
+%          \color{softred}
+%          \pgfcircle[fill]{\pgfxy(-0.6,0)}{0.6cm}}%
+%        %
+%        \color{black}
+%        \pgfcircle[stroke]{\pgfxy(-0.6,0)}{0.5cm}
+%        \pgfcircle[stroke]{\pgfxy(0.6,0)}{0.5cm}
+
+%        \pgfputat{\pgfxy(-0.6,0)}{\pgfbox[center,center]{$A^{(n)}$}}
+%        \pgfputat{\pgfxy(0.6,0)}{\pgfbox[center,center]{$\barA{}^{(n)}$}}     
+%      \end{pgfpicture}
+%    \end{column}
+%    \begin{column}{8cm}
+%      \begin{block}{Notation}
+%        Let $A^{(n)}$ contain all $n$ tuples of\\
+%        distinct elements of~$A$.
+%      \end{block}
+      
+%      \begin{block}{Theorem}
+%        Let $\mathcal S$ be a well-orderable logical structure in which
+%        all finite relations are elementarily definable.\\[0.5em]
+%        If $A^{(n)}$ and $\barA{}^{(n)}$ are \alert<2>{elementarily separable}
+%        in~$\mathcal S$, then~so~are~$A$~and~$\barA$.
+%      \end{block}
+
+%      \uncover<3>{
+%        \begin{alertblock}{Note}
+%          The theorem is no longer true if $\barA$ is replaced by an
+%          arbitrary set~$B$.
+%        \end{alertblock}
+%      }
+%    \end{column}
+%  \end{columns}
+%}
+
+
+\frame
+{
+  \begin{columns}
+    \begin{column}{4cm}
+      \begin{pgfpicture}{-2cm}{-1.75cm}{2cm}{2.25cm}
+        \color{shaded}
+        \pgfrect[fill]{\pgfxy(-2,-1.75)}{\pgfxy(4,4)}
+                                %\pgfcircle[fill]{\pgforigin}{2cm}
+
+        \only<1>{%
+          \color{white}%
+          \pgfcircle[fill]{\pgfpolar{90}{1cm}}{\innerradius}
+          \pgfcircle[fill]{\pgfpolar{210}{1cm}}{\innerradius}
+          \pgfcircle[fill]{\pgfpolar{330}{1cm}}{\innerradius}}%
+        \only<2->{%      
+        \color{softred}
+        \pgfcircle[fill]{\pgfpolar{90}{1cm}}{\radius}
+        \color{softgreen}
+        \pgfcircle[fill]{\pgfpolar{210}{1cm}}{\radius}
+        \color{softblue}
+        \pgfcircle[fill]{\pgfpolar{330}{1cm}}{\radius}}%
+        %
+      \only<2->{%
+        \begin{pgftranslate}{\pgfpolar{90}{1cm}}
+          \pgfzerocircle{\radius}
+          \pgfclip
+          
+          \begin{pgftranslate}{\pgfpolar{-90}{1cm}}
+            \color{softrb}
+            \pgfcircle[fill]{\pgfpolar{330}{1cm}}{\radius}
+            \color{softrg}
+            \pgfcircle[fill]{\pgfpolar{210}{1cm}}{\radius}
+          \end{pgftranslate}
+        \end{pgftranslate}
+
+        \begin{pgftranslate}{\pgfpolar{210}{1cm}}
+          \pgfzerocircle{\radius}
+          \pgfclip
+          
+          \begin{pgftranslate}{\pgfpolar{30}{1cm}}
+            \color{softgb}
+            \pgfcircle[fill]{\pgfpolar{330}{1cm}}{\radius}
+          \end{pgftranslate}
+        \end{pgftranslate}}%
+        %
+        \color{black}
+        \pgfcircle[stroke]{\pgfpolar{90}{1cm}}{\innerradius}
+        \pgfcircle[stroke]{\pgfpolar{210}{1cm}}{\innerradius}
+        \pgfcircle[stroke]{\pgfpolar{330}{1cm}}{\innerradius}
+
+        \pgfputat{\pgfrelative{\pgfpolar{90}{1cm}}%
+          {\pgfpoint{0pt}{-.5ex}}}%
+        {\pgfbox[center,base]{$A\times \barA$}}
+        \pgfputat{\pgfrelative{\pgfpolar{210}{1cm}}%
+          {\pgfpoint{0pt}{-.5ex}}}%
+        {\pgfbox[center,base]{$A\times A$}}
+        \pgfputat{\pgfrelative{\pgfpolar{330}{1cm}}%
+          {\pgfpoint{0pt}{-.5ex}}}%
+        {\pgfbox[center,base]{$\barA\times \barA$}}
+
+      \end{pgfpicture}
+    \end{column}
+    \begin{column}{6.8cm}
+      \begin{theorem}
+        Let $\mathcal S$ be a well-orderable logical structure in which
+        all finite relations are elementarily definable.\\[0.5em]
+        If there exist elementarily definable supersets of
+        {\color<2>{darkgreen}$A \times A$},
+        {\color<2>{darkred}$A \times \barA$}, and
+        {\color<2>{darkblue}$\barA \times \barA$} whose
+        intersection is empty,\\
+        then $A$ is elementarily definable in~$\mathcal S$. 
+      \end{theorem}  
+      \begin{alertblock}{Note}<3>
+        The theorem is no longer true\\
+        if we add $\barA \times A$ to the list. 
+      \end{alertblock}%
+    \end{column}
+  \end{columns}
+}
+
+
+\section*{Summary}
+
+\frame
+{
+  \frametitle{Summary}
+
+  \begin{block}{Summary}
+  \begin{itemize}
+  \item
+    The weak cardinality theorems for first-order logic \alert{unify}\\
+    the weak cardinality theorems of automata and recursion theory.
+  \item
+    The logical approach yields
+    weak cardinality theorems for\\ \alert{other computational models}.
+  \item
+    Cardinality theorems are \alert{separability theorems} in disguise.
+  \end{itemize}
+  \end{block}{}
+
+  \begin{block}{Open Problems}
+    \begin{itemize}
+    \item
+      Does a cardinality theorem for first-order logic hold?
+    \item
+      What about non-well-orderable structures like $(\mathbb R, +,
+      \cdot)$? 
+    \end{itemize}
+  \end{block}
+}
+
+\end{document}
+
+
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample6.pdf b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample6.pdf
new file mode 100644
index 00000000000..93a25983497
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample6.pdf
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample6.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample6.tex
new file mode 100644
index 00000000000..f77a6a1af4e
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample6.tex
@@ -0,0 +1,69 @@
+% $Header: /cvsroot/latex-beamer/latex-beamer/examples/beamerexample6.tex,v 1.5 2004/10/07 20:53:07 tantau Exp $
+
+\documentclass[serif]{beamer}
+
+% 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.
+
+%
+% The purpose of this example is to show how \part can be used to
+% organize a lecture.
+%
+
+\usepackage{times}
+\usepackage[latin1]{inputenc}
+
+\title{Beamer Animation Example}
+\author{Till~Tantau}
+\institute{
+  Fakult鋞 f黵 Elektrotechnik und Informatik\\
+  Technical University of Berlin}
+
+
+\begin{document}
+
+% View this in acroread with "loop after last page option" in full screen mode.
+
+\newcount\opaqueness
+\frame[plain]{
+  \itshape
+  \animate<1-30>
+  \Large
+
+  \only<1-10>{
+  \animatevalue<1-10>{\opaqueness}{100}{10}
+  \begin{colormixin}{\the\opaqueness!averagebackgroundcolor}
+    \begin{centering}
+      \Huge Urfaust\par
+    \end{centering}
+  \end{colormixin}
+  }
+ 
+  \only<11-20>{
+  \animatevalue<11-20>{\opaqueness}{100}{10}
+  \begin{colormixin}{\the\opaqueness!averagebackgroundcolor}
+    \begin{verse}
+      Hab nun, ach! die Philosophey,\\
+      Medizin und Juristerey \\
+      Und leider auch die Theologie\\
+      Durchaus studirt mit heisser M黨.
+    \end{verse}
+  \end{colormixin}
+  }
+ 
+  \only<21-30>{
+  \animatevalue<21-30>{\opaqueness}{100}{10}
+  \begin{colormixin}{\the\opaqueness!averagebackgroundcolor}
+    \begin{verse}
+      Da steh ich nun, ich armer Tohr,\\
+      Und binn so klug als wie zuvor.
+    \end{verse}
+  \end{colormixin}}
+}
+
+\end{document}
+
+