% Journee de rentree du LIAFA
\documentclass{beamer}
%----------------%
% packages <<<
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{lmodern}
\usepackage{amsmath}
%\usepackage{amstheorem}
\usepackage{amssymb}
\usepackage{ifthen,xifthen}
\usepackage{calc}
\usepackage{tikz}
\usetikzlibrary{automata,shapes,fit,calc}
\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{dark_blue}{RGB}{0,0,100}
\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}[5][rectangle]{
\small{
  \node[#1,black,draw] (H1) at (#2,#3) {#4};
  \path[->] (H1) edge ++(0,#5);
}
}
\newcommand{\autotriangle}[3]{
  \filldraw[dark_blue!18,fill opacity=.6,draw=black] (#1,#2) -- ++(-60:#3) -- ++(60:#3) --cycle;
}
\newcommand{\autocircle}[3]{
  \filldraw[yellow!18,fill opacity=.6,draw=black] (#1,#2) circle(#3/2);
}
% >>>>
%----------------%
% New theorems <<<
%\theoremstyle{plain}
\newtheorem{theorems}{Theorems}
\newtheorem{question}{Question}
\newtheorem{conjecture}{Conjecture}
%%%% source : http://tex.stackexchange.com/questions/71265/redefine-block-template-for-beamer-theorem-like-environment
\theoremstyle{example}
\newtheorem*{recall}{Recall}
% >>>
%----------------%
% 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 Aritheoremetic}
\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{Communicating Finite Automata Systems}
%\subtitle{}
\author{Bruno Guillon,\\
Christian Choffrut\\
cotutelle franco-italienne - Giovanni Pighizzini}
\institute{L.I.A.F.A, Universit\'e Paris Diderot - Paris \rom{7}\\
Dipartimento di Informatica, Universit\`a degli studi di Milano}
\date{October 10, 2012}
% >>>

\begin{document}

\begin{frame}
\maketitle
\end{frame}
\subsection*{Recall}
\begin{frame}
\frametitle{Finite Automata}
    \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{3.5}{2}{$q$}{1}}
	  \only<3>{
	    \draw[->,orange,thick] (3,2) -- (2,2);
	    \draw[->,orange,thick] (4,2) -- (5,2);
	    \letterruban{-1,3}{0}{\textcolor{orange}{$\boldsymbol{\dashv}$}}
	    \letterruban{7,3}{0}{\textcolor{orange}{$\boldsymbol{\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$};
	  \only<1>{
	    \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<2>{
	    \path[->]	(q_0)	edge	[bend left=18]	node		{$a$}	(q_1)
			      edge			node	[swap]	{$b$}	(q_2)
		      (q_1)	edge			node		{$a$}	(q_3)
			      edge	[bend left=15]	node		{$b$}	(q_0)
			      edge	[loop above]	node		{$b$}	()
		      (q_2)	edge			node	[swap]	{$a$}	(q_3)
			      edge	[loop below]	node		{$b$}	()
			      edge			node		{$a$}	(q_1);
	  }
	  \only<3>{
	    \path[->]	(q_0)	edge	[bend left=18]	node		{$a$\textcolor{orange}{$:\triangleright$}}	(q_1)
			      edge			node	[swap]	{$b$\textcolor{orange}{$:\triangledown$}}	(q_2)
		      (q_1)	edge			node		{$a$\textcolor{orange}{$:\triangleleft$}}	(q_3)
			      edge	[bend left=15]	node		{$b$\textcolor{orange}{$:\triangleright$}}	(q_0)
			      edge	[loop above]	node		{$b$\textcolor{orange}{$:\triangledown$}}	()
		      (q_2)	edge			node	[swap]	{$a$\textcolor{orange}{$:\triangleright$}}	(q_3)
			      edge	[loop below]	node		{$b$\textcolor{orange}{$:\triangleleft$}}	()
			      edge			node		{$a$\textcolor{orange}{$:\triangleright$}}	(q_1);
	  }
	  }
	\end{tikzpicture}
      \end{center}
    \end{figure}
\end{frame}
\subsection*{Definitions}
\begin{frame}
\frametitle{One input, multiple FAs}
\begin{figure}[h]
  \begin{center}
    \begin{tikzpicture}[scale=1]
      \letterruban{0,2}{7}{$w_\x$}
      \letterruban{-1,2}{0}{$\vdash$}
      \letterruban{8,2}{0}{$\dashv$}
      \phantom{
	\node at (8.5,5.2) {\textcolor{green}{$Accept$}};
      }
      \only<1>{
	\head[circle]{6.5}{4.5}{$q_3$}{-1.5}
	\head[isosceles triangle,shape border rotate=270]{4.5}{.5}{$q_2$}{1.5}
      }
      \only<2>{
	\head[circle]{6.5}{4.5}{$q_2$}{-1.5}
	\head[isosceles triangle,shape border rotate=270]{5.5}{.5}{$q_1$}{1.5}
      }
      \only<3,4>{
	\head[circle]{7.5}{4.5}{$q_1$}{-1.5}
	\head[isosceles triangle,shape border rotate=270]{4.5}{.5}{$q_4$}{1.5}
      }
      \only<4>{
	\draw[thick, red, ->] (5,.5) -- (7.2,4.2);
      }
      \only<5>{
	\head[circle]{6.5}{4.5}{$q_0$}{-1.5}
	\head[isosceles triangle,shape border rotate=270]{3.5}{.5}{$q_3$}{1.5}
      }
      \only<6>{
	\head[circle]{7.5}{4.5}{$q_9$}{-1.5}
	\head[isosceles triangle,shape border rotate=270]{2.5}{.5}{$q_2$}{1.5}
      }
      \only<7->{
	\head[circle]{8.5}{4.5}{$q_5$}{-1.5}
	\head[isosceles triangle,shape border rotate=270]{3.5}{.5}{$q_8$}{1.5}
      }
      \only<8>{
	\node at (8.5,5.2) {\textcolor{green}{$Accept$}};
      }
    \end{tikzpicture}
  \end{center}
\end{figure}
\end{frame}
\begin{frame}
\frametitle{Formally}
Each computing step is composed of:
\begin{enumerate}
  \item<2-> send message ?\hfill $\nu:\ \Sigma\times Q\rightarrow\set{0,1}$
  \item<3-> receive message
  \item<4-> execute transition: \hfill $\delta:\ Q\times\Sigma\times M\rightarrow \mathcal{P}(Q\times\set{-1,0,+1})$,\vsp[0.05]\\
    \hfill where $M=(Q\cup\set{\nil})^k$.
\end{enumerate}
\uncover<5->{
  \vsp[0.15]
  \begin{figure}[h!]
    \begin{center}
      \begin{tikzpicture}[scale=0.6,auto,node distance=0.4\textwidth,initial text=]
	\small{
	  \node[state]	(q_i)			{$q_i$};
	  \node[state]	(q_j)	[right of=q_i]	{$q_j$};
	  \path[->]	(q_i)	edge			node	[sloped]	{$c|M$ : $\triangledown$}	(q_j)
			      edge	[red,thick,->>]	node	[sloped,above]	{$c$}				($(q_i) + (0,2)$);
	}
      \end{tikzpicture}
    \end{center}
  \end{figure}
}
\end{frame}
\subsection*{Examples}
\begin{frame}
\frametitle{Example}
\only<1>{
      \begin{figure}[h]
	\begin{center}
	  \begin{tikzpicture}[scale=0.6,auto,node distance=0.4\textwidth,initial text=]
	    \tiny{
	      \node[state,initial,circle]	(q_0)				{$q^0_0$};
	      \node[state,circle]			(q_1)	[right of=q_0]		{$q^0_1$};
	      \node[state,accepting,circle]		(q_2)	[right of=q_1]		{$q^0_2$};
	      \path[->]	(q_0)	edge	[bend left=18]	node	[sloped]	{$\dashv|$ : $\triangleright$}		(q_1)
				      edge	[bend left=50]	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}$ : $\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,isosceles triangle]	(q_0)				{$q^1_0$};
	      \node[state,isosceles triangle]		(q_f)	[right of=q_0]		{$q^1_f$};
	      \path[->]	(q_0)	edge	[loop below]	node	[sloped]	{$\dashv,a,b|$ : $\triangleright$}		()
%	        			edge	[loop above]	node	[sloped]	{$a|$ : $\triangleright$}		()
%	        			edge	[loop left]	node	[sloped]	{$b|$ : $\triangleright$}		()
				      edge			node	[sloped]	{$\vdash|$ : $\triangledown$}		(q_f)
			      (q_0)	edge	[red,thick,->>]	node	[sloped,above]	{$\vdash$}				($(q_0) + (0,2)$);
	    }
	  \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,.5) edge  node [below,very near end,sloped] {$q^1_0$} (8,4.5);}
	\phantom{
	  \head[circle]{13.5}{4.5}{\tiny\textcolor{green}{$ACCEPT$}}{-1.5}
	  \node at (1,7) {accepted language: $\set{a^nb^n}$};
	  \node at (12,-1) {$1$ message};
	}\only<2>{
	  \head[circle]{.5}{4.5}{$q_0$}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{.5}{.5}{$q_0$}{1.5}
	}\only<3>{
	  \head[circle]{.5}{4.5}{$q_0$}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{.5}{.5}{$q_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<4>{
	  \head[circle]{1.5}{4.5}{\textcolor{blue}{$q_1$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{1.5}{.5}{$q_0$}{1.5}
	}\only<5>{
	  \head[circle]{1.5}{4.5}{\textcolor{blue}{$q_1$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{1.5}{.5}{$q_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<6>{
	  \head[circle]{1.5}{4.5}{$q_0$}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{2.5}{.5}{$q_0$}{1.5}
	}\only<7>{
	  \head[circle]{2.5}{4.5}{\textcolor{blue}{$q_1$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{3.5}{.5}{$q_0$}{1.5}
	}\only<8>{
	  \head[circle]{2.5}{4.5}{$q_0$}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{4.5}{.5}{$q_0$}{1.5}
	}\only<9>{
	  \head[circle]{3.5}{4.5}{\textcolor{blue}{$q_1$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{5.5}{.5}{$q_0$}{1.5}
	}\only<10>{
	  \head[circle]{3.5}{4.5}{$q_0$}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{6.5}{.5}{$q_0$}{1.5}
	}\only<11>{
	  \head[circle]{4.5}{4.5}{\textcolor{blue}{$q_1$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{7.5}{.5}{$q_0$}{1.5}
	}\only<12>{
	  \head[circle]{4.5}{4.5}{$q_0$}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{8.5}{.5}{$q_0$}{1.5}
	}\only<13>{
	  \head[circle]{5.5}{4.5}{\textcolor{blue}{$q_1$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{9.5}{.5}{$q_0$}{1.5}
	}\only<14>{
	  \head[circle]{5.5}{4.5}{$q_0$}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{10.5}{.5}{$q_0$}{1.5}
	}\only<15>{
	  \head[circle]{6.5}{4.5}{\textcolor{blue}{$q_1$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{11.5}{.5}{$q_0$}{1.5}
	}\only<16>{
	  \head[circle]{6.5}{4.5}{$q_0$}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{12.5}{.5}{$q_0$}{1.5}
	}\only<17>{
	  \head[circle]{7.5}{4.5}{\textcolor{blue}{$q_1$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{13.5}{.5}{$q_0$}{1.5}
	}\only<18>{
	  \head[circle]{7.5}{4.5}{\textcolor{blue}{$q_1$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{13.5}{.5}{$q_0$}{1.5}
      %message
	  \path[->,red] (13,.5) edge  node [below,very near end,sloped] {$q_0$} (8,4.5);
	}\only<19>{
	  \head[circle]{7.5}{4.5}{\textcolor{blue}{$q_1$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{13.5}{.5}{$q_0$}{1.5}
	  \draw[green] (7.5,2.5) circle (3ex);
	}\only<20>{
	  \head[circle]{8.5}{4.5}{\textcolor{green}{$q_2$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{13.5}{.5}{$q_f$}{1.5}
	}\only<21>{
	  \head[circle]{9.5}{4.5}{\textcolor{green}{$q_2$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{13.5}{.5}{$q_f$}{1.5}
	}\only<22>{
	  \head[circle]{10.5}{4.5}{\textcolor{green}{$q_2$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{13.5}{.5}{$q_f$}{1.5}
	}\only<23>{
	  \head[circle]{11.5}{4.5}{\textcolor{green}{$q_2$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{13.5}{.5}{$q_f$}{1.5}
	}\only<24>{
	  \head[circle]{12.5}{4.5}{\textcolor{green}{$q_2$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{13.5}{.5}{$q_f$}{1.5}
	}\only<25>{
	  \head[circle]{13.5}{4.5}{\textcolor{green}{$q_2$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{13.5}{.5}{$q_f$}{1.5}
	}\only<26->{
	  \head[circle]{13.5}{4.5}{\tiny\textcolor{green}{$ACCEPT$}}{-1.5}
	  \head[isosceles triangle,shape border rotate=270]{13.5}{.5}{$q_f$}{1.5}
	}
	\only<27>{
	  \node at (1,7) {accepted language $\set{a^nb^n}$};
	  \node at (12,-1) {$1$ message};
	}
      \end{tikzpicture}
    \end{center}
  \end{figure}
}
\end{frame}
\begin{frame}
\frametitle{Over unary alphabets?}
\uncover<2->{
  One may accept $\set{1^{2^n},\ n\in\mathbb{N}}$:
  \begin{figure}[h!]
    \begin{center}\tiny{
      \begin{tikzpicture}[scale=0.5]
%	\tikzstyle{auto1}=[regular polygon,regular polygon sides=3,shape border rotate=180,minimum height=0.8ex,minimum width=0.8ex,black,draw,font=\tiny]
%	\tikzstyle{auto2}=[circle,black,draw,font=\tiny]
	\letterruban{0,0}{7}{$a$}
	\letterruban{-1,0}{0}{$\dashv$}
	\letterruban{8,0}{0}{$\vdash$}
	\draw[ystep=.5,xstep=1,light_grey] (-1,-0.2) grid (9,-11.2);
	\path[->] (-1.3,-.3) edge node [above,left] {time} (-1.3,-11.2);
%	\foreach \i in {0,...,9}{
%	  \path (\i,-\i) ++(-.5,-.5+\i*0.3) node[auto1] {};
%	}
%	\foreach \j in {0,...,4}{
%	  \path (\j,-2*\j) ++(-.5,-.55+\j*0.6) node[auto2] {};
%	  \path (\j,-2*\j) ++(-.5,-1.25+\j*0.6) node[auto2] {};
%	}
%	\foreach \i in {0,...,2}{
%	  \path (8-\i,-2*\i-7) ++(-.5,-.5+\i*0.6) node[auto1] {};
%	  \path (8-\i,-2*\i-7) ++(-.5,-1.2+\i*0.6) node[auto1] {};
%	}
%	\foreach \j in {0,...,4}{
%	  \path (5+\j,-\j-7) ++(-.55,-.55+\j*.3) node[auto2] {};
%	}
%% Automaton 1: triangle
	\foreach \i in {0,...,9}{
	\autotriangle{\i-.75}{-\i*.5-.4}{.5}
	}
	\foreach \i in {0,...,1}{
	\autotriangle{8-\i-.75}{-5-\i-.4}{.5}
	\autotriangle{8-\i-.75}{-5-\i-.9}{.5}
	}
	\autotriangle{5.25}{-7.4}{.5}
	\foreach \i in {0,...,2}{
	\autotriangle{7+\i-.75}{-7.5-\i*.5-.4}{.5}
	}
	\autotriangle{7.25}{-9.4}{.5}
	\autotriangle{7.25}{-9.9}{.5}
	\autotriangle{8.25}{-10.4}{.5}
%% Automaton 2: circle
	\foreach \i in {0,...,4}{
	\autocircle{\i-.5}{-\i-.6}{.4}
	\autocircle{\i-.5}{-\i-1.1}{.4}
	}
	\foreach \i in {0,...,4}{
	\autocircle{5+\i-.5}{-5-\i*.5-.6}{.4}
	}
	\autocircle{8-.5}{-7.5-.6}{.4}
	\autocircle{8-.5}{-7.5-1.1}{.4}
	\autocircle{6.5}{-9.1}{.4}
	\autocircle{7.5}{-9.6}{.4}
	\autocircle{8.5}{-10.1}{.4}
	\autocircle{8.5}{-10.6}{.4}
%% Accept
	\node at (10,-10.6) {\tiny\textcolor{green}{$Accept$}};
%% Messages
	\path[red,->]	(8.15,-5.15)  edge (3.85,-5.15)
			(8.15,-7.65)  edge (5.85,-7.65)
			(8.15,-9.15)  edge (6.85,-9.15)
			(8.15,-10.15) edge (7.85,-10.15);
      \end{tikzpicture}}
    \end{center}
  \end{figure}
  }
\end{frame}

\subsection*{Known results}
\begin{frame}
  \frametitle{Previous results}
  \begin{theorems}[Tomasz Jurdzinski, 1999-2001]
    Notation: \hspace{0.1\textwidth} $dMes_k(f)$\vsp[0.1]
    \begin{itemize}
      \item<2-> $1Mes_k(m+1)\backslash2Mes_k(m)\neq\emptyset$
      \item<3-> $2Mes_2(m+1)\backslash2Mes_k(m)\neq\emptyset$
      \item<4-> $1Mes_k(\litleo{\log\ n})=1Mes_k(\bigo{1})$
      \item<5-> $2Mes_k(\litleo{(\log\log\log\ n)^c})=2Mes_k(\bigo{1})$
    \end{itemize}
  \end{theorems}
\end{frame}
\subsection*{Questions, conjectures\dots}
\begin{frame}
  \frametitle{Conjecture}
  \begin{question}
    \uncover<1->{Which language may be accepted by Communicating FA}%
    \uncover<2->{,\\over unary alphabets}%
    \uncover<3->{,\\with a constant number of messages?}%
  \end{question}
  \uncover<4->{
    \begin{conjecture}
      unary rational languages.
    \end{conjecture}
  }
  \uncover<5->{
    \begin{itemize}
      \item
	\only<5,6>{one-way/two-way}
	\only<7>{\textcolor{dark_green}{one-way}/\textcolor{gray}{two-way}}
	\only<8>{\textcolor{gray}{one-way}/\textcolor{orange}{two-way}}
	\only<9>{\textcolor{gray}{one-way}/\textcolor{dark_green}{two-way}}
      \item<6->
	\only<6>{deterministic/nondeterministic}
	\only<7>{\textcolor{dark_green}{deterministic}/\textcolor{dark_green}{nondeterministic}}
	\only<8>{\textcolor{orange}{deterministic}/\textcolor{orange}{nondeterministic}}
	\only<9>{\textcolor{dark_green}{deterministic}/\textcolor{red}{nondeterministic}}
    \end{itemize}
  }
  \uncover<7>{
    \begin{theorem}[Harrison \& Ibarra, 1968]
      Unary one-way multihead automata accept exactly regular languages.
    \end{theorem}
  }
\end{frame}
\begin{frame}
  \frametitle{Other questions, future work\dots}
  \begin{overlayarea}{\textwidth}{0.4\textheight}
    \begin{itemize}
      \item<1-> Does there exist a gap in the number of messages in the unary case (conjecture: $\log(n)/constant$)
      \item<2-> Influence of nondeterminism (in general case)
    \end{itemize}
  \end{overlayarea}

  \begin{overlayarea}{\textwidth}{0.2\textheight}
    \only<1>{
    \begin{recall}[Jurdzinski]
      General case: $2Mes_k(\litleo{(\log\log\log\ n)^c})=2Mes_k(\bigo{1})$
    \end{recall}
    }
    \only<2->{
    \begin{example}
      non regular language: $\set{1^n\#1^m,/ \gcd(n,m)=1}$ is accepted by nondeterministic $2Mes_2(1)$.
    \end{example}
    }
    %\only<1>{\phantom{\vsp We can nondeterministically accept nonregular language $\set{1^n\#1^m,/ \gcd(n,m)=1}$ with one message.}}
  \end{overlayarea}
  \uncover<4>{\vfill\hfill Thanks for your attention\dots}
\end{frame}

\end{document}
