diff options
Diffstat (limited to 'Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.tex')
-rw-r--r-- | Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.tex | 941 |
1 files changed, 941 insertions, 0 deletions
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ät für Elektrotechnik und Informatik\\ + Technical University of Berlin} +\date[DLT 2003]{Developments in Language Theory Conference, 2003} +\subject{Theoretical Computer Science} + +\pgfdeclaremask{tu}{beamer-tu-logo-mask} +\pgfdeclaremask{ur}{beamer-ur-logo-mask} +\pgfdeclareimage[mask=tu,width=0.6cm]{tu-logo}{beamer-tu-logo} +\pgfdeclareimage[mask=ur,width=1cm]{ur-logo}{beamer-ur-logo} + +\logo{\vbox{\hbox to 1cm{\hfil\pgfuseimage{tu-logo}}\vskip0.1cm\hbox{\pgfuseimage{ur-logo}}}} + + +\begin{document} + +\frame{\titlepage} + +\section<presentation>*{Outline} + +\begin{frame} + \frametitle{Outline} + \tableofcontents[part=1,pausesections] +\end{frame} + +\AtBeginSubsection[] +{ + \begin{frame}<beamer> + \frametitle{Outline} + \tableofcontents[current,currentsubsection] + \end{frame} +} + +\part<presentation>{Main Talk} + +\section[Models]{The Model of Overhead-Free Computation} + +\subsection[Standard Model]{The Standard Model of Linear Space} + +\begin{frame} + \frametitle{The Standard Model of Linear Space} + + \begin{columns} + + \column{4.5cm} + \note[item]<1>{Point out that \$ is a marker symbol.} + \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm} + \only<1| trans:1>{ + \putmachine{\pgfxy(1.75,3)}{Turing machine} + \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0} + \selectpos{1}} + \only<2| handout:0| trans:2>{ + \putmachineworking{\pgfxy(1.75,3)}{Turing machine} + \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{0} + \selectpos{2}} + \only<3| handout:0| trans:3>{ + \putmachineworking{\pgfxy(1.75,3)}{Turing machine} + \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{0} + \selectpos{8}} + \only<4| handout:0| trans:4>{ + \putmachineworking{\pgfxy(1.75,3)}{Turing machine} + \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{\$} + \selectpos{7}} + \only<5| handout:0| trans:0>{ + \putmachineworking{\pgfxy(1.75,3)}{Turing machine} + \tape{\pgfxy(0,5)}{\$}{0}{1}{0}{0}{1}{0}{\$} + \selectpos{2}} + \only<6| handout:0| trans:0>{ + \putmachineworking{\pgfxy(1.75,3)}{Turing machine} + \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{0}{\$} + \selectpos{3}} + \only<7| handout:0| trans:0>{ + \putmachineworking{\pgfxy(1.75,3)}{Turing machine} + \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{0}{\$} + \selectpos{7}} + \only<8| handout:0| trans:0>{ + \putmachineworking{\pgfxy(1.75,3)}{Turing machine} + \tape{\pgfxy(0,5)}{\$}{\$}{1}{0}{0}{1}{\$}{\$} + \selectpos{6}} + \only<9| handout:0| trans:0>{ + \putmachineworking{\pgfxy(1.75,3)}{Turing machine} + \tape{\pgfxy(0,5)}{\$}{\$}{\$}{\$}{\$}{\$}{\$}{\$} + \selectpos{5}} + \only<10| handout:0| trans:5>{ + \putmachine{\pgfxy(1.75,3)}{Turing machine} + \tape{\pgfxy(0,5)}{\$}{\$}{\$}{\$}{\$}{\$}{\$}{\$} + \selectpos{5}} + \end{pgfpicture} + + \column{6cm} + \begin{block}{Characteristics} + \begin{itemize} + \item + Input fills \alert{fixed-size tape} + \item + Input may be \alert{modified} + \item + Tape alphabet \alert{is larger than}\\ input alphabet + \note[item]<1>{Stress the larger tape alphabet.} + \end{itemize} + \end{block} + \end{columns} +\end{frame} + + +\begin{frame} + \frametitle{Linear Space is a Powerful Model} + + \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6cm} + \pgfsetlinewidth{0.8pt} + \pgfxyline(-5,0)(5,0) + + \pgfsetlinewidth{0.4pt} + + \pgfheaplabeledcentered{2cm}{2.5cm}{$\Class{CFL}$} + \pgfheaplabeledcentered{3.5cm}{3cm}{\raise10pt\hbox{}$\Class{DLINSPACE}$} + \pgfheaplabeledcentered{5cm}{4cm}{\raise13pt\hbox{}$\Class{NLINSPACE} = \Class{CSL}$} + \pgfheaplabeledcentered{6cm}{5cm}{$\Class{PSPACE}$} + \note[item]{Explain CSL.} + + \pgfsetdash{{3pt}{3pt}}{0pt} + \pgfheaplabeled{\pgfxy(0,3.3)}{\pgfxy(-5,6)}{\pgfxy(5,6)}{}% + \pgfputat{\pgfxy(-4.6,5.75)}{\pgfbox[left,base]{$\Class{PSPACE}\!\text{-hard}$}}% + \end{pgfpicture} + \note[item]{Point out the connections to formal language theory.} +\end{frame} + + +\subsection[Our Model]{Our Model of Absolutely No Space Overhead} + +\begin{frame} + \frametitle{Our Model of ``Absolutely No Space Overhead''} + + \transdissolve<7>[duration=0.2] + + \begin{columns} + + \column{4.5cm} + \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm} + \only<1| trans:1>{% + \putmachinea{\pgfxy(1.75,3)}{Turing machine}% + \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0}% + \selectpos{1}}% + \only<2| handout:0| trans:2>{% + \putmachineworkinga{\pgfxy(1.75,3)}{Turing machine}% + \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{0}% + \selectpos{2}}% + \only<3| handout:0| trans:3>{% + \putmachineworkinga{\pgfxy(1.75,3)}{Turing machine}% + \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{0}% + \selectpos{8}}% + \only<4| handout:0| trans:0>{% + \putmachineworkinga{\pgfxy(1.75,3)}{Turing machine}% + \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{1}% + \selectpos{7}}% + \only<5| handout:0| trans:0>{% + \putmachineworkinga{\pgfxy(1.75,3)}{Turing machine}% + \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{1}% + \selectpos{2}}% + \only<6| handout:0| trans:0>{% + \putmachineworkinga{\pgfxy(1.75,3)}{Turing machine}% + \tape{\pgfxy(0,5)}{1}{1}{1}{0}{0}{1}{0}{1}% + \selectpos{3}}% + \only<7| handout:0| trans:4>{% + \putmachinea{\pgfxy(1.75,3)}{Turing machine}% + \pgfputat{\pgfxy(1.75,5.5)}{\pgfbox[center,center]{\pgfuseimage{ram}}}% + \pgfnodecircle{n3}[virtual]{\pgfxy(1.25,5)}{2pt}% + \selectpos{3}}% + \end{pgfpicture} + + \column{6cm} + \begin{overprint} + \onslide<1-6| trans:1-3| handout:1> + \begin{block}{Characteristics} + \begin{itemize} + \item + Input fills \alert{fixed-size tape} + \item + Input may be \alert{modified} + \item + Tape alphabet \alert{equals}\\ + input alphabet + \end{itemize} + \end{block} + \onslide<7-| trans:4| handout:2> + \begin{alertblock}{Intuition} + \begin{itemize} + \item + Tape is used like a\\ RAM module. + \end{itemize} + \end{alertblock} + \end{overprint} + \end{columns} + \note[item]<6>{Point out that no markers are used.} +\end{frame} + + +\begin{frame} + \frametitle{Definition of Overhead-Free Computations} + + \begin{Definition} + A Turing machine is \alert{overhead-free} if + \begin{enumerate} + \item + it has only a single tape, + \item + writes only on input cells, + \item + writes only symbols drawn from the input alphabet. + \end{enumerate} + \end{Definition} +\end{frame} + +\begin{frame} + \frametitle{Overhead-Free Computation Complexity Classes} + + \begin{Definition} + A language $L \subseteq \Sigma^*$ is in + \begin{description} + \item[\alert<1| handout:0| trans:0>{$\DOF$}% + {\note[item]<1>{Joke about German pronunciation}}] + if $L$ is accepted by a deterministic overhead-free machine with + input alphabet~$\Sigma$, + \pause + \item[\alert<2| handout:0| trans:0>{$\DOFpoly$}] + if $L$ is accepted by a deterministic overhead-free machine with + input alphabet~$\Sigma$ in polynomial time. + \pause + \item[\alert<3| handout:0| trans:0>{$\NOF$}] + is the nondeterministic version of $\DOF$, + \note[item]<3>{Stress meaning of D and N.} + \pause + \item[\alert<4| handout:0| trans:0>{$\NOFpoly$}] + is the nondeterministic version of $\DOFpoly$. + \end{description} + \end{Definition} +\end{frame} + +\begin{frame} + \frametitle{Simple Relationships among\\ Overhead-Free Computation Classes} + + \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6cm} + \pgfsetlinewidth{0.8pt} + \pgfxyline(-5,0)(5,0) + + \pgfsetlinewidth{0.4pt} + + \pgfheaplabeledcentered{1.75cm}{2cm}{$\DOFpoly$} + \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOF$} + \pgfheaplabeledcentered{2.5cm}{3.5cm}{$\NOFpoly$} + \pgfheaplabeledcentered{5cm}{4cm}{$\NOF$} + + \pgfheaplabeledcentered{6cm}{5cm}{\raise10pt\hbox{}$\Class{NLINSPACE}$} + \end{pgfpicture} +\end{frame} + + +\section[Power of the Model]{The Power of Overhead-Free Computation} + + +\subsection{Palindromes} + +\begin{frame} + \frametitle{Palindromes Can be Accepted in an Overhead-Free Way} + + \begin{columns} + + \column{4.5cm} + \begin{pgfpicture}{-0.5cm}{1cm}{4cm}{7cm} + \only<1| trans:1>{ + \putmachinea{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0} + \selectpos{1}} + \only<2| handout:0| trans:0>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{0} + \selectpos{2}} + \only<3| handout:0| trans:0>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{0} + \selectpos{8}} + \only<4| handout:0| trans:2>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{1} + \selectpos{7}} + \only<5| handout:0| trans:0>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{1}{0}{1}{0}{0}{1}{0}{1} + \selectpos{1}} + \only<6| handout:0| trans:3>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{1}{1}{0}{0}{1}{0}{1} + \selectpos{2}} + \only<7| handout:0| trans:0>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{1}{1}{0}{0}{1}{0}{1} + \selectpos{8}} + \only<8| handout:0| trans:4>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{1}{1}{0}{0}{1}{1}{0} + \selectpos{7}} + \only<9| handout:0| trans:0>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{1}{1}{0}{0}{1}{1}{0} + \selectpos{2}} + \only<10| handout:0| trans:0>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{1}{0} + \selectpos{3}} + \only<11| handout:0| trans:0>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{1}{0} + \selectpos{7}} + \only<12| handout:0| trans:5>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0} + \selectpos{6}} + \only<13| handout:0| trans:0>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{0}{1}{0}{0}{1}{0}{0} + \selectpos{3}} + \only<14| handout:0| trans:0>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{0}{0}{1}{0}{1}{0}{0} + \selectpos{4}} + \only<15| handout:0| trans:0>{ + \putmachineworkinga{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{0}{0}{1}{0}{1}{0}{0} + \selectpos{6}} + \only<16| handout:0| trans:6>{ + \putmachinea{\pgfxy(1.75,3)}{overhead-free machine} + \tape{\pgfxy(0,5)}{0}{0}{0}{1}{1}{0}{0}{0} + \selectpos{5}} + \end{pgfpicture} + + \column{6cm} + \begin{block}{Algorithm} + \alert<1| handout:0| trans:1>{Phase 1:\\ + Compare first and last bit} + + \quad \alert<2| handout:0| trans:2>{Place left end marker} + + \quad \alert<3| handout:0| trans:2>{Place right end marker} + \vskip1em + + \alert<4| handout:0| trans:3->{Phase 2:\\ + Compare bits next to end markers} + + \quad \alert<5,9,13| handout:0| trans:0>{Find left end marker} + + \quad \alert<6,10,14| handout:0| trans:0>{Advance left end marker} + + \quad \alert<7,11,15| handout:0| trans:0>{Find right end marker} + + \quad \alert<8,12,16| handout:0| trans:0>{Advance right end marker} + + \end{block} + \end{columns} + \note<1>{Use 3 minutes.} +\end{frame} + +\begin{frame} + \frametitle{Relationships among Overhead-Free Computation Classes} + + \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5cm} + \pgfsetlinewidth{0.8pt} + \pgfxyline(-5,0)(5,0) + + \pgfsetlinewidth{0.4pt} + + \pgfheaplabeledcentered{1.75cm}{2cm}{$\DOFpoly$} + \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOF$} + \pgfheaplabeledcentered{2.5cm}{3.5cm}{$\NOFpoly$} + \pgfheaplabeledcentered{5cm}{4cm}{$\NOF$} + + \pgfputat{\pgfxy(0,0.25)}{\pgfbox[center,base]{\alert{Palindromes}}} + \end{pgfpicture} +\end{frame} + + +\subsection{Linear Languages} + +\begin{frame} + \frametitle{A Review of Linear Grammars} + + \begin{Definition}<1> + A grammar is \alert{linear} if it is context-free and\\ there is + only one nonterminal per right-hand side. + \end{Definition} + + \begin{Example}<1> + $G_1\colon S \to 00S0 \mid 1$ and $G_2\colon S \to 0S10 \mid 0$. + \end{Example} + + \begin{Definition}<2-> + A grammar is \alert{deterministic} if\\ ``there is always only one + rule that can be applied.'' + \note<2>{Just explain intution.} + \end{Definition} + + \begin{Example}<2-> + $G_1\colon S \to 00S0 \mid 1$ is deterministic. + + $G_2\colon S \to 0S10 \mid 0$ is \alert{not} deterministic. + \end{Example} +\end{frame} + + +\begin{frame} + \frametitle{Deterministic Linear Languages\\ Can Be Accepted in an + Overhead-Free Way} + + \begin{Theorem} + Every deterministic linear language is in $\DOFpoly$. + \end{Theorem} +\end{frame} + +\begin{frame}[<+->] + \frametitle{Metalinear Languages\\ Can Be Accepted in an + Overhead-Free Way} + + \begin{Definition} + A language is \alert{metalinear} if it is the concatenation\\ of + linear languages. + \end{Definition} + + \begin{Example} + $\Lang{triple-palindrome} = \Set{uvw \mid \text{$u$, $v$, and $w$ are palindromes}}$. + \end{Example} + + \begin{Theorem} + Every metalinear language is in $\NOFpoly$. + \end{Theorem} +\end{frame} + +\begin{frame} + \frametitle{Relationships among Overhead-Free Computation Classes} + + \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5cm} + \pgfsetlinewidth{0.8pt} + \pgfxyline(-5,0)(5,0) + + \pgfsetlinewidth{0.4pt} + + \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOFpoly$} + \pgfheaplabeledcentered{4.25cm}{4cm}{$\NOFpoly$} + \pgfheaplabeledcentered{5cm}{5cm}{$\NOF$} + + \color{red}% + \pgfheaplabeledcentered{1.75cm}{2cm}{\raise10pt\hbox{}deterministic} + \pgfheaplabeledcentered{2.5cm}{3.5cm}{metalinear} + + \pgfputat{\pgfxy(0,0.6)}{\pgfbox[center,base]{linear}} + \end{pgfpicture} + \note[item]{Skip next subsection if more than 18 minutes have passed.} +\end{frame} + + +\subsection[Forbidden Subword]{Context-Free Languages with a Forbidden Subword} + +\begin{frame} + \frametitle{Definition of Almost-Overhead-Free Computations} + + \begin{Definition} + A Turing machine is \alert{almost-overhead-free} if + \begin{enumerate}[<+-| alert@+>] + \item it has only a single tape, + \item writes only on input cells, + \item writes only symbols drawn from the input alphabet\\ + plus one special symbol. + \end{enumerate} + \end{Definition} +\end{frame} + +\begin{frame} + \frametitle{Context-Free Languages with a Forbidden Subword\\ Can Be + Accepted in an Overhead-Free Way} + + \begin{Theorem} + Let $L$ be a context-free language with a forbidden word.\\ + Then $L \in \NOFpoly$. + \end{Theorem} + + \begin{overprint} + \onslide<1| handout:0| trans:0| article:0> + \hfill\hyperlinkframestartnext{\beamerskipbutton{Skip proof}} + \onslide<2| handout:1| trans:1> + \begin{proof} + Every context-free language can be accepted by a nondeterministic + almost-overhead-free machine in polynomial time. + \end{proof} + \end{overprint} +\end{frame} + +\begin{frame} + \frametitle{Relationships among Overhead-Free Computation Classes} + + \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5cm} + \pgfsetlinewidth{0.8pt} + \pgfxyline(-5,0)(5,0) + + \pgfsetlinewidth{0.4pt} + + \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOFpoly$} + \pgfheaplabeledcentered{4.25cm}{4cm}{$\NOFpoly$} + \pgfheaplabeledcentered{5cm}{5cm}{$\NOF$} + + \color{red}% + \pgfheaplabeledcentered{2.5cm}{3.5cm}{CFL with} + + \pgfputat{\pgfxy(0,1.6)}{\pgfbox[center,base]{forbidden subwords}} + \end{pgfpicture} +\end{frame} + + + +\subsection[Complete Languages]{Languages Complete for Polynomial Space} + +\begin{frame}<1>[label=pspacecomplete] + \frametitle{Overhead-Free Languages can be PSPACE-Complete} + + \begin{Theorem} + $\DOF$ contains languages that are complete for + $\Class{PSPACE}$. + \end{Theorem} + + \only<1| article:0| trans:0| handout:0> + { + \vskip1em + + \hyperlink{pspacecomplete<2>}{\beamergotobutton{Proof details}} + } + \only<2> + {% this is only shown in the appendix, where this frame is resumed. + \begin{proof} + \begin{enumerate} + \item + Let $A \in \Class{DLINSPACE}$ be $\Class{PSPACE}$-complete.\\ + Such languages are known to exist. + \item + Let $M$ be a linear space machine that accepts~$A \subseteq + \Set{0,1}^*$ with tape alphabet~$\Gamma$. + \item + Let $h \colon \Gamma \to \Set{0,1}^*$ be an isometric, injective + homomorphism. + \item + Then $h(L)$ is in $\Class{DOF}$ and it is + $\Class{PSPACE}$-complete. \qedhere + \end{enumerate} + \end{proof} + + \only<beamer>{\hfill\hyperlink{pspacecomplete<1>}{\beamerreturnbutton{Return}}} + } +\end{frame} + +\begin{frame} + \frametitle{Relationships among Overhead-Free Computation Classes} + + \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6cm} + \pgfsetlinewidth{0.8pt} + \pgfxyline(-5,0)(5,0) + + \pgfsetlinewidth{0.4pt} + + \pgfheaplabeledcentered{1.75cm}{2cm}{$\DOFpoly$} + \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOF$} + \pgfheaplabeledcentered{2.5cm}{3.5cm}{$\NOFpoly$} + \pgfheaplabeledcentered{5cm}{4cm}{$\NOF$} + + \pgfsetdash{{3pt}{3pt}}{0pt} + \pgfheaplabeled{\pgfxy(0,2.9)}{\pgfxy(-5,6)}{\pgfxy(5,6)}{}% + \pgfputat{\pgfxy(-4.6,5.75)}{\pgfbox[left,base]{$\Class{PSPACE}\!\text{-hard}$}}% + \end{pgfpicture} +\end{frame} + + +\section[Limitations of the Model]{Limitations of Overhead-Free Computation} + + +\subsection[Strict Inclusion]{Linear Space is Strictly More Powerful} + +\begin{frame} + \frametitle{Some Context-Sensitive Languages\\ + Cannot be Accepted in an Overhead-Free Way} + + \begin{Theorem} + $\DOF \subsetneq \Class{DLINSPACE}$. + \end{Theorem} + + \begin{Theorem} + $\NOF \subsetneq \Class{NLINSPACE}$. + \end{Theorem} + + \vskip1em + The proofs are based on old diagonalisations due to Feldman, Owings, + and Seiferas. +\end{frame} + +\begin{frame} + \frametitle{Relationships among Overhead-Free Computation Classes} + + \begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{6cm} + \pgfsetlinewidth{0.8pt} + \pgfxyline(-5,0)(5,0) + + \pgfsetlinewidth{0.4pt} + + \pgfheaplabeledcentered{3.5cm}{3cm}{$\DOF$} + \pgfheaplabeledcentered{5cm}{4cm}{$\NOF$} + + \pgfheaplabeledcentered{4.3cm}{4.5cm}{\raise8pt\hbox{}$\Class{DLINSPACE}$} + \pgfheaplabeledcentered{6cm}{5cm}{\raise10pt\hbox{}$\Class{NLINSPACE}$} + + \pgfsetdash{{3pt}{3pt}}{0pt} + \pgfheaplabeled{\pgfxy(0,2.9)}{\pgfxy(-5,6)}{\pgfxy(5,6)}{}% + \pgfputat{\pgfxy(-4.6,5.75)}{\pgfbox[left,base]{$\Class{PSPACE}$-hard}}% + \end{pgfpicture} +\end{frame} + +\begin{frame} + \frametitle{Candidates for Languages that\\ + Cannot be Accepted in an Overhead-Free Way} + + \begin{overprint} + \onslide<all:1> + \begin{block}{Conjecture} + \strut + $\Lang{double-palindromes} \notin \Class{DOF}$. + \end{block} + + \onslide<all:2> + \begin{alertblock}{Theorem\vphantom{j}} + \strut + $\Lang{double-palindromes} \in \Class{DOF}$. + \end{alertblock} + \end{overprint} + + \begin{block}{Conjecture} + $\Set{ww \mid w\in \Set{0,1}^*} \notin \Class{NOF}$. + \end{block} + + \vskip1em + \uncover<1>{Proving the first conjecture would show $\Class{DOF} \subsetneq + \Class{NOF}$.} +\end{frame} + + +\section*{Summary} + +\subsection<presentation>*{Summary} + +\begin{frame} + \frametitle<presentation>{Summary} + + \begin{block}{} + \begin{itemize} + \item + Overhead-free computation is a more faithful\\ + \alert{model of fixed-size memory}. + \item + Overhead-free computation is \alert{less powerful} than linear space. + \item + \alert{Many} context-free languages can be accepted\\ + by overhead-free machines. + \item + We conjecture that \alert{all} context-free languages are in + $\NOFpoly$. + \item + Our results can be seen as new results on the power of\\ + \alert{linear bounded automata with fixed alphabet} size. + \end{itemize} + \end{block} + + \note[item]{Point out result concerning all context-free languages.} + \note[item]{Relationship to restart automata.} +\end{frame} + + + +\subsection<presentation>*{Further Reading} + +\begin{frame} + \frametitle<presentation>{For Further Reading} + + \beamertemplatebookbibitems + + \begin{thebibliography}{10} + + \bibitem{sal:b:formal-languages} + A.~Salomaa. + \newblock {\em Formal Languages}. + \newblock Academic Press, 1973. + \pause + + \beamertemplatearticlebibitems + \bibitem{dij:j:smoothsort} + E.~Dijkstra. + \newblock Smoothsort, an alternative for sorting in situ. + \newblock {\em Science of Computer Programming}, 1(3):223--233, + 1982. + \pause + + \bibitem{FeldmanO1973} + E.~Feldman and J.~Owings, Jr. + \newblock A class of universal linear bounded automata. + \newblock {\em Information Sciences}, 6:187--190, 1973. + \pause + + \bibitem{JancarMPV1995} + P.~Jan{\v c}ar, F.~Mr{\'a}z, M.~Pl{\'a}tek, and J.~Vogel. + \newblock Restarting automata. + \newblock {\em FCT Conference 1995}, LNCS 985, pages + 282--292. 1995. + \end{thebibliography} +\end{frame} + + +% +% The following appendix material is not shown in the normal course of +% the presentation +% + +\appendix + +\AtBeginSubsection{} + + +\section{\appendixname} + +\frame{\frametitle{Appendix Outline}\tableofcontents} + + +\subsection{Complete Languages} + +\againframe<beamer| beamer:2>{pspacecomplete} + + +\subsection{Improvements for Context-Free Languages} + +\begin{frame} + \frametitle{Improvements} + + \begin{theorem} + \begin{enumerate} + \item + $\Class{DCFL} \subseteq \DOFpoly$. + \item + $\Class{CFL} \subseteq \NOFpoly$. + \end{enumerate} + \end{theorem} +\end{frame} + + +\subsection{Abbreviations} + +\begin{frame} + \frametitle{Explanation of Different Abbreviations} + + \begin{table} + \rowcolors[]{1}{structure!25!averagebackgroundcolor}{structure!10!averagebackgroundcolor} + \begin{tabular}{ll} + \structure{$\DOF$} & \structure{D}eterministic \structure{O}verhead-\structure{F}ree.\\ + \structure{$\NOF$} & \structure{N}ondeterministic \structure{O}verhead-\structure{F}ree.\\ + \structure{$\DOFpoly$} & \structure{D}eterministic + \structure{O}verhead-\structure{F}ree, \structure{poly}nomial time.\\ + \structure{$\DOFpoly$} & \structure{N}ondeterministic \structure{O}verhead-\structure{F}ree, \structure{poly}nomial time. + \end{tabular} + \caption{Explanation of what different abbreviations mean.} + \end{table} +\end{frame} + +\end{document} + + |