% $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{colortbl}


%\usepackage{lmodern}
%\usepackage[T1]{fontenc} 


\usepackage{t1enc}
\usepackage{graphicx}


%!%\usepackage{times}
\usefonttheme{structurebold}

\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[russian,english]{babel}
\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps}
\usepackage{amsmath,amssymb}

\newcommand{\hm}[1]{#1\nobreak\discretionary{}{\hbox{\ensuremath{#1}%%
}}{}}%%продолжение команды дублирования знаков при переносе формулы%%%




\setbeamercovered{dynamic}

%
% The following defintions are peculiar to this particular
% presetation. They have nothing to do with the beamer class
%
%1>>>
% The following info should normally be given in your main file:
%

\title{Взвешенный метод полных наименьших квадратов}
\subtitle {(WTLS метод)}

\author{Ирина К. Плеханова\\Научный руководитель:  И.~В. Семушин}
\institute[Кафедра МКИ]{%
  Механико-математический факультет\\
  Ульяновский государственный университет}
\date{Студенческая научная конференция, май 2006}

\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{Оглавление}\tableofcontents[current]}}

\begin{document}

\frame{\titlepage}

%\section*{Outline}
\part{Main Part}
\frame{\frametitle{Оглавление}\tableofcontents[part=1]}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Актуальность}
\subsection{Приложение в химии}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
  \frametitle{Определение концентрации веществ}

  \begin{block}{Проблема}
    Температура $\alert{T}$ и концентрация $\alert{c}$ связаны
    сложной нелинейной зависимостью в неявной форме и измеряются
    с погрешностями
  \end{block}
  
  \vskip-1em

\begin{overprint}

  \onslide<2-4>

  \begin{example}

    \begin{overprint}

    \onslide<2>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
	\pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{nature11}}	&&
	\end{tabular}

    \onslide<3>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
	\pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{nature11}}	
	&&
    	\pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{nature22}}
	\end{tabular}
   
    \onslide<4>
      \vskip0.5em
      \begin{itemize}

      \item
      Для $i=1,2,\ldots, m$ получены измеренные данные 
      $(\tilde c_i, \tilde T_i)$.

      \item
	\alert{Вопрос}: в модельной зависимости данного вида
$$
\alert{x_1}y+\alert{x_2}y^{0.89}+\alert{x_3}y^{1.39} \pm 
\alert{x_4}y^{0.329} \pm \alert{x_5}y^{0.829} \pm 
\alert{x_6}y^{1.329}  = z\,,
$$
где  $ y=(1-T/T_{\text{крит}})$ и $z=c - c_{\text{крит}}$,
	как выбрать вектор $\alert{x}=
      [ \alert{x_1} , \alert{x_2} , \alert{x_3} , \alert{x_4} , \alert{x_5} , \alert{x_6} ]^{\prime}$
      \alert{наилучших} значений параметров ?
      \end{itemize}
    \end{overprint}

  \end{example}

  \onslide<5>
    \begin{block}{Решение}
	Подгонять модельные данные
$\alert{x}=
      [ \alert{x_1} , \alert{x_2} , \alert{x_3} , \alert{x_4} , \alert{x_5} , \alert{x_6} ]^{\prime}$ и 
      $$\boldsymbol{A}\triangleq \left[
\begin{array}{cccccc}
y_1&y_1^{0.89} &y_1^{1.39}&y_1^{0.329}&y_1^{0.829}&y_1^{1.329}\\
\ldots &\ldots &\ldots &\ldots &\ldots  &\ldots \\
y_m&y_m^{0.89} &y_m^{1.39}&y_m^{0.329}&y_m^{0.829}&y_m^{1.329}
\end{array} 
\right], \enspace 
\boldsymbol{z}\triangleq \boldsymbol{A}\alert{x}\,,
$$
определяемые через $ y_i=(1-T_i/T_{\text{крит}})$,
к опытным данным
$\boldsymbol{\tilde A}\triangleq \boldsymbol{A}\bigl|_{T_i=\tilde T_i}$,
$\boldsymbol{\tilde z}\triangleq [z_1,\ldots,z_1]^{\prime}\bigl|_{c_i=\tilde c_i}$,
где
$z_i=c_i - c_{\text{крит}}$.

    \end{block}
