diff options
Diffstat (limited to 'Master/texmf-dist/doc/latex/beamer/examples')
50 files changed, 5475 insertions, 2322 deletions
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-conference-talk/beamerexample-conference-talk.pdf b/Master/texmf-dist/doc/latex/beamer/examples/a-conference-talk/beamerexample-conference-talk.pdf Binary files differnew file mode 100644 index 00000000000..449567937b9 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-conference-talk/beamerexample-conference-talk.pdf diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-conference-talk/beamerexample-conference-talk.tex b/Master/texmf-dist/doc/latex/beamer/examples/a-conference-talk/beamerexample-conference-talk.tex new file mode 100644 index 00000000000..f5faef720e9 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-conference-talk/beamerexample-conference-talk.tex @@ -0,0 +1,744 @@ +% Copyright 2007 by Till Tantau +% +% This file may be distributed and/or modified +% +% 1. under the LaTeX Project Public License and/or +% 2. under the GNU Public License. +% +% See the file doc/licenses/LICENSE for more details. + + + +\documentclass{beamer} + +% +% DO NOT USE THIS FILE AS A TEMPLATE FOR YOUR OWN TALKS¡!! +% +% Use a file in the directory solutions instead. +% They are much better suited. +% + + +% Setup appearance: + +\usetheme{Darmstadt} +\usefonttheme[onlylarge]{structurebold} +\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries} +\setbeamertemplate{navigation symbols}{} + + +% Standard packages + +\usepackage[english]{babel} +\usepackage[latin1]{inputenc} +\usepackage{times} +\usepackage[T1]{fontenc} + + +% Setup TikZ + +\usepackage{tikz} +\usetikzlibrary{arrows} +\tikzstyle{block}=[draw opacity=0.7,line width=1.4cm] + + +% Author, Title, etc. + +\title[Block Partitioning and Perfect Phylogenies] +{% + On the Complexity of SNP Block Partitioning Under the Perfect + Phylogeny Model% +} + +\author[Gramm, Hartman, Nierhoff, Sharan, Tantau] +{ + Jens~Gramm\inst{1} \and + Tzvika~Hartman\inst{2} \and + Till~Nierhoff\inst{3} \and + Roded~Sharan\inst{4} \and + \textcolor{green!50!black}{Till~Tantau}\inst{5} +} + +\institute[Tübingen and others] +{ + \inst{1}% + Universität Tübingen, Germany + \and + \vskip-2mm + \inst{2}% + Bar-Ilan University, Ramat-Gan, Israel + \and + \vskip-2mm + \inst{3}% + International Computer Science Institute, Berkeley, USA + \and + \vskip-2mm + \inst{4}% + Tel-Aviv University, Israel + \and + \vskip-2mm + \inst{5}% + Universität zu Lübeck, Germany +} + +\date[WABI 2006] +{Workshop on Algorithms in Bioinformatics, 2006} + + + +% The main document + +\begin{document} + +\begin{frame} + \titlepage +\end{frame} + +\begin{frame}{Outline} + \tableofcontents +\end{frame} + + +\section{Introduction} + +\subsection{The Model and the Problem} + +\begin{frame}{What is haplotyping and why is it important?} + You hopefully know this after the previous three talks\dots +\end{frame} + +\begin{frame}[t]{General formalization of haplotyping.} + \begin{block}{Inputs} + \begin{itemize} + \item A \alert{genotype matrix} $G$. + \item The \alert{rows} of the matrix are \alert{taxa / individuals}. + \item The \alert{columns} of the matrix are \alert{SNP sites / + characters}. + \end{itemize} + \end{block} + \begin{block}{Outputs} + \begin{itemize} + \item A \alert{haplotype matrix} $H$. + \item Pairs of rows in $H$ \alert{explain} the rows of $G$. + \item The haplotypes in $H$ are \alert{biologically plausible}. + \end{itemize} + \end{block} +\end{frame} + + +\begin{frame}[t]{Our formalization of haplotyping.} + \begin{block}{Inputs} + \begin{itemize} + \item A genotype matrix $G$. + \item The rows of the matrix are individuals / taxa. + \item The columns of the matrix are SNP sites / characters. + \item<alert@1-> + The problem is directed: one haplotype is known. + \item<alert@1-> + The input is biallelic: there are only two homozygous + states (0 and 1) and one heterozygous state (2). + \end{itemize} + \end{block} + \begin{block}{Outputs} + \begin{itemize} + \item A haplotype matrix $H$. + \item Pairs of rows in $H$ explain the rows of $G$. + \item<alert@1> The haplotypes in $H$ form a perfect phylogeny. + \end{itemize} + \end{block} +\end{frame} + + +\begin{frame}{We can do perfect phylogeny haplotyping efficiently, but + \dots} + \begin{enumerate} + \item \alert{Data may be missing.} + \begin{itemize} + \item This makes the problem NP-complete \dots + \item \dots even for very restricted cases. + \end{itemize} + \textcolor{green!50!black}{Solutions:} + \begin{itemize} + \item Additional assumption like the rich data hypothesis. + \end{itemize} + \item \alert{No perfect phylogeny is possible.} + \begin{itemize} + \item This can be caused by chromosomal crossing-over effects. + \item This can be caused by incorrect data. + \item This can be caused by multiple mutations at the same sites. + \end{itemize} + \textcolor{green!50!black}{Solutions:} + \begin{itemize} + \item Look for phylogenetic networks. + \item Correct data. + \item<alert@1-> + Find blocks where a perfect phylogeny is possible. + \end{itemize} + \end{enumerate} +\end{frame} + + +\subsection{The Integrated Approach} + +\begin{frame}{How blocks help in perfect phylogeny haplotyping.} + \begin{enumerate} + \item Partition the site set into overlapping contiguous blocks. + \item Compute a perfect phylogeny for each block and combine them. + \item Use dynamic programming for finding the partition. + \end{enumerate} + + \begin{tikzpicture} + \useasboundingbox (0,-1) rectangle (10,2); + + \draw[line width=2mm,dash pattern=on 1mm off 1mm] + (0,1) -- (9.99,1) node[midway,above] {Genotype matrix} + (0,0.6666) -- (9.99,0.6666) + (0,0.3333) -- (9.99,0.3333) + (0,0) -- (9.99,0) node[midway,below] {\only<1>{no perfect phylogeny}}; + + \begin{scope}[xshift=-.5mm] + \only<2-> + { + \draw[red,block] (0,.5) -- (3,.5) + node[midway,below] {perfect phylogeny}; + } + + \only<3-> + { + \draw[green!50!black,block] (2.5,.5) -- (7,.5) + node[pos=0.6,below] {perfect phylogeny}; + } + + \only<4-> + { + \draw[blue,block] (6.5,.5) -- (10,.5) + node[pos=0.6,below] {perfect phylogeny}; + } + \end{scope} + \end{tikzpicture} +\end{frame} + +\begin{frame}{Objective of the integrated approach.} + \begin{enumerate} + \item Partition the site set into \alert{noncontiguous} blocks. + \item Compute a perfect phylogeny for each block and combine them. + \item<alert@1-> Compute partition while computing perfect + phylogenies. + \end{enumerate} + + \begin{tikzpicture} + \useasboundingbox (0,-1) rectangle (10,2); + + \draw[line width=2mm,dash pattern=on 1mm off 1mm] + (0,1) -- (9.99,1) node[midway,above] {Genotype matrix} + (0,0.6666) -- (9.99,0.6666) + (0,0.3333) -- (9.99,0.3333) + (0,0) -- (9.99,0) node[midway,below] {\only<1>{no perfect phylogeny}}; + + \only<2-> + { + \begin{scope}[xshift=-0.5mm] + \draw[red,block] (0,.5) -- (3,.5) + node[midway,below] {perfect phylogeny} + (8,.5) -- (9,.5); + + \draw[green!50!black,block] + (3,.5) -- (6,.5) + node[pos=0.6,below] {perfect phylogeny} + (6.4,.5) -- (8,.5) + (9,.5) -- (10,.5); + + \draw[blue,block] (6,.5) -- (6.4,.5) + node[midway,below=5mm] {perfect phylogeny}; + \end{scope} + } + \end{tikzpicture} +\end{frame} + + +\begin{frame}{The formal computational problem.} + We are interested in the computational complexity of \\ + \alert{the function \alert{$\chi_{\operatorname{PP}}$}}: + \begin{itemize} + \item It gets genotype matrices as input. + \item It maps them to a number $k$. + \item This number is minimal such that the sites can be + covered by $k$ sets, each admitting a perfect phylogeny. + \\ + (We call this a \alert{pp-partition}.) + \end{itemize} +\end{frame} + + +\section{Bad News: Hardness Results} + +\subsection{Hardness of PP-Partitioning of Haplotype Matrices} + +\begin{frame}{Finding pp-partitions of haplotype matrices.} + We start with a special case: + \begin{itemize} + \item The inputs $M$ are \alert{already haplotype matrices}. + \item The inputs $M$ \alert{do not allow a perfect phylogeny}. + \item What is $\chi_{\operatorname{PP}}(M)$? + \end{itemize} + \begin{example} + \begin{columns} + \column{.3\textwidth} + $M\colon$ + \footnotesize + \begin{tabular}{cccc} + 0 & 0 & 0 & 1 \\ + 0 & 1 & 0 & 0 \\ + 1 & 0 & 0 & 0 \\ + 0 & 1 & 0 & 0 \\ + 1 & 0 & 0 & 0 \\ + 0 & 1 & 0 & 1 \\ + 1 & 1 & 0 & 0 \\ + 0 & 0 & 1 & 0 \\ + 1 & 0 & 1 & 0 + \end{tabular}% + \only<2> + {% + \begin{tikzpicture} + \useasboundingbox (2.9,0); + + \draw [red, opacity=0.7,line width=1cm] (1.7 ,1.9) -- (1.7 ,-1.7); + \draw [blue,opacity=0.7,line width=5mm] (0.85,1.9) -- (0.85,-1.7) + (2.55,1.9) -- (2.55,-1.7); + \end{tikzpicture} + } + \column{.6\textwidth} + \begin{overprint} + \onslide<1> + No perfect phylogeny is possible. + + \onslide<2> + \textcolor{blue!70!bg}{Perfect phylogeny} + + \textcolor{red!70!bg}{Perfect phylogeny} + + $\chi_{\operatorname{PP}}(M) = 2$. + + \end{overprint} + \end{columns} + \end{example} +\end{frame} + +\begin{frame}{Bad news about pp-partitions of haplotype matrices.} + \begin{theorem} + Finding \alert{optimal pp-partition of haplotype matrices}\\ + is equivalent to finding \alert{optimal graph colorings}. + \end{theorem} + + \begin{proof}[Proof sketch for first direction] + \begin{enumerate} + \item Let $G$ be a graph. + \item Build a matrix with a column for each vertex of $G$. + \item For each edge of $G$ add four rows inducing\\the + submatrix $\left( + \begin{smallmatrix} + 0 & 0 \\ + 0 & 1 \\ + 1 & 0 \\ + 1 & 1 + \end{smallmatrix}\right)$. + \item The submatrix enforces that the columns lie in different + perfect phylogenies. \qedhere + \end{enumerate} + \end{proof} +\end{frame} + +\begin{frame}{Implications for pp-partitions of haplotype matrices.} + \begin{corollary} + If $\chi_{\operatorname{PP}}(M) = 2$ for a haplotype matrix $M$, + we can find an optimal pp-partition in polynomial time. + \end{corollary} + + \begin{corollary} + Computing $\chi_{\operatorname{PP}}$ for haplotype matrices is + \begin{itemize} + \item $\operatorname{NP}$-hard, + \item not fixed-parameter tractable, unless + $\operatorname{P}=\operatorname{NP}$, + \item very hard to approximate. + \end{itemize} + \end{corollary} +\end{frame} + + +\subsection{Hardness of PP-Partitioning of Genotype Matrices} + + +\begin{frame}{Finding pp-partitions of genotype matrices.} + Now comes the general case: + \begin{itemize} + \item The inputs $M$ are \alert{genotype matrices}. + \item The inputs $M$ \alert{do not allow a perfect phylogeny}. + \item What is $\chi_{\operatorname{PP}}(M)$? + \end{itemize} + \begin{example} + \begin{columns} + \column{.3\textwidth} + $M\colon$ + \footnotesize + \begin{tabular}{cccc} + 2 & 2 & 2 & 2 \\ + 1 & 0 & 0 & 0 \\ + 0 & 0 & 0 & 1 \\ + 0 & 0 & 1 & 0 \\ + 0 & 2 & 2 & 0 \\ + 1 & 1 & 0 & 0 + \end{tabular}% + \only<2> + {% + \begin{tikzpicture} + \useasboundingbox (2.9,0); + + \draw [red, opacity=0.7,line width=1cm] (1.7 ,1.3) -- (1.7 ,-1.1); + \draw [blue,opacity=0.7,line width=5mm] (0.85,1.3) -- (0.85,-1.1) + (2.55,1.3) -- (2.55,-1.1); + \end{tikzpicture} + } + \column{.6\textwidth} + \begin{overprint} + \onslide<1> + No perfect phylogeny is possible. + + \onslide<2> + \textcolor{blue!70!bg}{Perfect phylogeny} + + \textcolor{red!70!bg}{Perfect phylogeny} + + $\chi_{\operatorname{PP}}(M) = 2$. + + \end{overprint} + \end{columns} + \end{example} +\end{frame} + + +\begin{frame}{Bad news about pp-partitions of haplotype matrices.} + \begin{theorem} + Finding \alert{optimal pp-partition of genotype matrices} + is at least as hard as finding \alert{optimal colorings of + 3-uniform hypergraphs}. + \end{theorem} + + \begin{proof}[Proof sketch] + \begin{enumerate} + \item Let $G$ be a 3-uniform hypergraph. + \item Build a matrix with a column for each vertex of $G$. + \item For each hyperedge of $G$ add four rows inducing\\ the submatrix + $\left( + \begin{smallmatrix} + 2 & 2 & 2 \\ + 1 & 0 & 0 \\ + 0 & 1 & 0 \\ + 0 & 0 & 1 + \end{smallmatrix}\right) + $. + \item The submatrix enforces that the three columns do not all lie + in the same perfect phylogeny. \qedhere + \end{enumerate} + \end{proof} +\end{frame} + +\begin{frame}{Implications for pp-partitions of genotype matrices.} + \begin{corollary} + Even if we know $\chi_{\operatorname{PP}}(M) = 2$ for a genotype matrix $M$,\\ + finding a pp-partition of any fixed size is still + \begin{itemize} + \item $\operatorname{NP}$-hard, + \item not fixed-parameter tractable, unless + $\operatorname{P}=\operatorname{NP}$, + \item very hard to approximate. + \end{itemize} + \end{corollary} +\end{frame} + + +\section{Good News: Tractability Results} + +\subsection{Perfect Path Phylogenies} + +\begin{frame}{Automatic optimal pp-partitioning is hopeless, but\dots} + \begin{itemize} + \item The hardness results are \alert{worst-case} results for\\ + \alert{highly artificial inputs}. + \item \alert{Real biological data} might have special properties + that make the problem \alert{tractable}. + \item One such property is that perfect phylogenies are often + perfect \alert{path} phylogenies: + + In HapMap data, in 70\% of the blocks where a perfect phylogeny + is possible a perfect path phylogeny is also possible. + \end{itemize} +\end{frame} + + +\begin{frame}{Example of a perfect path phylogeny.} + \begin{columns}[t] + \column{.3\textwidth} + \begin{exampleblock}{Genotype matrix} + $G\colon$ + \begin{tabular}{ccc} + A & B & C \\\hline + 2 & 2 & 2 \\ + 0 & 2 & 0 \\ + 2 & 0 & 0 \\ + 0 & 2 & 2 + \end{tabular} + \end{exampleblock} + + \column{.3\textwidth} + \begin{exampleblock}{Haplotype matrix} + $H\colon$ + \begin{tabular}{ccc} + A & B & C \\\hline + 1 & 0 & 0 \\ + 0 & 1 & 1 \\ + 0 & 0 & 0 \\ + 0 & 1 & 0 \\ + 0 & 0 & 0 \\ + 1 & 0 & 0 \\ + 0 & 0 & 0 \\ + 0 & 1 & 1 + \end{tabular} + \end{exampleblock} + + \column{.4\textwidth} + \begin{exampleblock}{Perfect path phylogeny} + \begin{center} + \begin{tikzpicture}[auto,thick] + \tikzstyle{node}=% + [% + minimum size=10pt,% + inner sep=0pt,% + outer sep=0pt,% + ball color=example text.fg,% + circle% + ] + + \node [node] {} [->] + child {node [node] {} edge from parent node[swap]{A}} + child {node [node] {} + child {node [node] {} edge from parent node{C}} + edge from parent node{B} + }; + \end{tikzpicture} + \end{center} + \end{exampleblock} + \end{columns} +\end{frame} + + +\begin{frame}{The modified formal computational problem.} + We are interested in the computational complexity of \\ + the function $\chi_{\alert{\operatorname{PPP}}}$: + \begin{itemize} + \item It gets genotype matrices as input. + \item It maps them to a number $k$. + \item This number is minimal such that the sites can be + covered by $k$ sets, each admitting a perfect \alert{path} phylogeny. + \\ + (We call this a ppp-partition.) + \end{itemize} +\end{frame} + + + +\subsection{Tractability of PPP-Partitioning of Genotype Matrices} + +\begin{frame}{Good news about ppp-partitions of genotype matrices.} + \begin{theorem} + \alert{Optimal ppp-partitions of genotype matrices} can be + computed in \alert{polynomial time}. + \end{theorem} + \begin{block}{Algorithm} + \begin{enumerate} + \item Build the following partial order: + \begin{itemize} + \item Can one column be above the other in a phylogeny? + \item Can the columns be the two children of the root of a + perfect path phylogeny? + \end{itemize} + \item Cover the partial order with as few compatible chain pairs + as possible. + + For this, a maximal matching in a special graph needs to be + computed. + \end{enumerate} + \end{block} + \hyperlink{algorithm<1>}{\beamergotobutton{The algorithm in action}} + \hypertarget{return}{} +\end{frame} + +\section*{Summary} + +\begin{frame} + \frametitle<presentation>{Summary} + + \begin{itemize} + \item + Finding optimal pp-partitions is \alert{intractable}. + \item + It is even intractable to find a pp-partition when \alert{just two + noncontiguous blocks are known to suffice}. + \item + For perfect \alert{path} phylogenies, optimal partitions can be + computed \alert{in polynomial time}. + \end{itemize} +\end{frame} + + +\appendix + +\section*{Appendix} + +\begin{frame}[label=algorithm]{The algorithm in action.}{Computation of + the partial order.} + \begin{columns}[t] + \column{.4\textwidth} + \begin{exampleblock}{Genotype matrix} + $G\colon$ + \begin{tabular}{ccccc} + A & B & C & D & E \\\hline + 2 & 2 & 2 & 2 & 2 \\ + 0 & 1 & 2 & 1 & 0 \\ + 1 & 0 & 0 & 1 & 2 \\ + 0 & 2 & 2 & 0 & 0 + \end{tabular} + \end{exampleblock} + \column{.6\textwidth} + \begin{exampleblock}{Partial order} + \begin{tikzpicture}[node distance=15mm] + \tikzstyle{every node}= + [% + fill=green!50!black!20,% + draw=green!50!black,% + minimum size=7mm,% + circle,% + thick% + ] + + \node (A) {A}; + \node (B) [right of=A] {B}; + \node (C) [below of=B] {C}; + \node (D) [above of=A] {D}; + \node (E) [below of=A] {E}; + + \path [thick,shorten >=1pt,-stealth'] (A) edge (E) + (B) edge (C) + (D) edge (A) + edge[bend right] (E); + + \uncover<2>{ + \path [-,blue,thick](A) edge (B) + edge (C) + (B) edge (E) + (C) edge (E);} + \end{tikzpicture} + + Partial order: \tikz[baseline] \draw[thick,-stealth'] (0pt,.5ex) + -- (5mm,.5ex); + + \uncover<2>{\textcolor{blue}{Compatible as children of root: + \tikz[baseline] \draw[thick] (0pt,.5ex) -- (5mm,.5ex);}} + \end{exampleblock} + \end{columns} +\end{frame} + +\begin{frame}{The algorithm in action.}{The matching in the special graph.} + \begin{columns}[t] + \column{.3\textwidth} + \begin{exampleblock}{Partial order} + \begin{tikzpicture}[node distance=15mm] + \tikzstyle{every node}=% + [% + fill=green!50!black!20,% + draw=green!50!black,% + minimum size=8mm,% + circle,% + thick% + ] + + \node (A) {$A$}; + \node (B) [right of=A] {$B$}; + \node (C) [below of=B] {$C$}; + \node (D) [above of=A] {$D$}; + \node (E) [below of=A] {$E$}; + + \path [thick,shorten >=1pt,-stealth'] (A) edge (E) + (B) edge (C) + (D) edge (A) + edge[bend right] (E); + + \path [-,blue,thick](A) edge (B) + edge (C) + (B) edge (E) + (C) edge (E); + + \only<3-> + { + \path[very thick,shorten >=1pt,-stealth',red] (D) edge (A) (B) edge (C); + \path [-,red,very thick](E) edge (B); + } + \end{tikzpicture} + \end{exampleblock} + \column{.7\textwidth} + \begin{exampleblock}{Matching graph} + \begin{tikzpicture}[node distance=15mm] + \tikzstyle{every node}=% + [% + fill=green!50!black!20,% + draw=green!50!black,% + minimum size=8mm,% + circle,% + thick,% + inner sep=0pt% + ] + + \node (A) {$A$}; + \node (B) [right of=A] {$B$}; + \node (C) [below of=B] {$C$}; + \node (D) [above of=A] {$D$}; + \node (E) [below of=A] {$E$}; + + \begin{scope}[xshift=4.75cm] + \node (A') {$A'$}; + \node (B') [right of=A'] {$B'$}; + \node (C') [below of=B'] {$C'$}; + \node (D') [above of=A'] {$D'$}; + \node (E') [below of=A'] {$E'$}; + \end{scope} + + \path [thick] (A) edge (E') + (B) edge (C') + (D) edge (A') + edge (E'); + + \path [blue,thick](A') edge (B') + edge (C') + (B') edge (E') + (C') edge (E'); + + \only<2-> + { + \path[very thick,red] (D) edge (A') + (B) edge (C') + (B') edge (E'); + } + \end{tikzpicture} + \end{exampleblock} + \end{columns} + + \medskip + \uncover<2->{A \alert{maximal matching} in the matching graph + \uncover<3>{induces\\ \alert{perfect path phylogenies}.}} + + \hfill\hyperlink{return}{\beamerreturnbutton{Return}} +\end{frame} + +\end{document} + + diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic1.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic1.jpg Binary files differnew file mode 100644 index 00000000000..cc27292132f --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic1.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic2.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic2.jpg Binary files differnew file mode 100644 index 00000000000..cc27292132f --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic2.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic3.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic3.jpg Binary files differnew file mode 100644 index 00000000000..cc27292132f --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic3.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic4.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic4.jpg Binary files differnew file mode 100644 index 00000000000..cc27292132f --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic4.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic5.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic5.jpg Binary files differnew file mode 100644 index 00000000000..cc27292132f --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic5.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic6.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic6.jpg Binary files differnew file mode 100644 index 00000000000..cc27292132f --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/._beamerexample-lecture-pic6.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-beamer-version.pdf b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-beamer-version.pdf Binary files differnew file mode 100644 index 00000000000..2dade4ae2d7 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-beamer-version.pdf diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-beamer-version.tex b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-beamer-version.tex new file mode 100644 index 00000000000..dbda07c3ab7 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-beamer-version.tex @@ -0,0 +1,13 @@ +% Copyright 2007 by Till Tantau +% +% This file may be distributed and/or modified +% +% 1. under the LaTeX Project Public License and/or +% 2. under the GNU Public License. +% +% See the file doc/licenses/LICENSE for more details. + +\documentclass[german,10pt]{beamer} + +\input{beamerexample-lecture-style.tex} +\input{beamerexample-lecture-body.tex} diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-beamer-version.tex~ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-beamer-version.tex~ new file mode 100644 index 00000000000..8d24a941e04 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-beamer-version.tex~ @@ -0,0 +1,4 @@ +\documentclass[german,10pt]{beamer} + +\input{beamerexample-lecture-style.tex} +\input{beamerexample-lecture-body.tex} diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-body.tex b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-body.tex new file mode 100644 index 00000000000..5d472951be4 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-body.tex @@ -0,0 +1,587 @@ +% Copyright 2007 by Till Tantau +% +% This file may be distributed and/or modified +% +% 1. under the LaTeX Project Public License and/or +% 2. under the GNU Public License. +% +% See the file doc/licenses/LICENSE for more details. + +% +% DO NOT USE THIS FILE AS A TEMPLATE FOR YOUR OWN TALKS¡!! +% +% Use a file in the directory solutions instead. +% They are much better suited. +% + + +\lecture[1]{Syntax versus Semantik}{lecture-text} + +\subtitle{Text und seine Bedeutung} + +\date{27. Oktober 2006} + + +\begin{document} + +\begin{frame} + \maketitle +\end{frame} + + +\section*{Ziele und Inhalt} + +\begin{frame}{Die Lernziele der heutigen Vorlesung und der Übungen.} + \begin{enumerate} + \item Die Begriffe Syntax und Semantik erklären können + \item Syntaktische und semantische Elemente natürlicher Sprachen und + von Programmiersprachen benennen können + \item Die Begriffe Alphabet und Wort kennen + \item Objekte als Worte kodieren können + \end{enumerate} +\end{frame} + +\begin{frame}\frametitle<presentation>{Gliederung} + \tableofcontents +\end{frame} + + +\section{Was ist Syntax?} + +\begin{frame}{Die zwei Hauptbegriffe der heutigen Vorlesung.} + \begin{block}{Grobe Definition (Syntax)} + Unter einer \alert{Syntax} verstehen wir \alert{Regeln}, nach denen + Texte \alert{strukturiert} werden dürfen. + \end{block} + \begin{block}{Grobe Definition (Semantik)} + Unter einer \alert{Semantik} verstehen wir die Zuordnung von + \alert{Bedeutung} zu Text. + \end{block} +\end{frame} + + +\subsection[Syntax \protect\\ natürlicher Sprachen]{Syntax natürlicher Sprachen} + +\begin{frame}{Beobachtungen zu einem ägyptischen Text.} + \includegraphicscopyright[width=6cm]{beamerexample-lecture-pic3.jpg} + {Copyright by Guillaume Blanchard, GNU Free Documentation License, Low Resultion} + + \begin{block}{Beobachtungen} + \begin{itemize} + \item Wir haben keine Ahnung, was der Text bedeutet. + \item Es gibt aber \alert{Regeln}, die offenbar eingehalten wurden, + wie »Hieroglyphen stehen in Zeilen«. + \item Solche Regeln sind \alert{syntaktische Regeln} -- man kann sie + überprüfen, ohne den Inhalt zu verstehen. + \end{itemize} + \end{block} +\end{frame} + + +\begin{frame}{Beobachtungen zu einem kyrillischen Text.} + + \includegraphicscopyright[width=6.75cm]{beamerexample-lecture-pic4.jpg} + {Copyright by Cristian Chirita, GNU Free Documentation License, Low Resultion} + + \begin{block}{Beobachtungen} + \begin{itemize} + \item Wir haben keine Ahnung, was der Text bedeutet. + \item Es gibt aber \alert{Regeln}, die offenbar eingehalten wurden. + \item Wir kennen mehr Regeln als bei den Hieroglyphen. + \end{itemize} + \end{block} + + \begin{block}{Zur Diskussion} + Welche syntaktischen Regeln fallen Ihnen ein, die bei dem Text + eingehalten wurden? + \end{block} +\end{frame} + + + +\begin{frame}{Beobachtungen zu einem deutschen Text.} + \begin{quotation} + Informatiker lieben Logiker. + \end{quotation} + + \bigskip + \begin{block}{Beobachtungen} + \begin{itemize} + \item Auch hier werden viele syntaktische Regeln eingehalten. + \item Es fällt uns aber \alert{schwerer}, diese zu erkennen. + \item Der Grund ist, dass wir \alert{sofort über die Bedeutung + nachdenken}. + \end{itemize} + \end{block} +\end{frame} + +\begin{frame}{Zur Syntax von natürlichen Sprachen.} + \begin{itemize} + \item + Die \alert{Syntax} einer natürlichen Sprache ist die Menge an + \alert{Regeln}, nach denen Sätze gebildet werden dürfen. + \item + Die \alert{Bedeutung} oder der \alert{Sinn} der gebildeten Sätze + ist dabei unerheblich. + \item + Jede Sprache hat ihre eigene Syntax; die Syntax verschiedener + Sprachen ähneln sich aber oft. + \item + Es ist nicht immer klar, ob eine Regel noch zur Syntax gehört + oder ob es schon um den Sinn geht. + + \ExampleInline{Substantive werden groß geschrieben.} + \end{itemize} +\end{frame} + +\subsection{Syntax von Programmiersprachen} + +\begin{frame}[fragile]{Beobachtungen zu einem Programmtext.} + +\begin{verbatim} +\def\pgfpointadd#1#2{% + \pgf@process{#1}% + \pgf@xa=\pgf@x% + \pgf@ya=\pgf@y% + \pgf@process{#2}% + \advance\pgf@x by\pgf@xa% + \advance\pgf@y by\pgf@ya} +\end{verbatim} + \begin{block}{Beobachtungen} + \begin{itemize} + \item Der Programmtext sieht sehr kryptisch aus. + \item Trotzdem gibt es offenbar wieder Regeln. + \item So scheint einem Doppelkreuz eine Ziffer zu folgen und + Zeilen muss man offenbar mit Prozentzeichen beenden. + \end{itemize} + \end{block} +\end{frame} + + +\begin{frame}[fragile]{Beobachtungen zu einem weiteren Programmtext.} + +\begin{verbatim} +for (int i = 0; i < 100; i++) + a[i] = a[i]; +\end{verbatim} + \begin{block}{Beobachtungen} + \begin{itemize} + \item Wieder gibt es Regeln, die eingehalten werden. + \item Wieder fällt es uns \alert{schwerer}, diese zu erkennen, da + wir \alert{sofort über den Sinn nachdenken}. + \end{itemize} + \end{block} +\end{frame} + + +\begin{frame}{Zur Syntax von Programmiersprachen} + \begin{itemize} + \item Die \alert{Syntax} einer Programmiersprache ist die + \alert{Menge von Regeln}, nach der Programmtexte gebildet werden + dürfen. + \item Die \alert{Bedeutung} oder der \alert{Sinn} der Programmtexte + ist dabei egal. + \item + Jede Programmiersprache hat ihre eigene Syntax; die Syntax + verschiedener Sprachen ähneln sich aber oft. + \end{itemize} +\end{frame} + +\begin{frame}{5-Minuten-Aufgabe} + Welche der folgenden Regeln sind Syntax-Regeln? + \begin{enumerate} + \item Bezeichner dürfen nicht mit einer Ziffer anfangen. + \item Programme müssen in endlicher Zeit ein Ergebnis produzieren. + \item Öffnende und schließende geschweifte Klammern müssen + »balanciert« sein. + \item Methoden von Null-Objekten dürfen nicht aufgerufen werden. + \item Variablen müssen vor ihrer ersten Benutzung deklariert werden. + \end{enumerate} +\end{frame} + + +\subsection[Syntax\protect\\ logischer Sprachen]{Syntax logischer Sprachen} + +\begin{frame}{Beobachtungen zu einer logischen Formel.} + \begin{quotation} + $p \to q \land \neg q$ + \end{quotation} + + \bigskip + \begin{block}{Beobachtungen} + \begin{itemize} + \item Auch logische Formeln haben eine syntaktische Struktur. + \item So wäre es \alert{syntaktisch falsch}, statt einem Pfeil zwei + Pfeile zu benutzen. + \item Es wäre aber \alert{syntaktisch richtig}, statt einem + Negationszeichen zwei Negationszeichen zu verwenden. + \end{itemize} + \end{block} +\end{frame} + +\begin{frame}{Zur Syntax von logischen Sprachen} + \begin{itemize} + \item Die \alert{Syntax} einer logischen Sprache ist die + \alert{Menge von Regeln}, nach der Formeln gebildet werden + dürfen. + \item Die \alert{Bedeutung} oder der \alert{Sinn} der Formeln + ist dabei egal. + \item + Jede logische Sprache hat ihre eigene Syntax; die Syntax + verschiedener Sprachen ähneln sich aber oft. + \end{itemize} +\end{frame} + + + +\section{Was ist Semantik?} + +\subsection[Semantik\protect\\ natürlicher Sprachen]{Semantik natürlicher Sprachen} + +\begin{frame}{Was bedeutet ein Satz?} + + \begin{quotation} + Der Hörsaal ist groß. + \end{quotation} + + \bigskip + \begin{itemize} + \item Dieser Satz hat eine \alert{Bedeutung}. + \item Eine \alert{Semantik} legt solche Bedeutungen fest. + \item Syntaktisch falschen Sätzen wird im Allgemeinen keine + Bedeutung zugewiesen. + \end{itemize} +\end{frame} + +\begin{frame}{Ein Satz, zwei Bedeutungen.} + \begin{quotation} + Steter Tropfen höhlt den Stein. + \end{quotation} + + \bigskip + \begin{itemize} + \item Ein Satz kann \alert{mehrere Bedeutungen haben}, welche durch + \alert{unterschiedliche Semantiken} gegeben sind. + \item In der \alert{wortwörtlichen Semantik} sagt der Satz aus, dass + Steine ausgehöhlte werden, wenn man jahrelang Wasser auf + sie tropft. + \item In der \alert{übertragenen Semantik} sagt der Satz aus, dass + sich Beharrlichkeit auszahlt. + \end{itemize} +\end{frame} + +\begin{frame}{Die Semantik der Hieroglyphen} + \includegraphicscopyright[height=8cm]{beamerexample-lecture-pic5.jpg} + {Unknown Author, Public Domain, Low Resolution} +\end{frame} + + +\subsection{Semantik von Programmiersprachen} + +\begin{frame}[fragile]{Was bedeutet ein Programm?} +\begin{verbatim} +for (int i = 0; i < 100; i++) + a[i] = a[i]; +\end{verbatim} + \begin{itemize} + \item Auch dieser Programmtext »bedeutet etwas«, wir »meinen etwas« + mit diesem Text. + \item Die \alert{Semantik der Programmiersprache} legt fest, + was mit dem Programmtext gemeint ist. + \end{itemize} +\end{frame} + +\begin{frame}[fragile]{Ein Programm, zwei Bedeutungen.} +\begin{verbatim} +for (int i = 0; i < 100; i++) + a[i] = a[i]; +\end{verbatim} + \begin{itemize} + \item Ein Programmtext kann \alert{mehrere Bedeutungen haben}, + welche durch \alert{unterschiedliche Semantiken} gegeben sind. + \item In der \alert{operationalen Semantik} bedeutet der + Programmtext, dass die ersten einhundert Elemente eines Arrays + \verb!a! nacheinander ihren eigenen Wert zugewiesen bekommen. + \item In der \alert{denotationellen Semantik} bedeutet der + Programmtext, dass nichts passiert. + \end{itemize} +\end{frame} + + +\subsection[Semantik\protect\\ logischer Sprachen]{Semantik logischer Sprachen} + + + + +\section{Grundlage der Syntax: Text} + +\begin{frame}{Eine mathematische Sicht auf Text.} + \begin{itemize} + \item Viele (aber nicht alle!) syntaktische Systeme bauen auf + \alert{Text} auf. + \item Auch solche Systeme, die nicht auf Text aufbauen, lassen sich + trotzdem durch Text beschreiben. + \item Es ist deshalb nützlich, auf Text \text{Methoden der + Mathematik} anwenden zu können. + \item Im Folgenden wird deshalb die \alert{mathematische Sicht} auf + Text eingeführt, die \alert{in der gesamten Theoretischen + Informatik} genutzt wird. + \end{itemize} +\end{frame} + + +\subsection{Alphabete} + +\begin{frame}{Formale Alphabete} + \begin{definition}[Alphabet] + Ein \alert{Alphabet} ist eine nicht-leere, endliche Menge von + \alert{Symbolen} (auch \alert{Buchstaben} genannt). + \end{definition} + + \begin{itemize} + \item Alphabete werden häufig mit griechischen Großbuchstaben + bezeichnet, also $\Gamma$ oder~$\Sigma$. Manchmal auch mit + lateinischen Großbuchstaben, also $N$ oder~$T$. + \item Ein Symbol oder »Buchstabe« kann auch ein komplexes oder + komisches »Ding« sein wie ein Pointer oder ein Leerzeichen. + \end{itemize} + + \begin{examples} + \begin{itemize} + \item Die Groß- und Kleinbuchstaben + \item Die Menge $\{0,1\}$ (bei Informatikern beliebt) + \item Die Menge $\{A,C,G,T\}$ (bei Biologen beliebt) + \item Die Zeichenmenge des UNICODE. + \end{itemize} + \end{examples} +\end{frame} + + +\subsection{Worte} + + +\begin{frame}{Formale Worte} + \begin{definition}[Wort] + Ein \alert{Wort} ist eine (endliche) Folge von Symbolen. + \end{definition} + \begin{itemize} + \item »Worte« sind im Prinzip dasselbe wie + Strings. Insbesondere können in Worten Leerzeichen als Symbole + auftauchen. + \item Die Menge aller Worte über einem Alphabet $\Sigma$ hat einen + besonderen Namen: $\Sigma^*$. + \item + Deshalb schreibt man oft: »Sei $w \in \Sigma^*$, \dots« + \item Es gibt auch ein \alert{leeres Wort}, abgekürzt + $\epsilon$ oder $\lambda$, das dem String + \texttt{\char`\"\char`\"} entspricht. + \end{itemize} + + \begin{examples} + \begin{itemize} + \item \texttt{Hallo} + \item \texttt{TATAAAATATTA} + \item $\epsilon$ + \item \texttt{Hallo Welt.} + \end{itemize} + \end{examples} +\end{frame} + + +\begin{frame}{5-Minuten-Aufgabe} + Die folgenden Aufgaben sind nach Schwierigkeit sortiert. Lösen Sie + \alert{eine} der Aufgaben. + \begin{enumerate} + \item + Schreiben Sie alle Worte der Länge höchstens $2$ über dem Alphabet + $\Sigma = \{0,1,*\}$ auf. + \item + Wie viele Worte der Länge $n$ über dem Alphabet $\Sigma = + \{0,1,*\}$ gibt es? + \item + Wie viele Worte der Länge höchstens $n$ über einem Alphabet mit + $q$ Buchstaben gibt es? + \end{enumerate} +\end{frame} + + +\subsection{Sprachen} + +\begin{frame}{Formale Sprachen}{Definition} + \begin{itemize} + \item Natürlichen Sprachen sind komplexe Dinge, bestehend aus + Wörtern, ihrer Ausprache, einer Grammatik, Ausnahmen, Dialekten, + und vielem mehr. + \item Bei \alert{formalen Sprachen} vereinfacht man radikal. + \item Formale Sprachen müssen weder sinnvoll noch interessant sein. + \end{itemize} + + \begin{definition}[Formale Sprache] + Eine \alert{formale Sprache} ist eine (oft unendliche!) Menge von + Worten für ein festes Alphabet. + \end{definition} + + \begin{itemize} + \item Statt \frqq formale Sprache\flqq\ sagt man einfach \frqq Sprache\flqq. + \item Als Menge von Worten ist eine Sprache eine Teilmenge von + $\Sigma^*$. + \item + Deshalb schreibt man oft: \frqq Sei $L \subseteq \Sigma^*$, + \dots\flqq + \end{itemize} +\end{frame} + +\begin{frame}{Formale Sprachen}{Einfache Beispiele} + \begin{examples} + \begin{itemize} + \item Die Menge $\{AAA, AAC, AAT\}$ (endliche Sprache). + \item Die Menge aller Java-Programmtexte (unendliche Sprache). + \item Die Menge aller Basensequenzen, die \texttt{TATA} enthalten + (unendliche Sprache). + \end{itemize} + \end{examples} +\end{frame} + +\begin{frame}{Formale Sprachen in der Medieninformatik} + \begin{itemize} + \item Ein Renderer produziert 3D-Bilder. + \item Dazu erhält er eine \alert{Szenerie} als Eingabe. + \item Diese Szenerie ist als \alert{Text}, also als ein \alert{Wort} gegeben. + \item Eine \alert{Syntax} beschreibt die (formale) Sprache, die alle + \alert{syntaktisch korrekten Szenerien} enthält. + \item Eine \alert{Semantik} beschreibt, was diese Beschreibungen bedeuten. + \end{itemize} +\end{frame} + +\begin{frame}[fragile]{Formale Sprachen in der Medieninformatik}{Das + »Wort«, das eine Szenerie beschreibt\dots} +\only<presentation>{\scriptsize} +\begin{verbatim*} +global_settings { assumed_gamma 1.0 } + +camera { + location <10.0, 10, -10.0> + direction 1.5*z + right x*image_width/image_height + look_at <0.0, 0.0, 0.0> +} + +sky_sphere { pigment { color rgb <0.6,0.7,1.0> } } + +light_source { + <0, 0, 0> // light's position (translated below) + color rgb <1, 1, 1> // light's color + translate <-30, 30, -30> + shadowless +} + +#declare i = 0; +#declare Steps = 30; +#declare Kugel = sphere{<0,0,0>,0.5 pigment{color rgb<1,0,0>}}; + +#while(i<Steps) + object{Kugel translate<3,0,0> rotate <0,i * 360 / Steps, 0> } + #declare i = i + 1; +#end +\end{verbatim*} +\end{frame} + + +\begin{frame}{Formale Sprachen in der Medieninformatik}{\dots\ und was es bedeutet.} + \includegraphicscopyright[width=9.5cm]{beamerexample-lecture-pic2.jpg} + {Copyright Matthias Kabel, GNU Free Documentation License, Low Resolution} +\end{frame} + +\begin{frame}{Formale Sprachen in der Medieninformatik}{Komplexeres Beispielbild, das ein Renderer produziert.} + \includegraphicscopyright[width=9.5cm]{beamerexample-lecture-pic1.jpg} + {Copyright Giorgio Krenkel and Alex Sandri, GNU Free Documentation License, Low Resolution} +\end{frame} + + +\begin{frame}{Formale Sprachen in der Bioinformatik} + \begin{itemize} + \item In der Bioinformatik untersucht man unter anderem Proteine. + \item Dazu erhält man \alert{Molekülbeschreibungen} als Eingabe. + \item Eine solche ist auch ein \alert{Wort}. + \item Eine \alert{Syntax} beschreibt die (formale) Sprache, die alle + \alert{syntaktisch korrekten Molkülbeschreibungen} enthält. + \item Eine \alert{Semantik} beschreibt, was diese Beschreibungen bedeuten. + \end{itemize} +\end{frame} + + +\begin{frame}[fragile]{Formale Sprachen in der Bioinformatik} + {Das »Wort«, das ein Protein beschreibt\dots} +\only<presentation>{\tiny} +\only<article>{\footnotesize} +\begin{verbatim} +HEADER HYDROLASE 25-JUL-03 1UJ1 +TITLE CRYSTAL STRUCTURE OF SARS CORONAVIRUS MAIN PROTEINASE +TITLE 2 (3CLPRO) +COMPND MOL_ID: 1; +COMPND 2 MOLECULE: 3C-LIKE PROTEINASE; +COMPND 3 CHAIN: A, B; +COMPND 4 SYNONYM: MAIN PROTEINASE, 3CLPRO; +COMPND 5 EC: 3.4.24.-; +COMPND 6 ENGINEERED: YES +SOURCE MOL_ID: 1; +SOURCE 2 ORGANISM_SCIENTIFIC: SARS CORONAVIRUS; +SOURCE 3 ORGANISM_COMMON: VIRUSES; +SOURCE 4 STRAIN: SARS; +... +REVDAT 1 18-NOV-03 1UJ1 0 +JRNL AUTH H.YANG,M.YANG,Y.DING,Y.LIU,Z.LOU,Z.ZHOU,L.SUN,L.MO, +JRNL AUTH 2 S.YE,H.PANG,G.F.GAO,K.ANAND,M.BARTLAM,R.HILGENFELD, +JRNL AUTH 3 Z.RAO +JRNL TITL THE CRYSTAL STRUCTURES OF SEVERE ACUTE RESPIRATORY +JRNL TITL 2 SYNDROME VIRUS MAIN PROTEASE AND ITS COMPLEX WITH +JRNL TITL 3 AN INHIBITOR +JRNL REF PROC.NAT.ACAD.SCI.USA V. 100 13190 2003 +JRNL REFN ASTM PNASA6 US ISSN 0027-8424 +.... +ATOM 1 N PHE A 3 63.478 -27.806 23.971 1.00 44.82 N +ATOM 2 CA PHE A 3 64.607 -26.997 24.516 1.00 42.13 C +ATOM 3 C PHE A 3 64.674 -25.701 23.723 1.00 41.61 C +ATOM 4 O PHE A 3 65.331 -25.633 22.673 1.00 40.73 O +ATOM 5 CB PHE A 3 65.912 -27.763 24.358 1.00 44.33 C +ATOM 6 CG PHE A 3 67.065 -27.162 25.108 1.00 44.20 C +ATOM 7 CD1 PHE A 3 67.083 -27.172 26.496 1.00 43.35 C +ATOM 8 CD2 PHE A 3 68.135 -26.595 24.422 1.00 43.49 C +ATOM 9 CE1 PHE A 3 68.140 -26.631 27.187 1.00 43.21 C +ATOM 10 CE2 PHE A 3 69.210 -26.046 25.108 1.00 42.91 C +ATOM 11 CZ PHE A 3 69.216 -26.062 26.493 1.00 43.22 C +ATOM 12 N ARG A 4 64.007 -24.666 24.228 1.00 34.90 N +ATOM 13 CA ARG A 4 63.951 -23.376 23.543 1.00 37.71 C +... +\end{verbatim} +\end{frame} + +\begin{frame}[fragile]{Formale Sprachen in der Bioinformatik} + {\dots\ und das Protein, das beschrieben wird.} + + \includegraphicscopyright[width=9.5cm]{beamerexample-lecture-pic6.jpg} + {Copyright Till Tantau, Low Resultion} +\end{frame} + + +\section<article>{Zusammenfassung} +\section<presentation>*{Zusammenfassung} + +\begin{frame}{Zusammenfassung} + \begin{enumerate} + \item Ein \alert{Wort} ist eine Folge von Symbolen aus einem + \alert{Alphabet}. + \item Eine \alert{Syntax} besteht aus Regeln, nach denen + Worte (Texte) gebaut werden dürfen. + \item Eine \alert{Semantik} legt fest, was Worte \alert{bedeuten}. + \item Eine \alert{formale Sprache} ist eine Menge von Worten + über einem Alphabet. + \end{enumerate} +\end{frame} + +\end{document} + + + + + diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-logo.pdf b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-logo.pdf Binary files differnew file mode 100644 index 00000000000..d870b1203d2 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-logo.pdf diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic1.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic1.jpg Binary files differnew file mode 100644 index 00000000000..7fbce74d3e3 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic1.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic2.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic2.jpg Binary files differnew file mode 100644 index 00000000000..958a7f288b5 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic2.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic3.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic3.jpg Binary files differnew file mode 100644 index 00000000000..67c4bce95c1 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic3.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic4.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic4.jpg Binary files differnew file mode 100644 index 00000000000..fd6c9c1b22e --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic4.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic5.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic5.jpg Binary files differnew file mode 100644 index 00000000000..0a18dc5a735 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic5.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic6.jpg b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic6.jpg Binary files differnew file mode 100644 index 00000000000..fb451d9195b --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-pic6.jpg diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-print-version.pdf b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-print-version.pdf Binary files differnew file mode 100644 index 00000000000..f553a319c56 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-print-version.pdf diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-print-version.tex b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-print-version.tex new file mode 100644 index 00000000000..ee5a65c8d28 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-print-version.tex @@ -0,0 +1,14 @@ +% Copyright 2007 by Till Tantau +% +% This file may be distributed and/or modified +% +% 1. under the LaTeX Project Public License and/or +% 2. under the GNU Public License. +% +% See the file doc/licenses/LICENSE for more details. + +\documentclass[german,a4paper,9pt]{extarticle} +\usepackage{beamerarticle} +\input{beamerexample-lecture-style.tex} +\input{beamerexample-lecture-body.tex} + diff --git a/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-style.tex b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-style.tex new file mode 100644 index 00000000000..b71e7a9d0ad --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/a-lecture/beamerexample-lecture-style.tex @@ -0,0 +1,233 @@ +% Copyright 2007 by Till Tantau +% +% This file may be distributed and/or modified +% +% 1. under the LaTeX Project Public License and/or +% 2. under the GNU Public License. +% +% See the file doc/licenses/LICENSE for more details. + + +% Common packages + +\usepackage[german]{babel} +\usepackage[latin1]{inputenc} +\usepackage{times} +\mode<article> +{ + \usepackage{times} + \usepackage{mathptmx} + \usepackage[left=1.5cm,right=6cm,top=1.5cm,bottom=3cm]{geometry} +} + +\usepackage{hyperref} +\usepackage[T1]{fontenc} +\usepackage{tikz} +\usepackage{colortbl} +\usepackage{yfonts} +\usepackage{colortbl} +\usepackage{translator} % comment this, if not available + + +% Common settings for all lectures in this course + +\def\lecturename{Logik für Informatiker} + +\title{\insertlecture} + +\author{Till Tantau} + +\institute +{ + Institut für Theoretische Informatik\\ + Universität zu Lübeck +} + +\subject{Vorlesung \lecturename} + + + + +% Beamer version theme settings + +\useoutertheme[height=0pt,width=2cm,right]{sidebar} +\usecolortheme{rose,sidebartab} +\useinnertheme{circles} +\usefonttheme[only large]{structurebold} + +\setbeamercolor{sidebar right}{bg=black!15} +\setbeamercolor{structure}{fg=blue} +\setbeamercolor{author}{parent=structure} + +\setbeamerfont{title}{series=\normalfont,size=\LARGE} +\setbeamerfont{title in sidebar}{series=\bfseries} +\setbeamerfont{author in sidebar}{series=\bfseries} +\setbeamerfont*{item}{series=} +\setbeamerfont{frametitle}{size=} +\setbeamerfont{block title}{size=\small} +\setbeamerfont{subtitle}{size=\normalsize,series=\normalfont} + +\setbeamertemplate{navigation symbols}{} +\setbeamertemplate{bibliography item}[book] +\setbeamertemplate{sidebar right} +{ + {\usebeamerfont{title in sidebar}% + \vskip1.5em% + \hskip3pt% + \usebeamercolor[fg]{title in sidebar}% + \insertshorttitle[width=2cm-6pt,center,respectlinebreaks]\par% + \vskip1.25em% + }% + {% + \hskip3pt% + \usebeamercolor[fg]{author in sidebar}% + \usebeamerfont{author in sidebar}% + \insertshortauthor[width=2cm-2pt,center,respectlinebreaks]\par% + \vskip1.25em% + }% + \hbox to2cm{\hss\insertlogo\hss} + \vskip1.25em% + \insertverticalnavigation{2cm}% + \vfill + \hbox to 2cm{\hfill\usebeamerfont{subsection in + sidebar}\strut\usebeamercolor[fg]{subsection in + sidebar}\insertshortlecture.\insertframenumber\hskip5pt}% + \vskip3pt% +}% + +\setbeamertemplate{title page} +{ + \vbox{} + \vskip1em + {\huge Kapitel \insertshortlecture\par} + {\usebeamercolor[fg]{title}\usebeamerfont{title}\inserttitle\par}% + \ifx\insertsubtitle\@empty% + \else% + \vskip0.25em% + {\usebeamerfont{subtitle}\usebeamercolor[fg]{subtitle}\insertsubtitle\par}% + \fi% + \vskip1em\par + Vorlesung \emph{\lecturename}\ vom \insertdate\par + \vskip0pt plus1filll + \leftskip=0pt plus1fill\insertauthor\par + \insertinstitute\vskip1em +} + +\logo{\includegraphics[width=2cm]{beamerexample-lecture-logo.pdf}} + + + +% Article version layout settings + +\mode<article> + +\makeatletter +\def\@listI{\leftmargin\leftmargini + \parsep 0pt + \topsep 5\p@ \@plus3\p@ \@minus5\p@ + \itemsep0pt} +\let\@listi=\@listI + + +\setbeamertemplate{frametitle}{\paragraph*{\insertframetitle\ + \ \small\insertframesubtitle}\ \par +} +\setbeamertemplate{frame end}{% + \marginpar{\scriptsize\hbox to 1cm{\sffamily% + \hfill\strut\insertshortlecture.\insertframenumber}\hrule height .2pt}} +\setlength{\marginparwidth}{1cm} +\setlength{\marginparsep}{4.5cm} + +\def\@maketitle{\makechapter} + +\def\makechapter{ + \newpage + \null + \vskip 2em% + {% + \parindent=0pt + \raggedright + \sffamily + \vskip8pt + {\fontsize{36pt}{36pt}\selectfont Kapitel \insertshortlecture \par\vskip2pt} + {\fontsize{24pt}{28pt}\selectfont \color{blue!50!black} \insertlecture\par\vskip4pt} + {\Large\selectfont \color{blue!50!black} \insertsubtitle\par} + \vskip10pt + + \normalsize\selectfont Druckfassung der + Vorlesung \emph{\lecturename} vom \@date\par\vskip1.5em + \hfill Till Tantau, Institut für Theoretische Informatik, Universität zu Lübeck + } + \par + \vskip 1.5em% +} + +\let\origstartsection=\@startsection +\def\@startsection#1#2#3#4#5#6{% + \origstartsection{#1}{#2}{#3}{#4}{#5}{#6\normalfont\sffamily\color{blue!50!black}\selectfont}} + +\makeatother + +\mode +<all> + + + + +% Typesetting Listings + +\usepackage{listings} +\lstset{language=Java} + +\alt<presentation> +{\lstset{% + basicstyle=\footnotesize\ttfamily, + commentstyle=\slshape\color{green!50!black}, + keywordstyle=\bfseries\color{blue!50!black}, + identifierstyle=\color{blue}, + stringstyle=\color{orange}, + escapechar=\#, + emphstyle=\color{red}} +} +{ + \lstset{% + basicstyle=\ttfamily, + keywordstyle=\bfseries, + commentstyle=\itshape, + escapechar=\#, + emphstyle=\bfseries\color{red} + } +} + + + +% Common theorem-like environments + +\theoremstyle{definition} +\newtheorem{exercise}[theorem]{\translate{Exercise}} + + + + +% New useful definitions: + +\newbox\mytempbox +\newdimen\mytempdimen + +\newcommand\includegraphicscopyright[3][]{% + \leavevmode\vbox{\vskip3pt\raggedright\setbox\mytempbox=\hbox{\includegraphics[#1]{#2}}% + \mytempdimen=\wd\mytempbox\box\mytempbox\par\vskip1pt% + \fontsize{3}{3.5}\selectfont{\color{black!25}{\vbox{\hsize=\mytempdimen#3}}}\vskip3pt% +}} + +\newenvironment{colortabular}[1]{\medskip\rowcolors[]{1}{blue!20}{blue!10}\tabular{#1}\rowcolor{blue!40}}{\endtabular\medskip} + +\def\equad{\leavevmode\hbox{}\quad} + +\newenvironment{greencolortabular}[1] +{\medskip\rowcolors[]{1}{green!50!black!20}{green!50!black!10}% + \tabular{#1}\rowcolor{green!50!black!40}}% +{\endtabular\medskip} + + + 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 Binary files differdeleted file mode 100644 index b459c8fa099..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-computer-mask.jpg +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-computer.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-computer.jpg Binary files differdeleted file mode 100644 index f48e2ae106f..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-computer.jpg +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-computerred.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-computerred.jpg Binary files differdeleted file mode 100644 index 4e691bd2c58..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-computerred.jpg +++ /dev/null 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 Binary files differdeleted file mode 100644 index fe82742d707..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4-mask.jpg +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4.jpg Binary files differdeleted file mode 100644 index cea4d4c2177..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4.jpg +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4red.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4red.jpg Binary files differdeleted file mode 100644 index 77be392fa11..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-g4red.jpg +++ /dev/null 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 Binary files differdeleted file mode 100644 index 56556cfa7d9..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-ram-mask.jpg +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamer-ram.jpg b/Master/texmf-dist/doc/latex/beamer/examples/beamer-ram.jpg Binary files differdeleted file mode 100644 index a8768667840..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-ram.jpg +++ /dev/null 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 Binary files differdeleted file mode 100644 index 693877d65b7..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-tu-logo-mask.jpg +++ /dev/null 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 Binary files differdeleted file mode 100644 index 84d4fd4f228..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-tu-logo.jpg +++ /dev/null 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 Binary files differdeleted file mode 100644 index a1ce12cdff0..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-ur-logo-mask.jpg +++ /dev/null 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 Binary files differdeleted file mode 100644 index 29dc62f5a9f..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamer-ur-logo.jpg +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.pdf b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.pdf Binary files differdeleted file mode 100644 index e766318d174..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample1.pdf +++ /dev/null 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} - - diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.pdf b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.pdf Binary files differdeleted file mode 100644 index 3d5099be798..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.pdf +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.tex deleted file mode 100644 index a94cc306cac..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.article.tex +++ /dev/null @@ -1,11 +0,0 @@ -% $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 Binary files differdeleted file mode 100644 index 2121e2eceae..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.beamer.pdf +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.beamer.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.beamer.tex deleted file mode 100644 index 96a868c6da7..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.beamer.tex +++ /dev/null @@ -1,10 +0,0 @@ -% $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 deleted file mode 100644 index ffcb103d965..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample2.tex +++ /dev/null @@ -1,95 +0,0 @@ -% $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ät für 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 Binary files differdeleted file mode 100644 index abbea370d9c..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample3.pdf +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample3.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample3.tex deleted file mode 100644 index 3e79726310d..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample3.tex +++ /dev/null @@ -1,130 +0,0 @@ -% $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ät für 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 Binary files differdeleted file mode 100644 index 75b331a7c4e..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample4.pdf +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample4.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample4.tex deleted file mode 100644 index 7864d58473b..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample4.tex +++ /dev/null @@ -1,45 +0,0 @@ -% $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 Binary files differdeleted file mode 100644 index 06d7196ad2e..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample5.pdf +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample5.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample5.tex deleted file mode 100644 index 23ef834d70e..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample5.tex +++ /dev/null @@ -1,1021 +0,0 @@ -% $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ät für 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änder}{}} - \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änder}{}}% - \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 Binary files differdeleted file mode 100644 index 93a25983497..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample6.pdf +++ /dev/null diff --git a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample6.tex b/Master/texmf-dist/doc/latex/beamer/examples/beamerexample6.tex deleted file mode 100644 index f77a6a1af4e..00000000000 --- a/Master/texmf-dist/doc/latex/beamer/examples/beamerexample6.tex +++ /dev/null @@ -1,69 +0,0 @@ -% $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ät für 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üh. - \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} - - diff --git a/Master/texmf-dist/doc/latex/beamer/examples/lyx-based-presentation/beamerexample-lyx.lyx b/Master/texmf-dist/doc/latex/beamer/examples/lyx-based-presentation/beamerexample-lyx.lyx new file mode 100644 index 00000000000..0d443181c8b --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/examples/lyx-based-presentation/beamerexample-lyx.lyx @@ -0,0 +1,3880 @@ +#LyX 1.3 created this file. For more info see http://www.lyx.org/ +\lyxformat 221 +\textclass beamer +\begin_preamble +\beamertemplateshadingbackground{red!5}{structure!5} + +\usepackage{beamerthemeshadow} +\usepackage{pgfnodes,pgfarrows,pgfheaps} + +\beamertemplatetransparentcovereddynamicmedium + + +\pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo} +\logo{\pgfuseimage{icsi-logo}} + + + + +\newcommand{\Class}[1]{\operatorname{\mathchoice + {\text{\small #1}} + {\text{\small #1}} + {\text{#1}} + {\text{#1}}}} + +\newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}} + +\newcommand{\tape}[3]{% + \color{structure!30!averagebackgroundcolor} + \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{structure} + \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}} + \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}} + + \color{black} + \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}% +} + +\newcommand{\shorttape}[3]{% + \color{structure!30!averagebackgroundcolor} + \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(1,0.5)} + \pgflineto{\pgfxy(1.1,0.4)} + \pgflineto{\pgfxy(0.9,0.3)} + \pgflineto{\pgfxy(1.1,0.2)} + \pgflineto{\pgfxy(0.9,0.1)} + \pgflineto{\pgfxy(1,0)} + \pgfclosepath + \pgffill + + \color{structure} + \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}} + \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}} + + \color{black} + \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}% +} + +\pgfdeclareverticalshading{heap1}{\the\paperwidth}% + {color(0pt)=(black); color(1cm)=(structure!65!white)} +\pgfdeclareverticalshading{heap2}{\the\paperwidth}% + {color(0pt)=(black); color(1cm)=(structure!55!white)} +\pgfdeclareverticalshading{heap3}{\the\paperwidth}% + {color(0pt)=(black); color(1cm)=(structure!45!white)} +\pgfdeclareverticalshading{heap4}{\the\paperwidth}% + {color(0pt)=(black); color(1cm)=(structure!35!white)} +\pgfdeclareverticalshading{heap5}{\the\paperwidth}% + {color(0pt)=(black); color(1cm)=(structure!25!white)} +\pgfdeclareverticalshading{heap6}{\the\paperwidth}% + {color(0pt)=(black); color(1cm)=(red!35!white)} + +\newcommand{\heap}[5]{% + \begin{pgfscope} + \color{#4} + \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)} + \pgfclip + \begin{pgfmagnify}{1}{#1} + \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}} + \end{pgfmagnify} + \end{pgfscope} + %\pgffill + + \color{#4} + \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)} + \pgfstroke + + \color{white} + \pgfheaplabel{\pgfxy(0,#1)}{#3}% +} + + +\newcommand{\langat}[2]{% + \color{black!30!beamerexample} + \pgfsetlinewidth{0.6pt} + \pgfsetendarrow{\pgfarrowdot} + \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)} + \color{beamerexample} + \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}% +} + +\newcommand{\langatother}[2]{% + \color{black!30!beamerexample} + \pgfsetlinewidth{0.6pt} + \pgfsetendarrow{\pgfarrowdot} + \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)} + \color{beamerexample} + \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}% +} + + +\pgfdeclaremask{knight1-mask}{beamer-knight1-mask} \pgfdeclareimage[height=2cm,mask=knight1-mask]{knight1}{beamer-knight1} \pgfdeclaremask{knight2-mask}{beamer-knight2-mask} \pgfdeclareimage[height=2cm,mask=knight2-mask]{knight2}{beamer-knight2} \pgfdeclaremask{knight3-mask}{beamer-knight3-mask} \pgfdeclareimage[height=2cm,mask=knight3-mask,interpolate=true]{knight3}{beamer-knight3} \pgfdeclaremask{knight4-mask}{beamer-knight4-mask} \pgfdeclareimage[height=2cm,mask=knight4-mask,interpolate=true]{knight4}{beamer-knight4} + + +\pgfdeclareradialshading{graphnode} + {\pgfpoint{-3pt}{3.6pt}}% + {color(0cm)=(beamerexample!15); + color(2.63pt)=(beamerexample!75); + color(5.26pt)=(beamerexample!70!black); + color(7.6pt)=(beamerexample!50!black); + color(8pt)=(beamerexample!10!averagebackgroundcolor)} + +\newcommand{\graphnode}[2]{ + \pgfnodecircle{#1}[virtual]{#2}{8pt} + \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}} +} +\end_preamble +\options notes=show +\language english +\inputencoding auto +\fontscheme times +\graphics default +\paperfontsize default +\spacing single +\papersize Default +\paperpackage a4 +\use_geometry 0 +\use_amsmath 1 +\use_natbib 0 +\use_numerical_citations 0 +\paperorientation portrait +\secnumdepth 2 +\tocdepth 2 +\paragraph_separation indent +\defskip medskip +\quotes_language english +\quotes_times 2 +\papercolumns 1 +\papersides 1 +\paperpagestyle default + +\layout Title + +The Complexity of +\newline +Finding Paths in Tournaments +\layout Author + +Till Tantau +\layout Institute + +International Computer Schience Institute +\newline +Berkeley, California +\begin_inset OptArg +collapsed true + +\layout Standard + +ICSI +\end_inset + + +\layout Date + +January 30th, 2004 +\layout BeginFrame + +Outline +\layout Standard + + +\begin_inset LatexCommand \tableofcontents{} + +\end_inset + + +\begin_inset ERT +status Collapsed + +\layout Standard +[pausesections] +\end_inset + + +\layout EndFrame + +\layout Standard + + +\begin_inset ERT +status Collapsed + +\layout Standard +% Show the table of contents at the beginning +\layout Standard +% of every subsection. +\layout Standard + +\backslash +AtBeginSubsection[]{ +\layout Standard + +\backslash +frame<handout:0>{ +\layout Standard + +\backslash +frametitle{Outline} +\layout Standard + +\backslash +tableofcontents[current,currentsubsection] +\layout Standard + } +\layout Standard +} +\end_inset + + +\layout Section + +Introduction +\layout Subsection + +What are Tournaments? +\layout BeginFrame + +Tournaments Consist of Jousts Between Knights +\layout Columns + +\begin_deeper +\layout Column + +5.75cm +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm} +\layout Standard + +\backslash +pgfnodebox{A}[virtual]{ +\backslash +pgfxy(2,1)}{ +\backslash +pgfuseimage{knight1}}{2pt}{2pt} +\layout Standard + +\backslash +pgfnodebox{B}[virtual]{ +\backslash +pgfxy(6,1)}{ +\backslash +pgfuseimage{knight2}}{2pt}{2pt} +\layout Standard + +\backslash +pgfnodebox{C}[virtual]{ +\backslash +pgfxy(4,-1)}{ +\backslash +pgfuseimage{knight3}}{2pt}{2pt} +\layout Standard + +\backslash +pgfnodebox{D}[virtual]{ +\backslash +pgfxy(4,3)}{ +\backslash +pgfuseimage{knight4}}{2pt}{2pt} +\layout Standard + +\layout Standard + +\backslash +color{beamerexample} +\layout Standard + +\backslash +only<3->{ +\backslash +pgfsetendarrow{ +\backslash +pgfarrowto}} +\layout Standard + +\backslash +only<2->{ +\layout Standard + +\backslash +pgfsetlinewidth{0.6pt} +\layout Standard + +\backslash +pgfnodeconnline{A}{B} +\layout Standard + +\backslash +pgfnodeconnline{A}{C} +\layout Standard + +\backslash +pgfnodeconnline{D}{A} +\layout Standard + +\backslash +pgfnodeconnline{C}{B} +\layout Standard + +\backslash +pgfnodeconnline{B}{D} +\layout Standard + +\backslash +pgfnodeconnline{C}{D}} +\layout Standard + +\backslash +end{pgfpicture} +\end_inset + + +\layout Column + +6cm +\layout Block + + +\begin_inset ERT +status Inlined + +\layout Standard +{What is a Tournament?} +\end_inset + + +\begin_deeper +\layout Itemize + + +\begin_inset ERT +status Collapsed + +\layout Standard +<1-> +\end_inset + +A group of knights. +\layout Itemize + + +\begin_inset ERT +status Collapsed + +\layout Standard +<2-> +\end_inset + +Every pair has a joust. +\layout Itemize + + +\begin_inset ERT +status Collapsed + +\layout Standard +<3-> +\end_inset + +In every joust one knight wins. +\end_deeper +\end_deeper +\layout BeginFrame + +Tournaments are Complete Directed Graphs +\layout Columns + +\begin_deeper +\layout Column + +5cm +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm} +\layout Standard + +\backslash +color{beamerexample} +\layout Standard + +\backslash +pgfsetlinewidth{0.6pt} +\layout Standard + +\backslash +graphnode{A}{ +\backslash +pgfxy(2.5,1)} +\layout Standard + +\backslash +graphnode{B}{ +\backslash +pgfxy(5.5,1)} +\layout Standard + +\backslash +graphnode{C}{ +\backslash +pgfxy(4,-0.5)} +\layout Standard + +\backslash +graphnode{D}{ +\backslash +pgfxy(4,2.5)} +\layout Standard + +\layout Standard + +\backslash +color{white} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{A}}{ +\backslash +pgfbox[center,center]{$v_2$}} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{B}}{ +\backslash +pgfbox[center,center]{$v_3$}} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{C}}{ +\backslash +pgfbox[center,center]{$v_4$}} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{D}}{ +\backslash +pgfbox[center,center]{$v_1$}} +\layout Standard + +\layout Standard + +\backslash +color{beamerexample} +\layout Standard + +\backslash +pgfsetendarrow{ +\backslash +pgfarrowto} +\layout Standard + +\backslash +pgfnodesetsepstart{2pt} +\layout Standard + +\backslash +pgfnodesetsepend{4pt} +\layout Standard + +\backslash +pgfnodeconnline{A}{B} +\layout Standard + +\backslash +pgfnodeconnline{A}{C} +\layout Standard + +\backslash +pgfnodeconnline{D}{A} +\layout Standard + +\backslash +pgfnodeconnline{C}{B} +\layout Standard + +\backslash +pgfnodeconnline{B}{D} +\layout Standard + +\backslash +pgfnodeconnline{D}{C} +\layout Standard + +\backslash +end{pgfpicture} +\end_inset + + +\layout Column + +6cm +\layout Definition + + +\begin_inset ERT +status Collapsed + +\layout Standard +<2-> +\end_inset + +A +\color red +tournament +\color default + is a +\begin_deeper +\layout Enumerate + +directed graphs, +\layout Enumerate + +with exactly one edge between +\newline +any two different vertices. +\end_deeper +\end_deeper +\layout BeginFrame + + +\begin_inset ERT +status Collapsed + +\layout Standard +[<+>] +\end_inset + +Tournaments Arise Naturally in Different Situations +\layout ExampleBlock + + +\begin_inset ERT +status Inlined + +\layout Standard +{Applicatins in Ordering Theory} +\end_inset + + +\begin_deeper +\layout Standard + +Elements in a set need to be sorted. + +\newline +The comparison relation may be cyclic, however. +\end_deeper +\layout Separator + +\layout ExampleBlock + + +\begin_inset ERT +status Inlined + +\layout Standard +{Applications in Sociology} +\end_inset + + +\begin_deeper +\layout Standard + +Several candidates apply for a position. +\newline +Reviewers decide for any two candidates whom they prefer. + +\end_deeper +\layout Separator + +\layout ExampleBlock + + +\begin_inset ERT +status Inlined + +\layout Standard +{Applications in Structural Complexity Theory} +\end_inset + + +\begin_deeper +\layout Standard + +A language +\begin_inset Formula $L$ +\end_inset + + is given and a selector function +\begin_inset Formula $f$ +\end_inset + +. +\newline +It chooses from any two words the one more likely to be in +\begin_inset Formula $f$ +\end_inset + +. +\end_deeper +\layout Subsection + +What Does ``Finding Paths'' Mean? +\layout BeginFrame + +``Finding Paths'' is Ambiguous +\layout Block + + +\begin_inset ERT +status Inlined + +\layout Standard +{ +\backslash +strut Input for +\backslash +ignorespaces +\backslash +def +\backslash +par{}% because LyX inserts superfluous paragraphs +\layout Standard + +\backslash +only<1>{Path Finding Problems} +\backslash +ignorespaces +\layout Standard + +\backslash +only<2-3>{$ +\backslash +Lang{reach}$} +\backslash +ignorespaces +\layout Standard + +\backslash +only<4-5>{the Construction Problem} +\backslash +ignorespaces +\layout Standard + +\backslash +only<6-7>{the Optimization Problem} +\backslash +ignorespaces +\layout Standard + +\backslash +only<8-9>{$ +\backslash +Lang{distance}$} +\backslash +ignorespaces +\layout Standard + +\backslash +only<10->{the Approximation Problem}} +\end_inset + + +\begin_deeper +\layout Itemize + +A +\color red +graph +\color default + +\begin_inset Formula $G=(V,E)$ +\end_inset + +, a +\color red +source +\color default + +\begin_inset Formula $s\in V$ +\end_inset + + and a +\color red +target +\color default + +\begin_inset Formula $t\in V$ +\end_inset + +. +\layout Itemize + + +\begin_inset ERT +status Collapsed + +\layout Standard +<only@-9| visible@8-> +\end_inset + +A +\color red +maximum distance +\color default +\SpecialChar ~ + +\begin_inset Formula $d$ +\end_inset + +. +\begin_inset ERT +status Collapsed + +\layout Standard + +\backslash +phantom{p} +\end_inset + + +\layout Itemize + + +\begin_inset ERT +status Collapsed + +\layout Standard +<only@10-> +\end_inset + +An +\color red +approximation ratio +\color default + +\begin_inset Formula $r>1$ +\end_inset + +. +\end_deeper +\layout Standard + + +\begin_inset ERT +status Collapsed + +\layout Standard + +\backslash +nointerlineskip +\end_inset + + +\layout Overprint + +\begin_deeper +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +onslide<1,3,5,7,9,11-12> +\end_inset + + +\layout Columns + + +\begin_inset ERT +status Inlined + +\layout Standard +[t,onlytextwidth] +\end_inset + + +\begin_deeper +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +alt<1-2>{ +\backslash +column{ +\backslash +textwidth}}{ +\backslash +column{5cm}} +\end_inset + + +\layout ExampleBlock + + +\begin_inset ERT +status Inlined + +\layout Standard +{Example Input} +\end_inset + + +\begin_deeper +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm} +\layout Standard + +\backslash +color{beamerexample} +\layout Standard + +\backslash +pgfsetlinewidth{0.6pt} +\layout Standard + +\backslash +graphnode{A}{ +\backslash +pgfxy(3,1)} +\layout Standard + +\backslash +graphnode{B}{ +\backslash +pgfxy(5,1)} +\layout Standard + +\backslash +graphnode{C}{ +\backslash +pgfxy(4,0)} +\layout Standard + +\backslash +graphnode{D}{ +\backslash +pgfxy(4,2)} +\layout Standard + +\layout Standard + +\backslash +color{white} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{B}}{ +\backslash +pgfbox[center,center]{$t$}} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{D}}{ +\backslash +pgfbox[center,center]{$s$}} +\layout Standard + +\layout Standard + +\backslash +color{beamerexample} +\layout Standard + +\backslash +pgfsetendarrow{ +\backslash +pgfarrowto} +\layout Standard + +\backslash +pgfnodesetsepstart{2pt} +\layout Standard + +\backslash +pgfnodesetsepend{4pt} +\layout Standard + +\backslash +pgfnodeconnline{A}{B} +\layout Standard + +\backslash +pgfnodeconnline{A}{C} +\layout Standard + +\backslash +pgfnodeconnline{D}{A} +\layout Standard + +\backslash +pgfnodeconnline{C}{B} +\layout Standard + +\backslash +pgfnodeconnline{B}{D} +\layout Standard + +\backslash +pgfnodeconnline{D}{C} +\layout Standard + +\layout Standard + +\backslash +only<9> { +\backslash +pgfputat{ +\backslash +pgfxy(5.3,1)}{ +\backslash +pgfbox[left,center]{, $d=2$}}} +\layout Standard + +\backslash +only<11>{ +\backslash +pgfputat{ +\backslash +pgfxy(5.3,1)}{ +\backslash +pgfbox[left,center]{, $r=1.5$}}} +\layout Standard + +\backslash +only<12>{ +\backslash +pgfputat{ +\backslash +pgfxy(5.3,1)}{ +\backslash +pgfbox[left,center]{, $r=1.25$}}} +\layout Standard + +\backslash +end{pgfpicture} +\end_inset + + +\end_deeper +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +only<3->{ +\backslash +column{5cm}} +\end_inset + + +\layout ExampleBlock + + +\begin_inset ERT +status Inlined + +\layout Standard +<only@3->{Example Output} +\end_inset + + +\begin_deeper +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm} +\layout Standard + +\backslash +only<5-8,10->{ +\layout Standard + +\backslash +color{beamerexample} +\layout Standard + +\backslash +pgfsetlinewidth{0.6pt} +\layout Standard + +\backslash +graphnode{A}{ +\backslash +pgfxy(3,1)} +\layout Standard + +\backslash +graphnode{B}{ +\backslash +pgfxy(5,1)} +\layout Standard + +\backslash +graphnode{C}{ +\backslash +pgfxy(4,0)} +\layout Standard + +\backslash +graphnode{D}{ +\backslash +pgfxy(4,2)} +\layout Standard + +\layout Standard + +\backslash +color{white} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{B}}{ +\backslash +pgfbox[center,center]{$t$}} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{D}}{ +\backslash +pgfbox[center,center]{$s$}} +\layout Standard + +\layout Standard + +\backslash +color{beamerexample} +\layout Standard + +\backslash +pgfsetendarrow{ +\backslash +pgfarrowto} +\layout Standard + +\backslash +pgfnodesetsepstart{2pt} +\layout Standard + +\backslash +pgfnodesetsepend{4pt} +\layout Standard + +\layout Standard + +\backslash +alert<7,12>{ +\backslash +pgfnodeconnline{A}{B}} +\layout Standard + +\backslash +alert<5,11>{ +\backslash +pgfnodeconnline{A}{C}} +\layout Standard + +\backslash +alert<5,7,11-12>{ +\backslash +pgfnodeconnline{D}{A}} +\layout Standard + +\backslash +alert<5,11>{ +\backslash +pgfnodeconnline{C}{B}} +\layout Standard + +\backslash +pgfnodeconnline{B}{D} +\layout Standard + +\backslash +pgfnodeconnline{D}{C} +\layout Standard + } +\layout Standard + +\backslash +only<3,9>{ +\backslash +pgfputat{ +\backslash +pgfxy(2.75,1)}{ +\backslash +pgfbox[left,center]{ +\backslash +alert{``Yes''}}}} +\layout Standard + +\backslash +end{pgfpicture} +\end_inset + + +\end_deeper +\end_deeper +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +onslide<2,4,6,8,10> +\end_inset + + +\layout Block + + +\begin_inset ERT +status Inlined + +\layout Standard +{Variants of Path Finding Problems} +\end_inset + + +\begin_deeper +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +usedescriptionitemofwidthas{Approximation Problem:} +\end_inset + + +\layout Description + +Reachability\SpecialChar ~ +Problem: +\begin_inset ERT +status Collapsed + +\layout Standard +<2-> +\end_inset + +Is there a path from +\begin_inset Formula $s$ +\end_inset + + to\SpecialChar ~ + +\begin_inset Formula $t$ +\end_inset + +? +\layout Description + +Construction\SpecialChar ~ +Problem: +\begin_inset ERT +status Collapsed + +\layout Standard +<4-> +\end_inset + +Construct a path from +\begin_inset Formula $s$ +\end_inset + + to\SpecialChar ~ + +\begin_inset Formula $t$ +\end_inset + +? +\layout Description + +Optimization\SpecialChar ~ +Problem: +\begin_inset ERT +status Collapsed + +\layout Standard +<6-> +\end_inset + +Construct a shortest path from +\begin_inset Formula $s$ +\end_inset + + to\SpecialChar ~ + +\begin_inset Formula $t$ +\end_inset + +. +\layout Description + +Distance\SpecialChar ~ +Problem: +\begin_inset ERT +status Collapsed + +\layout Standard +<8-> +\end_inset + +Is the distance of +\begin_inset Formula $s$ +\end_inset + + and\SpecialChar ~ + +\begin_inset Formula $t$ +\end_inset + + at most\SpecialChar ~ + +\begin_inset Formula $d$ +\end_inset + +? +\layout Description + +Approximation\SpecialChar ~ +Problem: +\begin_inset ERT +status Collapsed + +\layout Standard +<10-> +\end_inset + +Construct a path from +\begin_inset Formula $s$ +\end_inset + + to\SpecialChar ~ + +\begin_inset Formula $t$ +\end_inset + + of length +\newline +approximately their distance. +\end_deeper +\end_deeper +\layout Section + +Review +\layout Subsection + +Standard Complexity Classes +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +pgfdeclaremask{computer-mask}{beamer-g4-mask} +\backslash +pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer-g4} +\end_inset + + +\layout BeginFrame + +The Classes L and NL are Defined via +\newline +Logspace Turing Machines +\layout Standard + + +\begin_inset ERT +status Open + +\layout Standard + +\backslash +begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfxy(0,4)}{ +\backslash +tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} +\layout Standard + +\backslash +uncover<2->{ +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfxy(0,0.5)}{ +\backslash +tape{}{output tape (write only)}{10690836937182}}} +\layout Standard + +\backslash +uncover<3->{ +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfxy(7,2)}{ +\backslash +shorttape{work tape (read/write), $O( +\backslash +log n)$ symbols}{}{42}} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfxy(1.75,2.5)}{ +\backslash +pgfbox[center,center]{ +\backslash +pgfuseimage{computer}}} +\layout Standard + } +\layout Standard + +\backslash +pgfsetlinewidth{0.6pt} +\layout Standard + +\layout Standard + +\backslash +color{structure} +\layout Standard + +\backslash +pgfsetendarrow{ +\backslash +pgfarrowto} +\layout Standard + +\backslash +pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85) +\layout Standard + +\backslash +uncover<2->{ +\backslash +pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)} +\layout Standard + +\backslash +uncover<3->{ +\backslash +pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)} +\layout Standard + +\backslash +end{pgfpicture} +\end_inset + + +\layout BeginFrame + +Logspace Turing Machines Are Quite Powerful +\layout Block + + +\begin_inset ERT +status Inlined + +\layout Standard +{Deterministic logspace machines can compute} +\end_inset + + +\begin_deeper +\layout Itemize + +addition, multiplication, and even division +\layout Itemize + +reductions used in completeness proofs, +\layout Itemize + +reachability in forests. +\end_deeper +\layout Pause + +\layout Block + + +\begin_inset ERT +status Inlined + +\layout Standard +{Non-deterministic logspace machines can compute} +\end_inset + + +\begin_deeper +\layout Itemize + +reachability in graphs, +\layout Itemize + +non-reachability in graphs, +\layout Itemize + +satisfiability with two literals per clause. +\end_deeper +\layout BeginFrame + + +\begin_inset ERT +status Inlined + +\layout Standard +<1>[label=hierarchy] +\end_inset + +The Complexity Class Hierarchy +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm} +\layout Standard + +\backslash +pgfsetlinewidth{0.8pt} +\layout Standard + +\backslash +heap{5.5}{3.5}{$ +\backslash +Class P$}{black}{1} +\layout Standard + +\backslash +pgfsetdash{{2pt}}{0pt} +\layout Standard + +\backslash +only<2->{ +\backslash +heap{4.5}{3}{$ +\backslash +Class{NC}^2$}{black!50!structure}{2}} +\layout Standard + +\backslash +heap{3.5}{2.5}{$ +\backslash +Class{NL}$}{black!50!structure}{3} +\layout Standard + +\backslash +heap{2.5}{2}{$ +\backslash +Class{L}$}{black!50!structure}{4} +\layout Standard + +\backslash +only<2->{ +\backslash +heap{1.75}{1.5}{$ +\backslash +vphantom{A} +\backslash +smash{ +\backslash +Class{NC}^1}$}{black!50!structure}{5}} +\layout Standard + +\backslash +pgfsetdash{}{0pt} +\layout Standard + +\backslash +only<2->{ +\backslash +heap{1.1}{1}{$ +\backslash +vphantom{A} +\backslash +smash{ +\backslash +Class{AC}^0}$}{black}{6}} +\layout Standard + +\layout Standard + +\backslash +pgfsetlinewidth{1.0pt} +\layout Standard + +\backslash +color{black} +\layout Standard + +\backslash +pgfxyline(-5,0)(5,0) +\layout Standard + +\layout Standard + +\backslash +only<1-2>{ +\backslash +langat{3.375}{$ +\backslash +Lang{reach}$}} +\layout Standard + +\backslash +only<1-2>{ +\backslash +langat{2.375}{$ +\backslash +Lang{reach}_{ +\backslash +operatorname{forest}}$}} +\layout Standard + +\layout Standard + +\backslash +only<2>{ +\backslash +langat{0.975}{$ +\backslash +Lang{addition}$}} +\layout Standard + +\backslash +only<2>{ +\backslash +langatother{1.6}{ +\backslash +vbox{ +\backslash +hbox{$ +\backslash +Lang{division}$,} +\backslash +hbox{$ +\backslash +Lang{parity}$}}}} +\layout Standard + +\backslash +only<3-5>{ +\backslash +langat{3.375}{ +\backslash +vbox{ +\backslash +hbox{$ +\backslash +Lang{distance}$,} +\backslash +hbox{$ +\backslash +Lang{reach}$}}}} +\layout Standard + +\backslash +only<4->{ +\backslash +langatother{2.375}{ +\backslash +vbox{ +\backslash +ignorespaces +\layout Standard + +\backslash +hbox{$ +\backslash +Lang{distance}_{ +\backslash +operatorname{forest}}$,} +\backslash +ignorespaces +\layout Standard + +\backslash +hbox{$ +\backslash +Lang{reach}_{ +\backslash +operatorname{forest}}$,} +\backslash +ignorespaces +\layout Standard + +\backslash +hbox{$ +\backslash +Lang{distance}_{ +\backslash +operatorname{path}}$,} +\backslash +ignorespaces +\layout Standard + +\backslash +hbox{$ +\backslash +Lang{reach}_{ +\backslash +operatorname{path}}$}}}} +\layout Standard + +\backslash +only<5->{ +\backslash +langat{0.975}{$ +\backslash +Lang{reach}_{ +\backslash +operatorname{tourn}}$}} +\layout Standard + +\backslash +only<6->{ +\backslash +langat{3.375}{ +\backslash +vbox{ +\backslash +ignorespaces +\layout Standard + +\backslash +hbox{$ +\backslash +Lang{distance}_{ +\backslash +operatorname{tourn}}$,} +\backslash +ignorespaces +\layout Standard + +\backslash +hbox{$ +\backslash +Lang{distance}$,} +\backslash +ignorespaces +\layout Standard + +\backslash +hbox{$ +\backslash +Lang{reach}$}}}} +\layout Standard + +\backslash +only<7->{ +\backslash +pgfsetdash{{1pt}}{0pt} +\backslash +langat{2.375}{``$ +\backslash +Lang{approx}_{ +\backslash +operatorname{tourn}}$''}} +\layout Standard + +\backslash +end{pgfpicture} +\end_inset + + +\layout BeginFrame + +The Circuit Complexity Classes AC +\begin_inset Formula $^{0}$ +\end_inset + +, NC +\begin_inset Formula $^{1}$ +\end_inset + +, and NC +\begin_inset Formula $^{2}$ +\end_inset + + +\newline +Limit the Circuit Depth +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +setlength +\backslash +leftmargini{1em} +\layout Standard + +\backslash +nointerlineskip +\end_inset + + +\layout Columns + + +\begin_inset ERT +status Collapsed + +\layout Standard +[t] +\end_inset + + +\begin_deeper +\layout Column + +3.6cm +\layout Block + + +\begin_inset ERT +status Collapsed + +\layout Standard +{ +\end_inset + +Circuit Class +\begin_inset Formula $\Class{AC}^{0}$ +\end_inset + + +\begin_inset ERT +status Collapsed + +\layout Standard +} +\end_inset + + +\begin_deeper +\layout Itemize + + +\begin_inset Formula $O(1)$ +\end_inset + + depth +\layout Itemize + +unbounded fan-in +\end_deeper +\layout Examples + +\begin_deeper +\layout Itemize + + +\begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$ +\end_inset + +. +\layout Itemize + + +\begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$ +\end_inset + +. +\end_deeper +\layout Pause + +\layout Column + +3.6cm +\layout Block + + +\begin_inset ERT +status Collapsed + +\layout Standard +{ +\end_inset + +Circuit Class +\begin_inset Formula $\Class{NC}^{1}$ +\end_inset + + +\begin_inset ERT +status Collapsed + +\layout Standard +} +\end_inset + + +\begin_deeper +\layout Itemize + + +\begin_inset Formula $O(\log n)$ +\end_inset + + depth +\layout Itemize + +bounded fan-in +\end_deeper +\layout Examples + +\begin_deeper +\layout Itemize + + +\begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$ +\end_inset + +. +\layout Itemize + + +\begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$ +\end_inset + +. +\layout Itemize + + +\begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$ +\end_inset + +. +\end_deeper +\layout Pause + +\layout Column + +3.6cm +\layout Block + + +\begin_inset ERT +status Collapsed + +\layout Standard +{ +\end_inset + +Circuit Class +\begin_inset Formula $\Class{NC}^{2}$ +\end_inset + + +\begin_inset ERT +status Collapsed + +\layout Standard +} +\end_inset + + +\begin_deeper +\layout Itemize + + +\begin_inset Formula $O(\log^{2}n)$ +\end_inset + + depth +\layout Itemize + +bounded fan-in +\end_deeper +\layout Examples + +\begin_deeper +\layout Itemize + + +\begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$ +\end_inset + +. +\end_deeper +\end_deeper +\layout AgainFrame + + +\begin_inset ERT +status Collapsed + +\layout Standard +<2> +\end_inset + +hierarchy +\layout Subsection + +Standard Complexity Results on Finding Paths +\layout BeginFrame + +All Variants of Finding Paths in Directed Graphs +\newline +Are Equally Difficult +\layout Fact + + +\begin_inset Formula $\Lang{reach}$ +\end_inset + + and +\begin_inset Formula $\Lang{distance}$ +\end_inset + + are +\begin_inset Formula $\Class{NL}$ +\end_inset + +-complete. + +\layout Pause + +\layout Corollary + +For directed graphs, we can solve +\begin_deeper +\layout Itemize + +the reachability problem in logspace iff +\begin_inset Formula $\Class{L}=\Class{NL}$ +\end_inset + +. +\layout Itemize + +the construction problem in logspace iff +\begin_inset Formula $\Class{L}=\Class{NL}$ +\end_inset + +. +\layout Itemize + +the optimization problem in logspace iff +\begin_inset Formula $\Class{L}=\Class{NL}$ +\end_inset + +. +\layout Itemize + +the approximation problem in logspace iff +\begin_inset Formula $\Class{L}=\Class{NL}$ +\end_inset + +. +\end_deeper +\layout AgainFrame + + +\begin_inset ERT +status Collapsed + +\layout Standard +<3> +\end_inset + +hierarchy +\layout BeginFrame + +FindingPaths in Forests and Directed Paths is Easy, +\newline +But Not Trivial +\layout Fact + + +\begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$ +\end_inset + + and +\begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$ +\end_inset + + are +\begin_inset Formula $\Class{L}$ +\end_inset + +-complete. +\layout Separator + +\layout Fact + + +\begin_inset Formula $\Lang{reach}_{\operatorname{path}}$ +\end_inset + + and +\begin_inset Formula $\Lang{distance}_{\operatorname{path}}$ +\end_inset + + are +\begin_inset Formula $\Class{L}$ +\end_inset + +-complete. +\layout AgainFrame + + +\begin_inset ERT +status Collapsed + +\layout Standard +<4> +\end_inset + +hierarchy +\layout Section + +Finding Paths in Tournaments +\layout Subsection + +Complexity of: Does a Path Exist? +\layout BeginFrame + +Definition of the Tournament Reachability Problem +\layout Definition + +Let +\color red + +\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$ +\end_inset + + +\color default + contain all triples +\begin_inset Formula $(T,s,t)$ +\end_inset + + such that +\begin_deeper +\layout Enumerate + + +\begin_inset Formula $T=(V,E)$ +\end_inset + + is a tournament and +\layout Enumerate + +there exists a path from\SpecialChar ~ + +\begin_inset Formula $s$ +\end_inset + + to\SpecialChar ~ + +\begin_inset Formula $t$ +\end_inset + +. +\end_deeper +\layout BeginFrame + +The Tournament Reachability Problem is Very Easy +\layout Theorem + + +\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$ +\end_inset + +. +\layout Pause + +\layout AlertBlock + + +\begin_inset ERT +status Inlined + +\layout Standard +{Implications} +\end_inset + + +\begin_deeper +\layout Itemize + +The problem is +\begin_inset Quotes eld +\end_inset + +easier +\begin_inset Quotes erd +\end_inset + + than +\begin_inset Formula $\Lang{reach}$ +\end_inset + + and even +\begin_inset Formula $\Lang{reach}_{\operatorname{path}}$ +\end_inset + +. +\layout Itemize + + +\begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$ +\end_inset + +. +\end_deeper +\layout AgainFrame + + +\begin_inset ERT +status Collapsed + +\layout Standard +<5> +\end_inset + +hierarchy +\layout Subsection + +Complexity of: Construct a Shortest Path +\layout BeginFrame + +Finding a Shortest Path Is as Difficult as +\newline +the Distance Problem +\layout Definition + +Let +\color red + +\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + + +\color default +contain all tuples +\begin_inset Formula $(T,s,t,d)$ +\end_inset + + such that +\begin_deeper +\layout Enumerate + + +\begin_inset Formula $T=(V,E)$ +\end_inset + + is a tournament in which +\layout Enumerate + +the distance of +\begin_inset Formula $s$ +\end_inset + + and\SpecialChar ~ + +\begin_inset Formula $t$ +\end_inset + + is at most\SpecialChar ~ + +\begin_inset Formula $d$ +\end_inset + +. +\end_deeper +\layout BeginFrame + +The Tournament Distance Problem is Hard +\layout Theorem + + +\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + + is +\begin_inset Formula $\Class{NL}$ +\end_inset + +-complete. +\layout Standard + + +\hfill + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +hyperlink{hierarchy<6>}{ +\backslash +beamerskipbutton{Skip Proof}} +\end_inset + + +\layout Pause + +\layout Corollary + +Shortest path in tournaments can be constructed +\newline +in logarithmic space, iff +\begin_inset Formula $\Class{L}=\Class{NL}$ +\end_inset + +. +\layout Pause + +\layout Corollary + + +\begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + +. +\layout BeginFrame + +Proof That +\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + + is NL-complete +\layout Standard + + +\begin_inset ERT +status Collapsed + +\layout Standard + +\backslash +nointerlineskip +\end_inset + + +\layout Columns + + +\begin_inset ERT +status Inlined + +\layout Standard +[t,onlytextwidth] +\end_inset + + +\begin_deeper +\layout Column + +5.7cm +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +setlength +\backslash +leftmargini{1.5em} +\end_inset + + +\layout Block + + +\begin_inset ERT +status Collapsed + +\layout Standard +{ +\end_inset + +Reduce +\begin_inset Formula $\Lang{reach}$ +\end_inset + + to +\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + + +\begin_inset ERT +status Collapsed + +\layout Standard +} +\end_inset + + +\begin_deeper +\layout Enumerate + + +\begin_inset ERT +status Inlined + +\layout Standard +<alert@1> +\end_inset + +Is input +\begin_inset Formula $(G,s,t)$ +\end_inset + + in +\begin_inset Formula $\Lang{reach}$ +\end_inset + +? +\layout Enumerate + + +\begin_inset ERT +status Inlined + +\layout Standard +<2-| alert@2-8> +\end_inset + +Map +\begin_inset Formula $G$ +\end_inset + + to +\begin_inset Formula $G'$ +\end_inset + +. +\layout Enumerate + + +\begin_inset ERT +status Inlined + +\layout Standard +<9-| alert@9> +\end_inset + +Query: +\newline + +\begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + +? +\end_deeper +\layout Separator + +\layout Block + + +\begin_inset ERT +status Collapsed + +\layout Standard +{ +\end_inset + +Correctness +\begin_inset ERT +status Collapsed + +\layout Standard +} +\end_inset + + +\begin_inset ERT +status Collapsed + +\layout Standard +<10-> +\end_inset + + +\begin_deeper +\layout Enumerate + + +\begin_inset ERT +status Inlined + +\layout Standard +<10-| alert@10-11> +\end_inset + +A path in\SpecialChar ~ + +\begin_inset Formula $G$ +\end_inset + + induces +\newline +a length-3 path in\SpecialChar ~ + +\begin_inset Formula $G'$ +\end_inset + +. +\layout Enumerate + + +\begin_inset ERT +status Inlined + +\layout Standard +<12-| alert@12-13> +\end_inset + +A length-3 path in\SpecialChar ~ + +\begin_inset Formula $G'$ +\end_inset + + induces +\newline +a path in\SpecialChar ~ + +\begin_inset Formula $G'$ +\end_inset + +. +\end_deeper +\layout Column + +4.5cm +\layout Example + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm} +\layout Standard + +\backslash +color{beamerexample} +\layout Standard + +\backslash +pgfsetlinewidth{0.6pt} +\layout Standard + +\backslash +graphnode{A}{ +\backslash +pgfxy(1,3.3)} +\layout Standard + +\backslash +graphnode{B}{ +\backslash +pgfxy(2,3.3)} +\layout Standard + +\backslash +graphnode{C}{ +\backslash +pgfxy(3,3.3)} +\layout Standard + +\backslash +graphnode{D}{ +\backslash +pgfxy(4,3.3)} +\layout Standard + +\layout Standard + +\backslash +color{white} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{A}}{ +\backslash +pgfbox[center,center]{$s$}} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{D}}{ +\backslash +pgfbox[center,center]{$t$}} +\layout Standard + +\layout Standard + +\backslash +color{beamerexample} +\layout Standard + +\backslash +pgfsetendarrow{ +\backslash +pgfarrowto} +\layout Standard + +\backslash +pgfnodesetsepstart{2pt} +\layout Standard + +\backslash +pgfnodesetsepend{2pt} +\layout Standard + +\backslash +alert<3>{ +\backslash +pgfnodeconnline{B}{A}} +\layout Standard + +\backslash +alert<4>{ +\backslash +pgfnodeconnline{B}{C}} +\layout Standard + +\backslash +alert<5,10-11,13>{ +\backslash +pgfnodeconnline{C}{D}} +\layout Standard + +\backslash +alert<6,10-11,13>{ +\backslash +pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}} +\layout Standard + +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfxy(0,3.3)}{ +\backslash +pgfbox[left,center]{$G +\backslash +colon$}} +\layout Standard + +\layout Standard + +\backslash +only<2->{ +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfxy(0,2.25)}{ +\backslash +pgfbox[left,center]{$G' +\backslash +colon$}} +\layout Standard + +\backslash +graphnode{A1}{ +\backslash +pgfxy(1,2.25)} +\layout Standard + +\backslash +graphnode{B1}{ +\backslash +pgfxy(2,2.25)} +\layout Standard + +\backslash +graphnode{C1}{ +\backslash +pgfxy(3,2.25)} +\layout Standard + +\backslash +graphnode{D1}{ +\backslash +pgfxy(4,2.25)} +\layout Standard + +\layout Standard + +\backslash +graphnode{A2}{ +\backslash +pgfxy(1,1.25)} +\layout Standard + +\backslash +graphnode{B2}{ +\backslash +pgfxy(2,1.25)} +\layout Standard + +\backslash +graphnode{C2}{ +\backslash +pgfxy(3,1.25)} +\layout Standard + +\backslash +graphnode{D2}{ +\backslash +pgfxy(4,1.25)} +\layout Standard + +\backslash +graphnode{A3}{ +\backslash +pgfxy(1,0.25)} +\layout Standard + +\backslash +graphnode{B3}{ +\backslash +pgfxy(2,0.25)} +\layout Standard + +\backslash +graphnode{C3}{ +\backslash +pgfxy(3,0.25)} +\layout Standard + +\backslash +graphnode{D3}{ +\backslash +pgfxy(4,0.25)} +\layout Standard + +\backslash +graphnode{A4}{ +\backslash +pgfxy(1,-.75)} +\layout Standard + +\backslash +graphnode{B4}{ +\backslash +pgfxy(2,-.75)} +\layout Standard + +\backslash +graphnode{C4}{ +\backslash +pgfxy(3,-.75)} +\layout Standard + +\backslash +graphnode{D4}{ +\backslash +pgfxy(4,-.75)} +\layout Standard + { +\backslash +color{white} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{A1}}{ +\backslash +pgfbox[center,center]{$s'$}} +\layout Standard + +\backslash +pgfputat{ +\backslash +pgfnodecenter{D4}}{ +\backslash +pgfbox[center,center]{$t'$}} +\layout Standard + }} +\layout Standard + +\layout Standard + +\backslash +only<8->{ +\layout Standard + +\backslash +pgfsetlinewidth{0.4pt} +\layout Standard + +\backslash +color{beamerexample!25!averagebackgroundcolor} +\layout Standard + +\backslash +pgfnodeconnline{A2}{C1} +\layout Standard + +\backslash +pgfnodeconnline{A2}{D1} +\layout Standard + +\backslash +pgfnodeconnline{B2}{A1} +\layout Standard + +\backslash +pgfnodeconnline{B2}{C1} +\layout Standard + +\backslash +pgfnodeconnline{B2}{D1} +\layout Standard + +\backslash +pgfnodeconnline{C2}{D1} +\layout Standard + +\backslash +pgfnodeconnline{D2}{A1} +\layout Standard + +\backslash +pgfnodeconnline{D2}{B1} +\layout Standard + +\backslash +pgfnodeconnline{A3}{C2} +\layout Standard + +\backslash +pgfnodeconnline{A3}{D2} +\layout Standard + +\backslash +pgfnodeconnline{B3}{A2} +\layout Standard + +\backslash +pgfnodeconnline{B3}{C2} +\layout Standard + +\backslash +pgfnodeconnline{B3}{D2} +\layout Standard + +\backslash +pgfnodeconnline{C3}{D2} +\layout Standard + +\backslash +pgfnodeconnline{D3}{A2} +\layout Standard + +\backslash +pgfnodeconnline{D3}{B2} +\layout Standard + +\backslash +pgfnodeconnline{A4}{C3} +\layout Standard + +\backslash +pgfnodeconnline{A4}{D3} +\layout Standard + +\backslash +pgfnodeconnline{B4}{A3} +\layout Standard + +\backslash +pgfnodeconnline{B4}{C3} +\layout Standard + +\backslash +pgfnodeconnline{B4}{D3} +\layout Standard + +\backslash +pgfnodeconnline{C4}{D3} +\layout Standard + +\backslash +pgfnodeconnline{D4}{A3} +\layout Standard + +\backslash +pgfnodeconnline{D4}{B3} +\layout Standard + +\layout Standard + +\backslash +pgfsetstartarrow{ +\backslash +pgfarrowto} +\layout Standard + +\backslash +pgfnodeconnline{A1}{B1} +\layout Standard + +\backslash +pgfnodeconnline{B1}{C1} +\layout Standard + +\backslash +pgfnodeconnline{C1}{D1} +\layout Standard + +\backslash +pgfnodeconnline{A2}{B2} +\layout Standard + +\backslash +pgfnodeconnline{B2}{C2} +\layout Standard + +\backslash +pgfnodeconnline{C2}{D2} +\layout Standard + +\backslash +pgfnodeconnline{A3}{B3} +\layout Standard + +\backslash +pgfnodeconnline{B3}{C3} +\layout Standard + +\backslash +pgfnodeconnline{C3}{D3} +\layout Standard + +\backslash +pgfnodeconnline{A4}{B4} +\layout Standard + +\backslash +pgfnodeconnline{B4}{C4} +\layout Standard + +\backslash +pgfnodeconnline{C4}{D4} +\layout Standard + +\layout Standard + +\backslash +pgfclearstartarrow +\layout Standard + +\backslash +pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt} +\layout Standard + +\backslash +pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt} +\layout Standard + +\backslash +pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt} +\layout Standard + +\backslash +pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt} +\layout Standard + +\backslash +pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt} +\layout Standard + +\backslash +pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt} +\layout Standard + +\backslash +pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt} +\layout Standard + +\backslash +pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt} +\layout Standard + +\backslash +pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt} +\layout Standard + +\backslash +pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt} +\layout Standard + +\backslash +pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt} +\layout Standard + +\backslash +pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt} +\layout Standard + +\backslash +color{beamerexample} +\layout Standard + +\backslash +pgfsetlinewidth{0.6pt} +\layout Standard + } +\layout Standard + +\layout Standard + +\backslash +only<3->{ +\layout Standard + +\backslash +color<3>{red} +\layout Standard + +\backslash +pgfnodeconnline{B1}{A2} +\layout Standard + +\backslash +pgfnodeconnline{B2}{A3} +\layout Standard + +\backslash +pgfnodeconnline{B3}{A4} +\layout Standard + } +\layout Standard + +\layout Standard + +\backslash +only<4->{ +\layout Standard + +\backslash +color<4>{red} +\layout Standard + +\backslash +pgfnodeconnline{B1}{C2} +\layout Standard + +\backslash +pgfnodeconnline{B2}{C3} +\layout Standard + +\backslash +pgfnodeconnline{B3}{C4} +\layout Standard + } +\layout Standard + +\layout Standard + +\backslash +only<5->{ +\layout Standard + +\backslash +color<5>{red} +\layout Standard + +\backslash +pgfnodeconnline{C1}{D2} +\layout Standard + +\backslash +alert<11>{ +\backslash +pgfnodeconnline{C2}{D3}} +\layout Standard + +\backslash +alert<12-13>{ +\backslash +pgfnodeconnline{C3}{D4}} +\layout Standard + } +\layout Standard + +\layout Standard + +\backslash +only<6->{ +\layout Standard + +\backslash +color<6>{red} +\layout Standard + +\backslash +alert<11>{ +\backslash +pgfnodeconnline{A1}{C2}} +\layout Standard + +\backslash +alert<12-13>{ +\backslash +pgfnodeconnline{A2}{C3}} +\layout Standard + +\backslash +pgfnodeconnline{A3}{C4} +\layout Standard + } +\layout Standard + +\layout Standard + +\backslash +only<7->{ +\layout Standard + +\backslash +color<7>{red} +\layout Standard + +\backslash +alert<12-13>{ +\backslash +pgfnodeconnline{A1}{A2}} +\layout Standard + +\backslash +pgfnodeconnline{A2}{A3} +\layout Standard + +\backslash +pgfnodeconnline{A3}{A4} +\layout Standard + +\backslash +pgfnodeconnline{B1}{B2} +\layout Standard + +\backslash +pgfnodeconnline{B2}{B3} +\layout Standard + +\backslash +pgfnodeconnline{B3}{B4} +\layout Standard + +\backslash +pgfnodeconnline{C1}{C2} +\layout Standard + +\backslash +pgfnodeconnline{C2}{C3} +\layout Standard + +\backslash +pgfnodeconnline{C3}{C4} +\layout Standard + +\backslash +pgfnodeconnline{D1}{D2} +\layout Standard + +\backslash +pgfnodeconnline{D2}{D3} +\layout Standard + +\backslash +alert<11>{ +\backslash +pgfnodeconnline{D3}{D4}} +\layout Standard + } +\layout Standard + +\backslash +end{pgfpicture} +\end_inset + + +\end_deeper +\layout AgainFrame + + +\begin_inset ERT +status Collapsed + +\layout Standard +<6> +\end_inset + +hierarchy +\layout Subsection + +Complexity of: Approximating the Shortest Path +\layout BeginFrame + +Approximators Compute Paths that Are Nearly As Short As a Shortest Path +\layout Definition + +An +\color red +approximation scheme for +\begin_inset Formula $\Lang{tournament-shortest-path}$ +\end_inset + + +\color default + gets as input +\begin_deeper +\layout Enumerate + +a tuple +\begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$ +\end_inset + + and +\layout Enumerate + +a number +\begin_inset Formula $r>1$ +\end_inset + +. +\layout Standard + +It outputs +\layout Itemize + +a path from +\begin_inset Formula $s$ +\end_inset + + to\SpecialChar ~ + +\begin_inset Formula $t$ +\end_inset + + of length at most +\begin_inset Formula $r\operatorname{d_{T}}(s,t)$ +\end_inset + +. +\end_deeper +\layout BeginFrame + +There Exists a Logspace Approximation Scheme for +\newline +the Tournament Shortest Path Problem +\layout Theorem + +There exists an approximation scheme for +\begin_inset Formula $\Lang{tournament-shortest-path}$ +\end_inset + + that for +\begin_inset Formula $1<r<2$ +\end_inset + + needs space +\begin_inset Formula \[ +O\left(\log|V|\log\frac{1}{r-1}\right).\] + +\end_inset + + +\layout Pause + +\layout Corollary + +In tournaments, paths can be constructed in logarithmic space. +\layout Standard + + +\hfill + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +hyperlink{optimality}{ +\backslash +beamergotobutton{More Details}} +\end_inset + + +\layout AgainFrame + + +\begin_inset ERT +status Collapsed + +\layout Standard +<7> +\end_inset + +hierarchy +\layout Section* + +Summary +\layout Subsection* + +Summary +\layout BeginFrame + +Summary +\layout Block + + +\begin_inset ERT +status Inlined + +\layout Standard +{Summary} +\end_inset + + +\begin_deeper +\layout Itemize + +Tournament +\color red +reachability +\color default + is in +\color red + +\begin_inset Formula $\Class{AC}^{0}$ +\end_inset + + +\color default +. + +\layout Itemize + +There exists a +\color red +logspace approximation scheme +\color default + for +\color red +approximating +\color default + shortest paths in tournaments. +\layout Itemize + +Finding +\color red +shortest paths +\color default + in tournaments is +\color red + +\begin_inset Formula $\Class{NL}$ +\end_inset + +-complete +\color default +. +\end_deeper +\layout Separator + +\layout Block + + +\begin_inset ERT +status Inlined + +\layout Standard +{Outlook} +\end_inset + + +\begin_deeper +\layout Itemize + +The same results apply to graphs with +\newline +bounded independence number. +\hfill + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +hyperlink{independence}{ +\backslash +beamergotobutton{More Details}} +\end_inset + + +\layout Itemize + +The complexity of finding paths in undirected graphs +\newline +is partly open. +\hfill + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +hyperlink{undirected}{ +\backslash +beamergotobutton{More Details}} +\end_inset + + +\end_deeper +\layout Subsection* + +For Further Reading +\layout BeginFrame + +For Further Reading +\layout Standard + + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +beamertemplatebookbibitems +\end_inset + + +\layout Bibliography +\bibitem {Moon1968} + +\SpecialChar ~ +John Moon. + +\begin_inset ERT +status Collapsed + +\layout Standard + +\backslash +newblock +\end_inset + + +\emph on +Topics on Tournaments. + +\emph default + +\begin_inset ERT +status Collapsed + +\layout Standard + +\backslash +newblock +\end_inset + + Holt, Rinehart, and Winston, 1968. + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +beamertemplatearticlebibitems +\end_inset + + +\layout Bibliography +\bibitem {NickelsenT2002} + +\SpecialChar ~ +Arfst Nickelsen and Till Tantau. + +\begin_inset ERT +status Collapsed + +\layout Standard + +\backslash +newblock +\end_inset + + On reachability in graphs with bounded independence number. +\begin_inset ERT +status Collapsed + +\layout Standard + +\backslash +newblock +\end_inset + + In +\emph on +Proc. + of COCOON 2002 +\emph default +, Springer-Verlag, 2002. +\layout Bibliography +\bibitem {Tantau2004b} + +\SpecialChar ~ +Till Tantau +\begin_inset ERT +status Collapsed + +\layout Standard + +\backslash +newblock +\end_inset + + A logspace approximation scheme for the shortest path problem for graphs + with bounded independence number. +\begin_inset ERT +status Collapsed + +\layout Standard + +\backslash +newblock +\end_inset + + In +\emph on +Proc. + of STACS 2004 +\emph default +, Springer-Verlag, 2004. + +\begin_inset ERT +status Collapsed + +\layout Standard + +\backslash +newblock +\end_inset + + In press. +\layout EndFrame + +\layout Standard +\start_of_appendix + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +AtBeginSubsection[]{} +\end_inset + + +\layout Section + +Appendix +\layout Subsection + +Graphs With Bounded Independence Number +\layout BeginFrame + + +\begin_inset ERT +status Inlined + +\layout Standard +[label=independence] +\end_inset + +Definition of Independence Number of a Graph +\layout Definition + +The +\color red +independence number +\color default + +\begin_inset Formula $\alpha(G)$ +\end_inset + + of a directed graph +\newline +is the maximum number of vertices we can pick, +\newline +such that there is no edge between them. +\layout Example + +Tournaments have independence number 1. + +\layout BeginFrame + +The Results for Tournaments also Apply to +\newline +Graphs With Bounded Independence Number +\layout Theorem + +For each\SpecialChar ~ + +\begin_inset Formula $k$ +\end_inset + +, +\color red +reachability +\color default + in graphs with independence number +\newline +at most\SpecialChar ~ + +\begin_inset Formula $k$ +\end_inset + + is in +\begin_inset Formula $\Class{AC}^{0}$ +\end_inset + +. +\layout Separator + +\layout Theorem + +For each\SpecialChar ~ + +\begin_inset Formula $k$ +\end_inset + +, there exists a +\color red +logspace approximation scheme +\color default + for approximating the shortest path in graphs with independence number + at most\SpecialChar ~ + +\begin_inset Formula $k$ +\end_inset + + +\layout Separator + +\layout Theorem + +For each\SpecialChar ~ + +\begin_inset Formula $k$ +\end_inset + +, finding the +\color red +shortest path +\color default + in graphs with independence number at most\SpecialChar ~ + +\begin_inset Formula $k$ +\end_inset + + is +\color red + +\begin_inset Formula $\Class{NL}$ +\end_inset + +-complete +\color default +. +\layout Subsection + +Finding Paths in Undirected Graphs +\layout BeginFrame + + +\begin_inset ERT +status Inlined + +\layout Standard +<1-2>[label=undirected] +\end_inset + +The Complexity of Finding Paths in Undirected Graphs +\newline +Is Party Unknown. +\layout Fact + + +\begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$ +\end_inset + + is +\begin_inset Formula $\Class{SL}$ +\end_inset + +-complete. +\layout Corollary + +For undirected graphs, we can solve +\begin_deeper +\layout Itemize + +the reachability problem in logspace iff +\begin_inset Formula $\Class L=\Class{SL}$ +\end_inset + +, +\layout Itemize + +the construction problem in logspace iff +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +alt<1>{?}{ +\backslash +alert{$ +\backslash +Class L = +\backslash +Class{SL}$}} +\end_inset + +, +\layout Itemize + +the optimization problem in logspace iff +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +alt<1>{?}{ +\backslash +alert{$ +\backslash +Class L = +\backslash +Class{NL}$}} +\end_inset + +, +\layout Itemize + +the approximation problem in logspace iff ?. + +\end_deeper +\layout Subsection + +The Approximation Scheme is Optimal +\layout BeginFrame + + +\begin_inset ERT +status Inlined + +\layout Standard +[label=optimality] +\end_inset + +The Approximation Scheme is Optimal +\layout Theorem + +Suppose there exists an approximation scheme for +\begin_inset Formula $\Lang{tournament-shortest-path}$ +\end_inset + + that needs space +\begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$ +\end_inset + +. + Then +\begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$ +\end_inset + +. +\layout Proof + +\begin_deeper +\layout Enumerate + +Suppose the approximation scheme exists. +\newline +We show +\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$ +\end_inset + +. + +\layout Enumerate + +Let +\begin_inset Formula $(T,s,t)$ +\end_inset + + be an input. + Let +\begin_inset Formula $n$ +\end_inset + + be the number of vertices. +\layout Enumerate + +Run the approximation scheme for +\begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$ +\end_inset + +. +\newline +This needs space +\begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$ +\end_inset + +. +\layout Enumerate + +The resulting path has optimal length. + +\begin_inset ERT +status Collapsed + +\layout Standard + +\backslash +qedhere +\end_inset + + +\end_deeper +\layout EndFrame + +\the_end |
