% M2-internship repport: preamble
\documentclass{beamer}
%----------------%
% packages <<<
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage{lmodern}
\usepackage{amsmath}
%\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{ifthen,xifthen}
\usepackage{calc}
\usepackage{tikz}
\usetikzlibrary{automata}
\usepackage{chngpage}% allows for temporary adjustment of side margins
%\usepackage{latexsym}%why ?
\usepackage{lipsum}%for modification on elsarticle class
% >>>
%----------------%
% theme beamer <<<<
%\usebeamertheme{}
% >>>>
%----------------%
% Colors <<<<
\definecolor{light_green}{RGB}{100,206,100}
\definecolor{dark_green}{RGB}{0,100,0}
\definecolor{light_blue}{RGB}{135,206,255}
\definecolor{light_red}{RGB}{255,135,100}
\definecolor{light_grey}{RGB}{180,180,180}
\definecolor{dark_grey}{RGB}{130,130,130}
% >>>>
%----------------%
% draw commands <<<<
\newcommand{\emptyruban}[2]{
  \foreach \x in {0,...,#2}{
    \path (#1) ++(\x,0) coordinate (A);
    \draw (A) rectangle +(1,1);
  }
}
\newcommand{\letterruban}[3]{
  \small{
    \foreach \x in {0,...,#2}{
      \path (#1) ++(\x,0) coordinate (A);
      \draw (A) rectangle +(1,1);
      \path (A) ++(.5,.5) coordinate (B);
      \node at (B) {$#3$};
    }
  }
}
\newcommand{\head}[4]{
  \small{
    \node[rectangle,black,draw] (H1) at (#1,#2) {$#3$};
    \path[->] (H1) edge ++(0,#4);
  }
}
% >>>>
%----------------%
% New theorems <<<
\newtheorem{thm}{Th\'eoreme}
\newtheorem{thms}{Th\'eoremes}
\newtheorem{qst}{Question}
%\newtheorem{definition}{Definition}
%\newtheorem{property}{Property}
\newtheorem{lem}{Lemme}
%\newtheorem{remark}{Remark}
\newtheorem{cor}{Corollaire}
\newtheorem{conj}{Conjecture}
% >>>
%----------------%
% text, editor utils <<<
\newcommand{\brefb}[1]{(\ref{#1})}%bracket ref
\newcommand{\vsp}[1][0.01]{\vspace{#1\textheight}}
\newcommand{\todo}[1][!]{
  ~\\ \noindent
  \begin{adjustwidth}{-0.2\textwidth}{-0.1\textwidth}
    \textcolor{blue}{
      \begin{tabular}{||l | p{1.2\textwidth} ||}
	\hline\hline
	\textbf{TO DO:}	&	#1\\
	\hline\hline
      \end{tabular}
    }
  \end{adjustwidth}
}
\newcommand{\name}[1]{\mbox{#1}}
\newcommand{\ie}{\ensuremath{i.e.}}
\newcommand{\resp}{\ensuremath{resp.}}
\newcommand{\Wlog}[1][W]{#1ithout loss of generality}
\renewcommand{\iff}{if and only if}
\newcommand*{\rom}[1]{\MakeUppercase{\romannumeral #1}}
\newcommand{\voc}[1]{#1}
% >>>
%----------------%
% Math <<<
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\interval}[1]{\left[#1\right]}
\newcommand{\seq}[1]{\left\{#1\right\}}
\newcommand{\card}[1]{\left|#1\right|}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\fracphantom}{\vphantom{\frac{0}{1}}}
\DeclareMathOperator{\lcm}{lcm}
\newcommand{\bigo}[1]{\mathcal{O}\left(#1\right)}
\newcommand{\litleo}[1]{o\left(#1\right)}
% >>>
%----------------%
% Names <<<
\newcommand{\tally}{\ensuremath{Tally}}
\newcommand{\Prefix}{\ensuremath{Prefix}}
\newcommand{\Wait}{\ensuremath{Wait}}
\newcommand{\Loop}{\ensuremath{Loop}}
\newcommand{\onoff}{m}%\ensuremath{ON/OFF}}
\newcommand{\dset}{\set{-1,0,+1}}
\newcommand{\nextborder}{\ensuremath{nextborder}}
\newcommand{\nil}{\ensuremath{Nil}}
\newcommand{\Right}{\ensuremath{RIGHT}}
\newcommand{\Left}{\ensuremath{LEFT}}
\newcommand{\presbarith}{Presburger Arithmetic}
\newcommand{\presbform}{Presburger Formula}
% >>>
%----------------%
% Machines <<<
%% general				%% deterministic				%% nondeterministic
\newcommand{\fa}{\ensuremath{FA}}	\newcommand{\dfa}{\ensuremath{DFA}}		\newcommand{\nfa}{\ensuremath{NFA}}
\newcommand{\ufa}{\ensuremath{UFA}}	\newcommand{\udfa}{\ensuremath{UDFA}}		\newcommand{\unfa}{\ensuremath{UNFA}}
\newcommand{\sufa}{\ensuremath{SUFA}}	\newcommand{\sudfa}{\ensuremath{SUDFA}}		\newcommand{\sunfa}{\ensuremath{SUNFA}}
					\newcommand{\tsudfa}{\ensuremath{TSUDFA}}
\newcommand{\fas}{\ensuremath{FAS}}	\newcommand{\dfas}{\ensuremath{DFAS}}		\newcommand{\nfas}{\ensuremath{NFAS}}
\newcommand{\ufas}{\ensuremath{UFAS}}	\newcommand{\udfas}{\ensuremath{UDFAS}}		\newcommand{\unfas}{\ensuremath{UNFAS}}
					\newcommand{\tsudfas}{\ensuremath{TSUDFAS}}
% >>>
%----------------%
% hyphenation <<<<
\hyphenation{dif-fe-rent be-ha-vior}
% >>>>
%----------------%
% titlepage definitions <<<
\title{Syst\`eme d'automates communiquants}
\subtitle{soutenance de stage M2 - PENSUNS - (Mars-Ao\^ut 2012)}
\author{Bruno Guillon,\\
dirig\'e par Christian Choffrut}
\institute{L.I.A.F.A, Universit\'e Paris \rom{7}, 2 pl. Jussieu, 75251 Paris, France}
\date{7 septembre 2012}
% >>>

\begin{document}

\begin{frame}
  \maketitle
\end{frame}
\section{Introduction}
\subsection*{Rappels}
\begin{frame}
  \frametitle{Encore des automates finis}
  On sait ce qu'est un automate fini
  \begin{columns}
    \begin{column}{0.5\textwidth}
      \begin{itemize}
	\item<4-> d\'eterministe/non-d\'eterministe
	\item<5-> uni/bi-directionnel
      \end{itemize}
    \end{column}
    \begin{column}{0.5\textwidth}
      \begin{figure}[h]
	\begin{center}
	  \begin{tikzpicture}[scale=0.6]
	    \phantom{
	      \letterruban{-1,3}{0}{\textcolor{orange}{\dashv}}
	      \letterruban{7,3}{0}{\textcolor{orange}{\vdash}}
	    }
	    \letterruban{0,3}{6}{w_\x}
	    \only<1>{\head{2.5}{2}{q_3}{1}}
	    \only<2>{\head{3.5}{2}{q_1}{1}}
	    \only<3,4>{\head{4.5}{2}{q_2}{1}}
	    \only<5>{
	      \head{3.5}{2}{q_8}{1}
	      \draw[->,orange] (3,2) -- (2,2);
	      \draw[->,orange] (4,2) -- (5,2);
	      \letterruban{-1,3}{0}{\textcolor{orange}{\dashv}}
	      \letterruban{7,3}{0}{\textcolor{orange}{\vdash}}
	    }
	  \end{tikzpicture}
	\end{center}
      \end{figure}
      \begin{figure}[h]
	\begin{center}
	  \begin{tikzpicture}[scale=0.6,node distance=0.3\textwidth,auto,initial text=]
	    \tikzstyle{initial}=[initial by arrow]
	    \tiny{
	    \node[state,initial]	(q_0)				{$q_0$};
	    \node[state] 		(q_1)	[above right of=q_0]	{$q_1$};
	    \node[state]		(q_2)	[below right of=q_0]	{$q_2$};
	    \node[state,accepting]	(q_3)	[below right of=q_1]	{$q_3$};
	    \path[->]	(q_0)	edge			node		{$a$}	(q_1)
	   			edge			node	[swap]	{$b$}	(q_2)
			(q_1)	edge			node		{$a$}	(q_3)
				edge	[loop above]	node		{$b$}	()
			(q_2)	edge			node	[swap]	{$a$}	(q_3)
				edge	[loop below]	node		{$b$}	();
	    \only<4>{
	      \path[->] (q_2) edge node {$a$} (q_1);
	    }
	    }
	  \end{tikzpicture}
	\end{center}
      \end{figure}
    \end{column}
  \end{columns}
\end{frame}
\subsection*{Syst\`emes communiquants}
\subsubsection*{D\'efinition}
\begin{frame}
  \frametitle{Plusieurs automates}
  \begin{figure}[h]
    \begin{center}
      \begin{tikzpicture}[scale=1]
	\letterruban{0,2}{7}{w_\x}
	\node at (8.8,2.5) {\dots};
	\only<1>{
	  \head{.5}{.5}{q^1_1}{1.5}
	  \head{.5}{4.5}{q^2_2}{-1.5}
	}
	\only<2>{
	  \head{1.5}{.5}{q^1_2}{1.5}
	  \head{1.5}{4.5}{q^2_4}{-1.5}
	}
	\only<3>{
	  \head{2.5}{.5}{q^1_2}{1.5}
	  \head{1.5}{4.5}{q^2_3}{-1.5}
	}
	\only<4>{
	  \head{1.5}{.5}{q^1_7}{1.5}
	  \head{2.5}{4.5}{q^2_5}{-1.5}
	}
	\only<5>{
	  \head{2.5}{.5}{q^1_5}{1.5}
	  \head{3.5}{4.5}{q^2_1}{-1.5}
	}
	\only<6>{
	  \head{1.5}{.5}{q^1_3}{1.5}
	  \head{4.5}{4.5}{q^2_6}{-1.5}
	}
	\only<7,8>{
	  \head{2.5}{.5}{q^1_9}{1.5}
	  \head{5.5}{4.5}{q^2_2}{-1.5}
	}
	\only<8>{
	  \draw[thick,red,->] (5,4.5) -- (3,.5);
	}
	\only<9>{
	  \head{3.5}{.5}{q^1_0}{1.5}
	  \head{6.5}{4.5}{q^2_7}{-1.5}
	}
	\only<10>{
	  \head{4.5}{.5}{q^1_3}{1.5}
	  \head{5.5}{4.5}{q^2_6}{-1.5}
	}
	\only<11>{
	  \head{5.5}{.5}{q^1_2}{1.5}
	  \head{7.5}{4.5}{q^2_8}{-1.5}
	}
	\only<12>{
	  \head{4.5}{.5}{q^1_4}{1.5}
	  \head{7.5}{4.5}{q^2_1}{-1.5}
	}
      \end{tikzpicture}
    \end{center}
  \end{figure}
\end{frame}
\begin{frame}
  \frametitle{Formellement}
  Chaque automate a un \'etat.
  Un pas de calcul~:
  \begin{itemize}
    \item<2-> d\'ecision de l'envoi d'un message par une fonction binaire $\nu$
      \begin{itemize}
	\item<3-> envoi (broadcast) \'eventuel du message (\'etat,caract\`ere lu)
      \end{itemize}
    \item<4-> r\'eception des messages
    \item<5-> transition selon une fonction $\delta$\\\pause
      (\'etat,caract\`ere lu,message) $\rightarrow$ (\'etat,d\'eplacement)
  \end{itemize}
\end{frame}
\subsubsection*{Exemples}
\begin{frame}
  \frametitle{Exemple}
  \only<1>{
	\begin{figure}[h]
	  \begin{center}
	    \begin{tikzpicture}[scale=0.6,auto,node distance=0.4\textwidth,initial text=]
	      \tiny{
	        \node[state,initial]	(q_0)				{$q^0_0$};
	        \node[state]		(q_1)	[right of=q_0]		{$q^0_1$};
	        \node[state,accepting]	(q_2)	[right of=q_1]		{$q^0_2$};
		\path[->]	(q_0)	edge	[bend left]	node	[sloped]	{$\dashv,a|$ : $\triangleright|$}		(q_1)
%	    				edge			node	[sloped]	{$a|$ : $\triangleright|$}			(q_1)
				(q_1)	edge	[bend left]	node	[sloped]	{$a|$ : $\triangledown|$}			(q_0)
					edge			node	[sloped]	{$b|\textcolor{red}{(q^1_0,\vdash)}$ : $\triangleright|$}		(q_2)
				(q_2)	edge	[loop below]	node	[sloped]	{$b|$ : $\triangleright|$}			();
	      }
	    \end{tikzpicture}
	  \end{center}
	\end{figure}
	\begin{figure}[h]
	  \begin{center}
	    \begin{tikzpicture}[scale=0.6,node distance=0.3\textwidth,auto,initial text=]
	      \tiny{
	        \node[state,initial]	(q_0)				{$q^1_0$};
	        \node[state]		(q_f)	[right of=q_0]		{$q^1_f$};
	        \path[->]		(q_0)	edge	[loop below]	node	[sloped]	{$\dashv,a,b|$ : $\triangleright|$}		()
	      					edge			node	[sloped]	{$\vdash|$ : $\triangledown|\textcolor{red}{(q^1_0,\vdash)}$}	(q_f);
	      }
	    \end{tikzpicture}
	  \end{center}
	\end{figure}
  }
  \only<2->{
    \begin{figure}[h]
      \begin{center}
	\begin{tikzpicture}[scale=0.7,auto]
	  \letterruban{0,2}{0}{\vdash}
	  \letterruban{1,2}{5}{a}
	  \letterruban{7,2}{5}{b}
	  \letterruban{13,2}{0}{\dashv}
	  \vphantom{\path[->,red] (13,4.5) edge  node [below,very near end,sloped] {$(q^1_0,\dashv)$} (8,.5);}
	  \phantom{
	    \head{13.5}{.5}{\textcolor{green}{ACCEPT}}{1.5}
	    \node at (1,7) {langage accept\'e~: $\set{a^nb^n}$};
	    \node at (12,-1) {$1$ message};
	  }
	  \only<+>{
	    \head{.5}{.5}{q^0_0}{1.5}
	    \head{.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{.5}{.5}{q^0_0}{1.5}
	    \head{.5}{4.5}{q^1_0}{-1.5}
	  %no message
	    \path[->,red] (1.5,.5) edge node [right] {~$\nil$} (1,.5);
	    \path[->,red] (1.5,4.5) edge node [right] {~$\nil$} (1,4.5);
	  }\only<+>{
	    \head{1.5}{.5}{\textcolor{blue}{q^0_1}}{1.5}
	    \head{1.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{1.5}{.5}{\textcolor{blue}{q^0_1}}{1.5}
	    \head{1.5}{4.5}{q^1_0}{-1.5}
	    \path[->,red] (2.5,.5) edge node [right] {~$\nil$} (2,.5);
	    \path[->,red] (2.5,4.5) edge node [right] {~$\nil$} (2,4.5);
	  }\only<+>{
	    \head{1.5}{.5}{q^0_0}{1.5}
	    \head{2.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{2.5}{.5}{\textcolor{blue}{q^0_1}}{1.5}
	    \head{3.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{2.5}{.5}{q^0_0}{1.5}
	    \head{4.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{3.5}{.5}{\textcolor{blue}{q^0_1}}{1.5}
	    \head{5.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{3.5}{.5}{q^0_0}{1.5}
	    \head{6.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{4.5}{.5}{\textcolor{blue}{q^0_1}}{1.5}
	    \head{7.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{4.5}{.5}{q^0_0}{1.5}
	    \head{8.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{5.5}{.5}{\textcolor{blue}{q^0_1}}{1.5}
	    \head{9.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{5.5}{.5}{q^0_0}{1.5}
	    \head{10.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{6.5}{.5}{\textcolor{blue}{q^0_1}}{1.5}
	    \head{11.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{6.5}{.5}{q^0_0}{1.5}
	    \head{12.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{7.5}{.5}{\textcolor{blue}{q^0_1}}{1.5}
	    \head{13.5}{4.5}{q^1_0}{-1.5}
	  }\only<+>{
	    \head{7.5}{.5}{\textcolor{blue}{q^0_1}}{1.5}
	    \head{13.5}{4.5}{q^1_0}{-1.5}
	%message
	    \path[->,red] (13,4.5) edge  node [below,very near end,sloped] {$(q^1_0,\dashv)$} (8,.5);
	  }\only<+>{
	    \head{7.5}{.5}{\textcolor{blue}{q^0_1}}{1.5}
	    \head{13.5}{4.5}{q^1_0}{-1.5}
	    \draw[green] (7.5,2.5) circle (3ex);
	  }\only<+>{
	    \head{8.5}{.5}{\textcolor{green}{q^0_2}}{1.5}
	    \head{13.5}{4.5}{q^1_f}{-1.5}
	  }\only<+>{
	    \head{9.5}{.5}{\textcolor{green}{q^0_2}}{1.5}
	    \head{13.5}{4.5}{q^1_f}{-1.5}
	  }\only<+>{
	    \head{10.5}{.5}{\textcolor{green}{q^0_2}}{1.5}
	    \head{13.5}{4.5}{q^1_f}{-1.5}
	  }\only<+>{
	    \head{11.5}{.5}{\textcolor{green}{q^0_2}}{1.5}
	    \head{13.5}{4.5}{q^1_f}{-1.5}
	  }\only<+>{
	    \head{12.5}{.5}{\textcolor{green}{q^0_2}}{1.5}
	    \head{13.5}{4.5}{q^1_f}{-1.5}
	  }\only<+>{
	    \head{13.5}{.5}{\textcolor{green}{q^0_2}}{1.5}
	    \head{13.5}{4.5}{q^1_f}{-1.5}
	  }\only<+->{
	    \head{13.5}{.5}{\textcolor{green}{ACCEPT}}{1.5}
	    \head{13.5}{4.5}{q^1_f}{-1.5}
	  }
	  \only<+>{
	    \node at (1,7) {langage accept\'e~: $\set{a^nb^n}$};
	    \node at (12,-1) {$1$ message};
	  }
	\end{tikzpicture}
      \end{center}
    \end{figure}
  }
\end{frame}
\begin{frame}
  \frametitle{Et Bidirectionnels ? Et sur un alphabet unaire ?}
  \uncover<2->{
    On reconnait $\set{1^{2^n},\ n\in\mathbb{N}}$:
    \begin{figure}[h]
      \begin{center}
	\begin{tikzpicture}[scale=1]
	  \only<+->{
	    \letterruban{1,2}{7}{a}
	    \letterruban{0,2}{0}{\dashv}
	    \letterruban{9,2}{0}{\vdash}
	    \phantom{\head{9.5}{.5}{\textcolor{green}{ACCEPT}}{1.5}}
	    \phantom{\node at (9,-1) {$\log(n)$ messages};i}
	  }
	  \only<+>{
	    \head{.5}{4.5}{q^1_0}{-1.5}
	    \head{.5}{.5}{q^0_0}{1.5}
	  }\only<+>{
	    \head{1.5}{4.5}{q^1_0}{-1.5}
	    \head{.5}{.5}{q^0_{0'}}{1.5}
	  }\only<+>{
	    \head{2.5}{4.5}{q^1_0}{-1.5}
	    \head{1.5}{.5}{q^0_{0}}{1.5}
	  }\only<+>{
	    \head{3.5}{4.5}{q^1_0}{-1.5}
	    \head{1.5}{.5}{q^0_{0'}}{1.5}
	  }\only<+>{
	    \head{9.5}{4.5}{q^1_0}{-1.5}
	    \head{4.5}{.5}{q^0_{0'}}{1.5}
	  }\only<+>{
	    \head{9.5}{4.5}{q^1_0}{-1.5}
	    \head{4.5}{.5}{q^0_{0'}}{1.5}
	    \draw[->,red] (9,4.5) -- (5,.5);
	  }\only<+>{
	    \head{8.5}{4.5}{\textcolor{blue}{q^1_1}}{-1.5}
	    \head{5.5}{.5}{q^0_1}{1.5}
	  }\only<+>{
	    \head{8.5}{4.5}{\textcolor{blue}{q^1_{1'}}}{-1.5}
	    \head{6.5}{.5}{q^0_1}{1.5}
	  }\only<+>{
	    \head{7.5}{4.5}{\textcolor{blue}{q^1_{1}}}{-1.5}
	    \head{7.5}{.5}{q^0_1}{1.5}
	  }\only<+>{
	    \head{7.5}{4.5}{\textcolor{blue}{q^1_{1'}}}{-1.5}
	    \head{8.5}{.5}{q^0_1}{1.5}
	  }\only<+>{
	    \head{6.5}{4.5}{\textcolor{blue}{q^1_{1}}}{-1.5}
	    \head{9.5}{.5}{q^0_1}{1.5}
	  }\only<+>{
	    \head{6.5}{4.5}{\textcolor{blue}{q^1_{1}}}{-1.5}
	    \head{9.5}{.5}{q^0_1}{1.5}
	    \draw[->,red] (9,.5) -- (7,4.5);
	  }\only<+>{
	    \head{7.5}{4.5}{q^1_{0}}{-1.5}
	    \head{8.5}{.5}{\textcolor{blue}{q^0_{0}}}{1.5}
	  }\only<+->{
	    \head{9.5}{4.5}{q^1_{0}}{-1.5}
	    \head{9.5}{.5}{\textcolor{green}{ACCEPT}}{1.5}
	  }
	  \only<+>{
	    \node at (9,-1) {$\log(n)$ messages};
	  }
	\end{tikzpicture}
      \end{center}
    \end{figure}
  }
\end{frame}

\subsubsection*{R\'esultats connus}
\begin{frame}
  \frametitle{Influence du nombre de message}
  \begin{thms}[Tomasz Jurdzinski]
    \begin{itemize}
      \item<+-> $1Mes_k(m)\subsetneq 2Mes_k(m+1)$
      \item<+-> $2Mes_2(m)\subsetneq 2Mes_k(m-1)$
      \item<+-> si $f(n)=\litleo{\log\ n}$ et $f(n)=\omega(1)$
	alors il n'existe pas de syst\`eme \textcolor{blue}{unidirectionnel}
	qui utilise $f(n)$ messages.
      \item<+-> il existe une constante $c$ telle que\\
	si $f(n)=\litleo{(\log\log\log\ n)^c}$ et $f(n)=\omega(1)$
	alors il n'existe pas de syst\`eme \textcolor{blue}{bidirectionnel}
	qui utilise $f(n)$ messages.
    \end{itemize}
  \end{thms}
\end{frame}
\subsubsection*{Questions et conjectures}
\begin{frame}
  \frametitle{Conjecture}
  \begin{qst}
    Qu'acceptent les \fas\
    \uncover<3->{\textcolor{blue}{unaire}}
    \uncover<2->{avec un nombre \textcolor{red}{constant} de communications ?}
  \end{qst}
  \uncover<4->{
    \begin{conj}
      les langages rationnels (unaire).
    \end{conj}
  }
  \uncover<5->{
    \begin{itemize}
      \item\only<5,6>{unidirectionnel/bidirectionnel}
	\only<7>{\textcolor{dark_green}{unidirectionnel}/\textcolor{gray}{bidirectionnel}}
	\only<8>{\textcolor{gray}{unidirectionnel}/\textcolor{orange}{bidirectionnel}}
	\only<9>{\textcolor{gray}{unidirectionnel}/\textcolor{dark_green}{bidirectionnel}}
    \end{itemize}
  }
  \uncover<6->{
    \begin{itemize}
      \item\only<6>{d\'eterministe/non-d\'eterministe}
	\only<7>{\textcolor{dark_green}{d\'eterministe}/\textcolor{dark_green}{non-d\'eterministe}}
	\only<8>{\textcolor{orange}{d\'eterministe}/\textcolor{orange}{non-d\'eterministe}}
	\only<9>{\textcolor{dark_green}{d\'eterministe}/\textcolor{red}{non-d\'eterministe}}
    \end{itemize}
  }
  \uncover<7>{
    \begin{thm}[Harrison \& Ibarra]
      Si un langage est accept\'e par un automate unaire unidirectionnel \`a tête multiple
      alors il est r\'egulier.
    \end{thm}
  }
\end{frame}

\section{R\'esultat principal}
\subsection*{Plan de la preuve}
\begin{frame}
  \frametitle{Plan de la preuve}
  \begin{itemize}
    \item<2-> on introduit un mod\`ele simplifi\'e~: \tsudfas
    \item<3-> on simule n'importe quel syst\`eme unaire unidirectionnel d\'eterministe par un \tsudfas (sans trop augmenter le nombre de message).
    \item<4-> on montre que les \tsudfas\ avec un nombre constant de messages reconnaissent exactement les langages rationnels
  \end{itemize}
\end{frame}

\subsection*{Comportements d\'eterministes sur un alphabet unaire}

\begin{frame}
  \frametitle{Comportements d\'eterministes sur un alphabet unaire}
  \begin{overlayarea}{\textwidth}{0.2\textheight}
    \vsp
    La seule chose qui compte~:\\
    \uncover<2->{\flushright \textcolor{blue}{la taille du mot.}}
  \end{overlayarea}
  \begin{overlayarea}{\textwidth}{0.6\textheight}
    \vsp
    \only<3>{
      \begin{figure}[h]
	\begin{center}
	  \begin{tikzpicture}[scale=0.5]
	    \letterruban{0,2}{0}{\dashv}
	    \letterruban{1,2}{1}{a}
	    \node at (4,2.5) {\dots};
	    \letterruban{5,2}{5}{a}
	    \node at (12,2.5) {\dots};
	    \letterruban{13,2}{1}{a}
	    \letterruban{15,2}{0}{\dashv}
	    \head{7.5}{.5}{q}{1.5}
	  \end{tikzpicture}
	\end{center}
      \end{figure}
    }
    \only<4->{
      \begin{figure}[h]
	\begin{center}
	  \begin{tikzpicture}[scale=0.6,auto]
	    \letterruban{-.5,2.5}{0}{\dashv}
	    \letterruban{.5,2.5}{11}{a}
	    \node at (13.5,3) {\ldots};
	    \path[->] (-1,2.5) edge node [very near end,swap] {\tiny temps} (-1,-1.9);
%	  \letterruban{12.5,2.5}{0}{\vdash}
	    \only<5>{
	      \draw[smooth] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (2,2) (1,1.9) (2,1.8) (3,1.7) (4,1.6) (3,1.5) (4,1.4) (4,1.3) (5,1.2) (4,1.1) (3,1) (4,.9) (3,.8) (2,.7) (1,.6) (2,.5) (2,.5) (1,.4) (0,.3)};
	    }
	    \only<6>{
	      \draw[smooth] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (1,2) (2,1.9) (2,1.8) (3,1.7) (4,1.6) (3,1.5) (4,1.4) (4,1.3) (5,1.2) (4,1.1) (3,1) (4,.9) (3,.8) (3,.7) (4,.6) (4,.5) (5,.4) (4,.3) (3,.2) (4,.1) (3,0) (3,-.1) (4,-.2) (4,-.3) (5,-.4) (4,-.5) (3,-.6) (4,-.7) (3,-.8) (3,-.9) (4,-1) (4,-1.1) (5,-1.2) (4,-1.3) (3,-1.4) (4,-1.5) (3,-1.6) (3,-1.7) (4,-1.8)}; 
	    }
	    \only<7>{
	      \draw[smooth] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (2,2) (1,1.9) (2,1.8) (2,1.7) (3,1.6) (3,1.6) (4,1.5) (5,1.4) (4,1.3) (4,1.2) (5,1.1) (6,1) (5,.9) (5,.8) (6,.7) (7,.6) (6,.5) (6,.4) (7,.3) (8,.2) (7,.1) (7,0) (8,-.1) (9,-.2) (8,-.3) (8,-.4) (9,-.5) (9,-.5) (10,-.6)};
	    }
	  \end{tikzpicture}
	\end{center}
      \end{figure}
    }
  \end{overlayarea}
\end{frame}

\subsection*{\tsudfas}
\begin{frame}
  \frametitle{Simulation des 2\udfas\ par \tsudfas}
  \uncover<1->{
    \only<1,2,3,4>{\textcolor{black}{Tri-Phase}}%
    \only<6->{\textcolor{black}{Tri-Phase}}%
    \only<5>{\textcolor{blue}{Tri-Phase}}
    \only<1,2,3,5>{\textcolor{black}{Sweeping}}%
    \only<6->{\textcolor{black}{Sweeping}}%
    \only<4>{\textcolor{blue}{Sweeping}}
    \only<1,2,4,5>{\textcolor{black}{Unary}}%
    \only<6->{\textcolor{black}{Unary}}%
    \only<3>{\textcolor{blue}{Unary}}
    \only<1,3,4,5>{\textcolor{black}{Deterministic Finite Automata System}}%
    \only<6->{\textcolor{black}{Deterministic Finite Automata System}}%
    \only<2>{\textcolor{blue}{Deterministic Finite Automata System}}
  }
  \uncover<6->{
    \begin{figure}[h]
      \begin{center}
	\begin{tikzpicture}[scale=0.6,auto]
	  \letterruban{-.5,2.5}{0}{\dashv}
	  \letterruban{.5,2.5}{11}{a}
	  \node at (13.5,3) {\ldots};
	  \path[->] (-1,2.5) edge node [very near end,swap] {\tiny temps} (-1,-1.9);
%	  \letterruban{12.5,2.5}{0}{\vdash}
	  \only<7>{
	    \draw[smooth] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (1,2) (2,1.9) (2,1.8) (3,1.7) (4,1.6) (3,1.5) (4,1.4) (4,1.3) (5,1.2) (4,1.1) (3,1) (4,.9) (3,.8) (3,.7) (4,.6) (4,.5) (5,.4) (4,.3) (3,.2) (4,.1) (3,0) (3,-.1) (4,-.2) (4,-.3) (5,-.4) (4,-.5) (3,-.6) (4,-.7) (3,-.8) (3,-.9) (4,-1) (4,-1.1) (5,-1.2) (4,-1.3) (3,-1.4) (4,-1.5) (3,-1.6) (3,-1.7) (4,-1.8)}; 
	  }
	  \only<8>{
	    \draw[smooth,opacity=0.7] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (1,2) (2,1.9) (2,1.8) (3,1.7) (4,1.6) (3,1.5) (4,1.4) (4,1.3) (5,1.2) (4,1.1) (3,1) (4,.9) (3,.8) (3,.7) (4,.6) (4,.5) (5,.4) (4,.3) (3,.2) (4,.1) (3,0) (3,-.1) (4,-.2) (4,-.3) (5,-.4) (4,-.5) (3,-.6) (4,-.7) (3,-.8) (3,-.9) (4,-1) (4,-1.1) (5,-1.2) (4,-1.3) (3,-1.4) (4,-1.5) (3,-1.6) (3,-1.7) (4,-1.8)}; 
	    \draw[dark_green,dashed] (0,2.3) -- (5,1.8);
	    \draw[green,dashed] (5,1.8) -- (5,1.2);
	    \draw[blue,dashed] (5,1.2) -- (5,-1.8);
	  }
	  \only<9>{
	    \draw[smooth] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (2,2) (1,1.9) (2,1.8) (2,1.7) (3,1.6) (3,1.6) (4,1.5) (5,1.4) (4,1.3) (4,1.2) (5,1.1) (6,1) (5,.9) (5,.8) (6,.7) (7,.6) (6,.5) (6,.4) (7,.3) (8,.2) (7,.1) (7,0) (8,-.1) (9,-.2) (8,-.3) (8,-.4) (9,-.5) (9,-.5) (10,-.6)};
	  }
	  \only<10>{
	    \draw[smooth,opacity=0.7] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (2,2) (1,1.9) (2,1.8) (2,1.7) (3,1.6) (3,1.6) (4,1.5) (5,1.4) (4,1.3) (4,1.2) (5,1.1) (6,1) (5,.9) (5,.8) (6,.7) (7,.6) (6,.5) (6,.4) (7,.3) (8,.2) (7,.1) (7,0) (8,-.1) (9,-.2) (8,-.3) (8,-.4) (9,-.5) (9,-.5) (10,-.6)};
	    \draw[dark_green,dashed] (0,2.3) -- (5,1.7);
	    \draw[green,dashed] (5,1.7) -- (5,1.4);
	    \draw[blue,dashed] (5,1.4) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1);
	  }
	  \only<11>{
	    \draw[smooth] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (2,2) (1,1.9) (2,1.8) (3,1.7) (4,1.6) (3,1.5) (4,1.4) (4,1.3) (5,1.2) (4,1.1) (3,1) (4,.9) (3,.8) (2,.7) (1,.6) (2,.5) (2,.5) (1,.4) (0,.3)};
	  }
	  \only<12>{
	    \draw[smooth,gray] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (2,2) (1,1.9) (2,1.8) (3,1.7) (4,1.6) (3,1.5) (4,1.4) (4,1.3) (5,1.2) (4,1.1) (3,1) (4,.9) (3,.8) (2,.7) (1,.6) (2,.5) (2,.4) (1,.3) (0,.2)};
	    \draw[smooth] plot coordinates{(0,.2) (1,.1) (2,0) (2,-.1) (1,-.2) (2,-.3) (3,-.4) (4,-.5) (3,-.6) (4,-.7) (4,-.8) (5,-.9) (4,-1) (3,-1.1) (4,-1.2) (3,-1.3) (2,-1.4) (1,-1.5) (2,-1.6) (2,-1.7) (1,-1.8) (0,-1.9)};
	  }
	  \only<13>{
	    \draw[smooth,opacity=0.7] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (2,2) (1,1.9) (2,1.8) (3,1.7) (4,1.6) (3,1.5) (4,1.4) (4,1.3) (5,1.2) (4,1.1) (3,1) (4,.9) (3,.8) (2,.7) (1,.6) (2,.5) (2,.4) (1,.3) (0,.2)};
	    \draw[smooth,opacity=0.7] plot coordinates{(0,.2) (1,.1) (2,0) (2,-.1) (1,-.2) (2,-.3) (3,-.4) (4,-.5) (3,-.6) (4,-.7) (4,-.8) (5,-.9) (4,-1) (3,-1.1) (4,-1.2) (3,-1.3) (2,-1.4) (1,-1.5) (2,-1.6) (2,-1.7) (1,-1.8) (0,-1.9)};
	    \draw[dark_green] (0,2.3) -- (5,1.7);
	    \draw[green] (5,1.7) -- (5,.2);
	    \draw[blue] (5,.2) -- (5,-1.8);
	  }
	  \only<14>{
	    \draw[smooth,gray] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (2,2) (1,1.9) (2,1.8) (3,1.7) (4,1.6) (3,1.5) (4,1.4) (4,1.3) (5,1.2) (4,1.1) (3,1) (4,.9) (3,.8) (2,.7) (1,.6) (2,.5) (2,.4) (1,.3) (0,.2)};
	    \draw[smooth,black] plot coordinates{(0,.2) (1,.1) (2,0) (2,-.1) (1,-.2) (2,-.3) (2,-.4) (3,-.5) (3,-.6) (4,-.7) (5,-.8) (4,-.9) (4,-1) (5,-1.1) (6,-1.2) (5,-1.3) (5,-1.4) (6,-1.5) (7,-1.6) (6,-1.7) (6,-1.8) (7,-1.9)};
	  }
	  \only<15>{
	    \draw[smooth,gray] plot coordinates{(0,2.3) (1,2.2) (2,2.1) (2,2) (1,1.9) (2,1.8) (3,1.7) (4,1.6) (3,1.5) (4,1.4) (4,1.3) (5,1.2) (4,1.1) (3,1) (4,.9) (3,.8) (2,.7) (1,.6) (2,.5) (2,.4) (1,.3) (0,.2)};
	    \draw[smooth,black] plot coordinates{(0,.2) (1,.1) (2,0) (2,-.1) (1,-.2) (2,-.3) (2,-.4) (3,-.5) (3,-.6) (4,-.7) (5,-.8) (4,-.9) (4,-1) (5,-1.1) (6,-1.2) (5,-1.3) (5,-1.4) (6,-1.5) (7,-1.6) (6,-1.7) (6,-1.8) (7,-1.9)};
	    \draw[dark_green] (0,2.3) -- (5,1.7);
	    \draw[green] (5,1.7) -- (5,-.8);
	    \draw[blue] (5,-.8)  -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1);
	  }
	\end{tikzpicture}
      \end{center}
    \end{figure}
  }
\end{frame}

\begin{frame}
  \frametitle{Simulation \`a partir du milieu}
  \begin{figure}[h]
    \begin{center}
      \begin{tikzpicture}[scale=0.8]
	\letterruban{-1.5,2.5}{7}{a}
	\node at (-2,3) {\dots};
	\node at (7,3) {\dots};
	\draw[thick,red] (4,2.3) circle (1ex);
	\only<1>{
	  \draw[smooth] plot coordinates{(4,2.3) (5,2.2) (5,2.1) (6,2) (5,1.9) (5,1.8) (4,1.7) (3,1.6) (3,1.5) (2,1.4) (3,1.3) (2,1.2) (1,1.1) (2,1) (1,.9) (0,.8) (1,.7) (0,.6) (-1,.5)};
	}
	\only<2->{
	  \draw[smooth,opacity=0.7] plot coordinates{(4,2.3) (5,2.2) (5,2.1) (6,2) (5,1.9) (5,1.8) (4,1.7) (3,1.6) (3,1.5) (2,1.4) (3,1.3) (2,1.2) (1,1.1) (2,1) (1,.9) (0,.8) (1,.7) (0,.6) (-1,.5)};
	}
	\only<2>{
	  \draw[dark_green,dashed] (4,2.3) -- (3,2.1);
	  \draw[green,dashed] (3,2.1) -- (3,1.5);
	  \draw[blue,dashed] (3,1.5) -- ++(-1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(-1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(-1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(-1,-.1);
	}
	\only<3->{
	  \draw[dark_green,dashed] (4,2.3) -- (6,2.1);
	  \draw[green,dashed] (6,2.1) -- ++(0,-.1);
	}
	\only<4->{
	  \draw[thick,red] (6,2) circle (1ex);
	}
	\only<5->{
	  \draw[dark_green] (6,2) -- ++(-3,-.3);
	  \draw[green] (3,1.7) -- ++(0,-.2);
	  \draw[blue,dashed] (3,1.5) -- ++(-1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(-1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(-1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(-1,-.1);
	}
      \end{tikzpicture}
    \end{center}
  \end{figure}
  \uncover<6->{
    \flushright ajoute $1$ message
  }
\end{frame}

\begin{frame}
  \frametitle{R\'eception d'un message}
  \begin{figure}[h]
    \begin{center}
      \begin{tikzpicture}[scale=0.8]
	\letterruban{-1.5,4.5}{7}{a}
	\node at (-2,5) {\dots};
	\node at (7,5) {\dots};
	\phantom{
	  \draw[smooth] plot coordinates{(-1,4.2) (0,4.1) (1,4) (0,3.9) (0,3.8) (1,3.7) (2,3.6) (1,3.5) (1,3.4) (2,3.3) (3,3.2) (2,3.1) (2,3) (3,2.9) (4,2.8) (3,2.7) (3,2.6) (4,2.5) (5,2.4) (4,2.3)};
	  \draw[smooth] plot coordinates{(4,2.3) (5,2.2) (5,2.1) (6,2) (5,1.9) (5,1.8) (4,1.7) (3,1.6) (3,1.5) (2,1.4) (3,1.3) (2,1.2) (1,1.1) (2,1) (1,.9) (0,.8) (1,.7) (0,.6) (-1,.5)};
	}
	%simulated trajectoriies <<<
	\only<1,2,4>{%before message
	  \draw[smooth] plot coordinates{(-1,4.2) (0,4.1) (1,4) (0,3.9) (0,3.8) (1,3.7) (2,3.6) (1,3.5) (1,3.4) (2,3.3) (3,3.2) (2,3.1) (2,3) (3,2.9) (4,2.8) (3,2.7) (3,2.6) (4,2.5) (5,2.4) (4,2.3)};
	}
	\only<3>{%after message
	  \draw[smooth] plot coordinates{(4,2.3) (5,2.2) (5,2.1) (6,2) (5,1.9) (5,1.8) (4,1.7) (3,1.6) (3,1.5) (2,1.4) (3,1.3) (2,1.2) (1,1.1) (2,1) (1,.9) (0,.8) (1,.7) (0,.6) (-1,.5)};
	}
	\only<3,5->{%before message opacity=0.7
	  \draw[smooth,opacity=0.7] plot coordinates{(-1,4.2) (0,4.1) (1,4) (0,3.9) (0,3.8) (1,3.7) (2,3.6) (1,3.5) (1,3.4) (2,3.3) (3,3.2) (2,3.1) (2,3) (3,2.9) (4,2.8) (3,2.7) (3,2.6) (4,2.5) (5,2.4) (4,2.3)};
	}
	\only<9->{%after message opacity=0.7
	  \draw[smooth,opacity=0.7] plot coordinates{(4,2.3) (5,2.2) (5,2.1) (6,2) (5,1.9) (5,1.8) (4,1.7) (3,1.6) (3,1.5) (2,1.4) (3,1.3) (2,1.2) (1,1.1) (2,1) (1,.9) (0,.8) (1,.7) (0,.6) (-1,.5)};
	}
	%>>>
	%messages <<<
	\only<2,3,4,5,8->{%simulated message
	  \coordinate (MR1) at (4,2.3);
	  \draw[thick,red] (MR1) circle (1ex);
	}
	\only<6,7,8,11>{%simulating message 1
	  \coordinate (M1) at (5,2.3);
	  \draw[thick,red] (M1) circle (1ex);
	}
	%>>>
	%simulating trajectories<<<
	\only<5,6,7,8,11>{
	  \draw[blue,dashed] (-1,4.5) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(1,-.1) -- ++(0,-.1) -- ++(0,-.1);
	}
	\only<7,8,11>{
	  \draw[thick,red,->] (M1) -- (MR1);
	}
	\only<10->{
	  \draw[dark_green,dashed] (4,2.3) -- (6,2.1);
	  \draw[green,dashed] (6,2.1) -- ++(0,-.1);
	}
	\only<10->{
	  \draw[thick,red] (6,2) circle (1ex);
	}
	\only<10->{
	  \draw[dark_green] (6,2) -- ++(-3,-.3);
	  \draw[green] (3,1.7) -- ++(0,-.2);
	  \draw[blue,dashed] (3,1.5) -- ++(-1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(-1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(-1,-.1) -- ++(0,-.1) -- ++(0,-.1) -- ++(-1,-.1);
	}
	%>>>
      \end{tikzpicture}
    \end{center}
  \end{figure}
  \uncover<11->{
    ajoute $2$ messages
  }
\end{frame}
\subsection*{Les \tsudfas\ acceptent exactement les langages rationnels}

\begin{frame}
  \frametitle{\`A quoi \c ca sert ?}
  \begin{thm}
    \begin{tabular}{lcr}
      \begin{tabular}{l}
	$\mathcal{L}$ reconnu par un \tsudfas\\
	avec un nombre constant de messages
      \end{tabular}
      & $\Rightarrow$ & $\mathcal{L}$ rationnel
    \end{tabular}
  \end{thm}
\end{frame}

\begin{frame}
  \frametitle{Tout est plus simple}
  \begin{lem}
    Soit $A$ une composante d'un \tsudfas.\pause\\
    Soit $q$ un \'etat\pause\ et $d$ sa direction associ\'ee.\pause\\
    Il existe $\pi_1 < \pi_2$ \pause\ et $\Delta < \omega$ tels que\\\pause
    si $A$ fait $s$ pas de calcul depuis une position $p$\pause\\
    sans recevoir de messages\pause\ et sans atteindre un bord\pause, 
    alors:\\
    \begin{itemize}
      \item<+-> si $s<\pi_1$ alors sa position est $p+d*s$
      \item<+-> si $\pi_1<s<\pi_2$ alors sa position est $p+\pi_1*d$
      \item<+-> si $\pi_2<s$ alors sa position est\\
	$p+(\pi_1+\left\lceil (s-\pi_2)*\frac{\Delta}{\omega}\right\rceil)*d$
    \end{itemize}
  \end{lem}
  \uncover<12->{
    \begin{cor}
      Combien d'\'etapes avant le prochain marqueur de fin ?
      \begin{itemize}
	\item<+-> $d=+1\ \Rightarrow\ \alpha*(n-p)+\beta$
	\item<+-> $d=-1\ \Rightarrow\ \alpha*p+\beta$
      \end{itemize}
    \end{cor}
  }
\end{frame}

\begin{frame}
  \frametitle{Des \'ev\'enements particuliers}
  \begin{lem}
    Entre deux messages il y a un nombre fini de configuration au bords.
  \end{lem}
  \pause
  \vsp
  \begin{cor}
    Nombre fini de message $\Rightarrow$ nombre fini d'\'ev\'enement particulier
  \end{cor}
\end{frame}

\begin{frame}
  \frametitle{Tout est affine}
  \begin{figure}[h]
    \begin{center}
      \begin{tikzpicture}[scale=0.5,auto]
	\letterruban{0,2.5}{0}{\dashv}
	\letterruban{1,2.5}{5}{a}
	\node at (8,3) {\dots};
	\letterruban{9,2.5}{5}{a}
	\letterruban{15,2.5}{0}{\vdash}
	\phantom{
	  \node at (8,-7) {apr\`es un nombre constant de pas de calcul};
	  \node at (8,-8) {expression affine des positions (resp. \'etats) de chaque automate};
	  \node at (6,-9) {\'etats connus selon congruence de $n$};
	}
	\only<1>{
	  \head{0.5}{1}{1}{1.5}
	  \head{0.5}{0}{2}{.5}
	  \head{0.5}{-1}{3}{.5}
	  \path[opacity=0,white,->] (0.5,-1) edge node [sloped,opacity=1,black] {\dots} (0.5,-3);
	  \head{0.5}{-4}{k}{.5}
	}
	\only<2>{
	  \head{1.5}{1}{1}{1.5}
	  \head{1.5}{0}{2}{.5}
	  \head{1.5}{-1}{3}{.5}
	  \head{1.5}{-4}{k}{2.5}
	}
	\only<3>{
	  \head{2.5}{1}{1}{1.5}
	  \head{1.5}{0}{2}{2.5}
	  \head{1.5}{-1}{3}{.5}
	  \head{2.5}{-4}{k}{4.5}
	}
	\only<4>{
	  \head{3.5}{1}{1}{1.5}
	  \head{1.5}{0}{2}{2.5}
	  \head{2.5}{-1}{3}{3.5}
	  \head{2.5}{-4}{k}{2.5}
	}
	\only<5>{
	  \head{4.5}{1}{1}{1.5}
	  \head{2.5}{0}{2}{2.5}
	  \head{2.5}{-1}{3}{.5}
	  \head{3.5}{-4}{k}{6.5}
	}
	\only<6>{
	  \head{5.5}{1}{1}{1.5}
	  \head{3.5}{0}{2}{2.5}
	  \head{2.5}{-1}{3}{3.5}
	  \head{4.5}{-4}{k}{6.5}
	}
	\only<7>{
	  \head{5.5}{1}{1}{1.5}
	  \head{4.5}{0}{2}{2.5}
	  \head{2.5}{-1}{3}{3.5}
	  \head{5.5}{-4}{k}{4.5}
	}
	\only<8-11>{
	  \head{6.5}{1}{1}{1.5}
	  \head{4.5}{0}{2}{2.5}
	  \head{3.5}{-1}{3}{3.5}
	  \head{6.5}{-4}{k}{4.5}
	}
	\only<9-11>{
	  \draw[red,thick,->] (H1) -- ++(90:2);
	  \draw[red,thick,->] (H1) -- ++(115:2);
	  \draw[red,thick,->] (H1) -- ++(135:2);
	  \draw[red,thick,dotted,->] (H1) -- ++(160:2);
	  \node at (10,-6.5) {\textcolor{red}{apr\`es un nombre constant de pas de calcul}};
	}
	\only<10,11>{
	  \node at (8,-8) {expression affine des positions de chaque automate};
	}
	\only<11>{
	  \node at (5,-9) {\'etats connus};
	}
	\only<12->{
	  \head{15.5}{1}{1}{1.5}
	  \head{6.5}{0}{2}{2.5}
	  \head{14.5}{-1}{3}{3.5}
	  \head{11.5}{-4}{k}{6.5}
	  \node at (10,-6.5) {\textcolor{red}{apr\`es $\alpha*n+\beta$ pas de calcul}};
	}
	\only<13,14>{
	  \node at (8,-8) {expression affine des positions de chaque automate};
	}
	\only<14>{
	  \node at (6,-9) {\'etats connus selon congruence de $n$};
	}
      \end{tikzpicture}
    \end{center}
  \end{figure}
\end{frame}


\section*{Conclusion}
\begin{frame}
  \frametitle{Conclusion}
  Les 2\udfas\ acceptent exactement les langages rationnels.\pause\\\vsp
  Ce n'est pas encore le r\'esultat esp\'er\'e.\pause\\\vsp
  Objets simples, mais comportement complexes\dots
\end{frame}

\begin{frame}
  \frametitle{Questions ouvertes}
  \begin{itemize}
    \item<2-4> Le cas non-d\'eterministe ? 
      \uncover<3>{(conjecture : rationnel)}\\
      \begin{itemize}
	\item<4-> Seul l'envoi des messages est non-d\'eterministe ?
      \end{itemize}
    \item<5,6> Y-a-t-il des langages unaire qui requiert $\litleo{\log n}$ et $\omega(1)$ ?\pause\ 
      \uncover<6>{(conjecture non)}
    \item<7> Influence du nombre d'automates dans le cas unaire ?
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Merci pour votre attention}
  Avez-vous des questions ?
\end{frame}

\end{document}
