diff options
author | Karl Berry <karl@freefriends.org> | 2007-03-13 22:57:30 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2007-03-13 22:57:30 +0000 |
commit | 7528bed5b6dc85d8d97044a2ad1ea49a55b96a90 (patch) | |
tree | 60e6c5a19888dc3ac915c729eb139f4f86ec1151 /Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.tex | |
parent | 08117c08874292787f9823c3064dbb2acc9b8cf4 (diff) |
beamer 3.07 (12mar07)
git-svn-id: svn://tug.org/texlive/trunk@4030 c570f23f-e606-0410-a88d-b1316a301751
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, 0 insertions, 941 deletions
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.tex deleted file mode 100644 index eaa7e9b642c..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.tex +++ /dev/null @@ -1,941 +0,0 @@ -% $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} - - |