\end{overprint}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Приложение в авиации}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frame
{
  \frametitle{Определение траектории самолета}

    \begin{block}{Проблема}
    Координаты $\alert{x}$ и $\alert{y}$ объекта подвержены
    внешним случайным воздействиям среды и измеряются
    с погрешностями
    \end{block}
  
    \vskip-1em

\begin{overprint}

  \onslide<2-23>

  \begin{example}

    \begin{overprint}
    \onslide<2>
       \vskip-1em
	\begin{tabular}{p{3cm}p{4cm}p{3cm}}
	&
	\pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{MIG29}}	
	&
	\end{tabular}

    \onslide<3>
       \vskip-1em
	\begin{tabular}{p{3cm}p{4cm}p{3cm}}
	&
	\pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{MIG29}}	
	&
	\pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{cloudym}}	\end{tabular}
   
    \onslide<4>
       \vskip-1em
	\begin{tabular}{p{3cm}p{4cm}p{3cm}}
	\pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{cloudym'}}	
	&
	\pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{MIG29}}	
	&
	\pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{cloudym}}	
	\end{tabular}

    \onslide<5>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_01}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}

\animate<6-21>

\onslide<6>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_02}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<7>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_03}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<8>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_04}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<9>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_05}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<10>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_06}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<11>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_07}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<12>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_08}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<13>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_09}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<14>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_01}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<15>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_02}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<16>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_03}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<17>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_04}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<18>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_05}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<19>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_06}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<20>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_07}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<21>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_08}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}
\onslide<22>
       \vskip-1em
	\begin{tabular}{p{4cm}p{0.5cm}p{4cm}}
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{rls1_Page_09}}
&&
     \pgfputat{\pgfxy(1,1)}{\includegraphics[height=3.5cm]{irina}}
	\end{tabular}

    \onslide<23>
      \vskip0.5em
      \begin{itemize}
      \item
>>> Таким образом, имеем..
      \item
>>> В чем заключается конкретный вопрос (проблема) ?
      \end{itemize}
    \end{overprint}

  \end{example}

  \onslide<24>
    \begin{block}{Решение}
>>> Предлагается...

    \end{block}
  \end{overprint}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Формулировка задачи и метода}
\subsection{1111}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{2222}

\subsection{3333}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Математическое моделирование}
\subsection{4444}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{5555}

\subsection{6666}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Заключение и выводы}

\end{document}
%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%




\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}}}}






%%%\pgfdeclareimage[width=1cm]{logo}{usu-logo.eps}
\logo{%
\vbox{\hbox to 1cm{\hfil{\includegraphics[width=0.6cm]{usu-logo.eps}}}%
\vskip0.1cm\hbox{\includegraphics[width=1cm]{usu-logo.eps}}}%
}

\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}

%2>>>
\subsection[Our Model]{Our Model of Absolutely No Space Overhead}

%3>>>
\section[Power of the Model]{The Power of Overhead-Free Computation}

\subsection{Palindromes}

%4>>>

\subsection{Linear Languages}

%5>>>

\subsection[Forbidden Subword]{Context-Free Languages with a Forbidden Subword}

%6>>>

\subsection[Complete Languages]{Languages Complete for Polynomial Space}

%7>>>

\section[Limitations of the Model]{Limitations of Overhead-Free Computation}

\subsection[Strict Inclusion]{Linear Space is Strictly More Powerful}


%8>>>

\section*{Summary}

\subsection<presentation>*{Summary}

%9>>>

\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}
%10>>>

\subsection{Abbreviations}


\end{document}


%1>>>

\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}%
}

%1>>>

%2>>>
\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}

%2>>>

%3>>>
\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}

%3>>>

%4>>>
\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}
%4>>>


%5>>>
\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}

%5>>>

%6>>>
\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}

%6>>>

%7>>>
\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}

%7>>>

%8>>>
\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}

%8>>>

%9>>>
\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}


%9>>>

%10>>>
\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}

%10>>>