% Time-stamp: <expose.tex   3 Oct 2006 14:09:26>

% L'option xcolor=pst est nécessaire pour pstricks
\documentclass[xcolor=pst]{beamer}

\usefonttheme{serif}
\usetheme{Madrid}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amscd}
\usepackage{pstricks}
\usepackage{gastex}
\usepackage{fancybox}

% Théorèmes, propositions, ...
\newtheorem{prop}{Proposition}
%\theoremstyle{example}
%\newtheorem{exemple}[theorem]{Exemple}
%\newtheorem{exemples}[theorem]{Exemples}

% emptyset
\renewcommand{\emptyset}{\varnothing}
% Entiers
\newcommand{\N}{\mathbb{N}}
% Ensemble des coodonnées nulles
\newcommand{\zero}{\operatorname{Null}}
% Familles de relations rationnelles
\newcommand{\Rat}{\operatorname{Rat}}
\newcommand{\DRat}{\operatorname{DRat}}
\newcommand{\Sync}{\operatorname{Sync}}
\newcommand{\Rec}{\operatorname{Rec}}

% Titre court et titre en entier
\title[Decidability of rational relations]{
       Decidability of some classes \\[2mm] 
       of rational relations}

% Auteurs
\author[Olivier Carton]{Olivier Carton, \\[2mm] 
        Christian Choffrut, Serge Grigorieff}

% Instituts
\institute[LIAFA]{
  LIAFA, CNRS \\
  Universit\'e Paris 7
}

% Date 
\date{Szeged 2006}

% Logo du LIAFA
\pgfdeclareimage[width=0.4cm]{liafa}{liafa}
\logo{\pgfuseimage{liafa}}

\begin{document}
%\thicklines
\frame{\titlepage}

\frame{\tableofcontents}

\section{Introduction}

\section{Automata}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Automates (vision machine de Turing)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{$n$-tapes automata (as Turing machines)}

  Run on the input 
  $(cabca, bba, aabcbc)\in A_1^*\times A_2^*\times A_3^*$

  \begin{center}
    \begin{pspicture}(10,3.5)
      % Contrôle
      \psframe[framearc=.1](0,1.3)(1.8,2.5)
      \rput[B](0.9,1.8){$Q$}
      % Première bande
      \rput(4,2.4){%
        % Bande
        \multips(0,0)(0.5,0){6}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.15){$c$}
        \rput[B](0.75,0.15){$a$}
        \rput[B](1.25,0.15){$b$}
        \rput[B](1.75,0.15){$c$}
        \rput[B](2.25,0.15){$a$}
        \rput[B](2.75,0.15){$\#$}
        % Tête de lecture
        % Partie fixe
        \psline(-2.2,-0.2)(-1,-0.2)(-1,0.8)
        % Partie variable
        \only<1>{%
          \psline[arrows=->](-1,0.8)(0.25,0.8)(0.25,0.5)
          \psframe(0,0)(0.5,0.5)
        }%
        \only<2-4>{%
          \psline[arrows=->](-1,0.8)(0.75,0.8)(0.75,0.5)
          \psframe(0.5,0)(1,0.5)
        }%
        \only<5-6>{%
          \psline[arrows=->](-1,0.8)(1.25,0.8)(1.25,0.5)
          \psframe(1,0)(1.5,0.5)
        }%
        \only<7-12>{%
          \psline[arrows=->](-1,0.8)(1.75,0.8)(1.75,0.5)
          \psframe(1.5,0)(2,0.5)
        }%
        \only<13>{%
          \psline[arrows=->](-1,0.8)(2.25,0.8)(2.25,0.5)
          \psframe(2,0)(2.5,0.5)
        }%
        \only<14->{%
          \psline[arrows=->](-1,0.8)(2.75,0.8)(2.75,0.5)
          \psframe(2.5,0)(3,0.5)
        }%
      }
      % Deuxième bande
      \rput(4,1.2){%
        % Bande
        \multips(0,0)(0.5,0){4}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.1){$b$}
        \rput[B](0.75,0.1){$b$}
        \rput[B](1.25,0.1){$a$}
        \rput[B](1.75,0.1){$\#$}
        % Tête de lecture
        % Partie fixe
        \psline(-2.2,0.8)(-1,0.8)
        % Partie variable
        \only<1-5>{%
          \psline[arrows=->](-1,0.8)(0.25,0.8)(0.25,0.5)
          \psframe(0,0)(0.5,0.5)
        }%
        \only<6-11>{%
          \psline[arrows=->](-1,0.8)(0.75,0.8)(0.75,0.5)
          \psframe(0.5,0)(1,0.5)
        }%
        \only<12-14>{%
          \psline[arrows=->](-1,0.8)(1.25,0.8)(1.25,0.5)
          \psframe(1,0)(1.5,0.5)
        }%
        \only<15>{%
          \psline[arrows=->](-1,0.8)(1.75,0.8)(1.75,0.5)
          \psframe(1.5,0)(2,0.5)
        }%
      }
      % Troisième bande
      \rput(4,0){%
        % Bande
        \multips(0,0)(0.5,0){7}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.1){$a$}
        \rput[B](0.75,0.1){$a$}
        \rput[B](1.25,0.1){$b$}
        \rput[B](1.75,0.1){$c$}
        \rput[B](2.25,0.1){$b$}
        \rput[B](2.75,0.1){$c$}
        \rput[B](3.25,0.1){$\#$}
        % Tête de lecture
        % Partie fixe
        \psline(-2.2,1.8)(-1,1.8)(-1,0.8)
        % Partie variable
        \only<1-2>{%
          \psline[arrows=->](-1,0.8)(0.25,0.8)(0.25,0.5)
          \psframe(0,0)(0.5,0.5)
        }%
        \only<3>{%
          \psline[arrows=->](-1,0.8)(0.75,0.8)(0.75,0.5)
          \psframe(0.5,0)(1,0.5)
        }%
        \only<4-7>{%
          \psline[arrows=->](-1,0.8)(1.25,0.8)(1.25,0.5)
          \psframe(1,0)(1.5,0.5)
        }%
        \only<8>{%
          \psline[arrows=->](-1,0.8)(1.75,0.8)(1.75,0.5)
          \psframe(1.5,0)(2,0.5)
        }%
        \only<9>{%
          \psline[arrows=->](-1,0.8)(2.25,0.8)(2.25,0.5)
          \psframe(2,0)(2.5,0.5)
        }%
        \only<10>{%
          \psline[arrows=->](-1,0.8)(2.75,0.8)(2.75,0.5)
          \psframe(2.5,0)(3,0.5)
        }%
        \only<11->{%
          \psline[arrows=->](-1,0.8)(3.25,0.8)(3.25,0.5)
          \psframe(3,0)(3.5,0.5)
        }%
      }
    \end{pspicture}
  \end{center}
  \begin{itemize}
  \item unique control (non deterministic)
  \item read-only heads
  \item No backwards move of the heads
  \item stop on the end-markers
  \end{itemize}
\end{frame}

%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% % Automates à n bandes (vision automates)
%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% \begin{frame}
%%   \frametitle{$n$-tapes automata (as automata)}
  
%%   Automaton on the monoid $M = A_1^* \times\cdots\times A_n^*$ with
%%   transitions of the following form
%%   \begin{center}
%%     \gasset{Nh=6,Nw=6}
%%     \begin{picture}(60,12)(0,-5)
%%       \node(p)(0,0){$p$}
%%       \node(q)(50,0){$q$}
%%       \drawedge[curvedepth=2](p,q){$(\varepsilon,\ldots,\varepsilon,a,\varepsilon,\ldots,\varepsilon)$}
%%     \end{picture}
%%   \end{center}

%%   \begin{theorem}[Kleene]
%%     A relation $R \subseteq M$ is accepted by an automaton  iff
%%     it is rational (described by a rational expression).
%%   \end{theorem}
  
%%   The set of rational relations is denoted by \alert{$\Rat(M)$}.
%% \end{frame}

\subsection{Deterministic automata}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Automates déterministes
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Deterministic $n$-tapes automata}

  \begin{center}
    \begin{pspicture}(10,3.2)
      % Contrôle
      \psframe[framearc=.1](0,1.3)(1.8,2.5)
      \rput[B](0.9,1.8){$Q$}
      % Première bande
      \rput(4,2.4){%
        % Bande
        \multips(0,0)(0.5,0){6}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.15){$c$}
        \rput[B](0.75,0.15){$a$}
        \rput[B](1.25,0.15){$b$}
        \rput[B](1.75,0.15){$c$}
        \rput[B](2.25,0.15){$a$}
        \rput[B](2.75,0.15){$\#$}
        % Tête de lecture
        \psline[arrows=->](-2.2,-0.2)(-1,-0.2)(-1,0.8)(1.75,0.8)(1.75,0.5)
        \psframe(1.5,0)(2,0.5)
      }
      % Deuxième bande
      \rput(4,1.2){%
        % Bande
        \multips(0,0)(0.5,0){4}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.1){$b$}
        \rput[B](0.75,0.1){$b$}
        \rput[B](1.25,0.1){$a$}
        \rput[B](1.75,0.1){$\#$}
        % Tête de lecture
        \psline[arrows=->](-2.2,0.8)(-1,0.8)(0.75,0.8)(0.75,0.5)
        \psframe(0.5,0)(1,0.5)
      }
      % Troisième bande
      \rput(4,0){%
        % Bande
        \multips(0,0)(0.5,0){7}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.1){$a$}
        \rput[B](0.75,0.1){$a$}
        \rput[B](1.25,0.1){$b$}
        \rput[B](1.75,0.1){$c$}
        \rput[B](2.25,0.1){$b$}
        \rput[B](2.75,0.1){$c$}
        \rput[B](3.25,0.1){$\#$}
        % Tête de lecture
        \psline[arrows=->](-2.2,1.8)(-1,1.8)(-1,0.8)(2.75,0.8)(2.75,0.5)
        \psframe(2.5,0)(3,0.5)
      }
    \end{pspicture}
  \end{center}
  \begin{itemize}
  \item \alert{deterministic} control 
  \item end-markers (as automata)
  \end{itemize}

  \begin{examples}
    \begin{itemize}
    \item $\{(a^n,b^n) \mid n \ge 0\}$ et $\{(a^n,b^{2n}) \mid n \ge 0\}$
      are deterministic
    \item $\{(a^n,b^n) \mid n \ge 0\} \cup \{(a^n,b^{2n}) \mid n \ge 0\}$
      is not deterministic
    \end{itemize}
  \end{examples}
  The set of relations accepted by deterministic automata is denoted
  \alert{$\DRat(M)$}.
\end{frame}

\subsection{Synchronous automata}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Automates synchrones
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Synchronous $n$-tapes automata}

  \begin{center}
    \begin{pspicture}(10,2.5)(0,1)
      % Contrôle
      \psframe[framearc=.1](0,1.3)(1.8,2.5)
      \rput[B](0.9,1.8){$Q$}
      % Première bande
      \rput(4,1.7){%
        % Bande
        \multips(0,0)(0.5,0){7}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.15){$c$}
        \rput[B](0.75,0.15){$a$}
        \rput[B](1.25,0.15){$b$}
        \rput[B](1.75,0.15){$c$}
        \rput[B](2.25,0.15){$a$}
        \rput[B](2.75,0.15){$\#$}
        \rput[B](3.25,0.15){$\#$}
        % Tête de lecture
        % Partie fixe
        \psline(-2.2,0.2)(-1,0.2)(-1,0.8)
        % Partie variable
        \only<1>{%
          \psline[arrows=->](-1,0.8)(0.25,0.8)(0.25,0.5)
          \psframe(0,-1)(0.5,0.5)
        }%
        \only<2>{%
          \psline[arrows=->](-1,0.8)(0.75,0.8)(0.75,0.5)
          \psframe(0.5,-1)(1,0.5)
        }%
        \only<3>{%
          \psline[arrows=->](-1,0.8)(1.25,0.8)(1.25,0.5)
          \psframe(1,-1)(1.5,0.5)
        }%
        \only<4>{%
          \psline[arrows=->](-1,0.8)(1.75,0.8)(1.75,0.5)
          \psframe(1.5,-1)(2,0.5)
        }%
        \only<5>{%
          \psline[arrows=->](-1,0.8)(2.25,0.8)(2.25,0.5)
          \psframe(2,-1)(2.5,0.5)
        }%
        \only<6>{%
          \psline[arrows=->](-1,0.8)(2.75,0.8)(2.75,0.5)
          \psframe(2.5,-1)(3,0.5)
        }%
        \only<7>{%
          \psline[arrows=->](-1,0.8)(3.25,0.8)(3.25,0.5)
          \psframe(3,-1)(3.5,0.5)
        }%
      }
      % Deuxième bande
      \rput(4,1.2){%
        % Bande
        \multips(0,0)(0.5,0){7}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.1){$b$}
        \rput[B](0.75,0.1){$b$}
        \rput[B](1.25,0.1){$a$}
        \rput[B](1.75,0.1){$\#$}
        \rput[B](2.25,0.1){$\#$}
        \rput[B](2.75,0.1){$\#$}
        \rput[B](3.25,0.1){$\#$}
      }
      % Troisième bande
      \rput(4,0.7){%
        % Bande
        \multips(0,0)(0.5,0){7}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.1){$a$}
        \rput[B](0.75,0.1){$a$}
        \rput[B](1.25,0.1){$b$}
        \rput[B](1.75,0.1){$c$}
        \rput[B](2.25,0.1){$b$}
        \rput[B](2.75,0.1){$c$}
        \rput[B](3.25,0.1){$\#$}
      }
    \end{pspicture}
  \end{center}
  \begin{itemize}
  \item \alert{Synchronous} moves of the heads 
  \item padding of the shorter words
  \end{itemize}

  \begin{examples}
    \begin{itemize}
    \item $\{(a^n,b^n) \mid n \ge 0\}$ et 
      $\{(u,v) \mid u \text{  prefix of } v\}$ are synchronous
    \item $\{(a^n,b^{2n}) \mid n \ge 0\}$ is not synchronous
    \item $((a,ab) + (b,b))^*$  is not synchronous
    \end{itemize}
  \end{examples}
  The set of relations accepted by synchronous automata is denoted
  \alert{$\Sync(M)$}.
\end{frame}


\subsection{Asynchronous automata}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Automates décentralisés
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Asynchronous $n$-tapes automata}

  \begin{center}
    \begin{pspicture}(10,3.5)
      % Contrôle
      \psframe[framearc=.1](0,1.3)(1.8,2.5)
      \rput[B](0.9,1.8){$Q$}
      % Première bande
      \rput(4,2.4){%
        % Bande
        \multips(0,0)(0.5,0){6}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.15){$c$}
        \rput[B](0.75,0.15){$a$}
        \rput[B](1.25,0.15){$b$}
        \rput[B](1.75,0.15){$c$}
        \rput[B](2.25,0.15){$a$}
        \rput[B](2.75,0.15){$\#$}
        % Tête de lecture
        % Partie fixe
        \psline(-2.2,-0.2)(-1,-0.2)(-1,0.8)
        % Partie variable
        \only<1>{%
          \psline[arrows=->](-1,0.8)(0.25,0.8)(0.25,0.5)
          \psframe(0,0)(0.5,0.5)
        }%
        \only<2>{%
          \psline[arrows=->](-1,0.8)(0.75,0.8)(0.75,0.5)
          \psframe(0.5,0)(1,0.5)
        }%
        \only<3>{%
          \psline[arrows=->](-1,0.8)(1.25,0.8)(1.25,0.5)
          \psframe(1,0)(1.5,0.5)
        }%
        \only<4>{%
          \psline[arrows=->](-1,0.8)(1.75,0.8)(1.75,0.5)
          \psframe(1.5,0)(2,0.5)
        }%
        \only<5>{%
          \psline[arrows=->](-1,0.8)(2.25,0.8)(2.25,0.5)
          \psframe(2,0)(2.5,0.5)
        }%
        \only<6->{%
          \psline[arrows=->](-1,0.8)(2.75,0.8)(2.75,0.5)
          \psframe(2.5,0)(3,0.5)
        }%
      }
      % Deuxième bande
      \rput(4,1.2){%
        % Bande
        \multips(0,0)(0.5,0){4}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.1){$b$}
        \rput[B](0.75,0.1){$b$}
        \rput[B](1.25,0.1){$a$}
        \rput[B](1.75,0.1){$\#$}
        % Tête de lecture
        % Partie fixe
        \psline(-2.2,0.8)(-1,0.8)
        % Partie variable
        \only<-6>{%
          \psline[arrows=->](-1,0.8)(0.25,0.8)(0.25,0.5)
          \psframe(0,0)(0.5,0.5)
        }%
        \only<7>{%
          \psline[arrows=->](-1,0.8)(0.75,0.8)(0.75,0.5)
          \psframe(0.5,0)(1,0.5)
        }%
        \only<8>{%
          \psline[arrows=->](-1,0.8)(1.25,0.8)(1.25,0.5)
          \psframe(1,0)(1.5,0.5)
        }%
        \only<9->{%
          \psline[arrows=->](-1,0.8)(1.75,0.8)(1.75,0.5)
          \psframe(1.5,0)(2,0.5)
        }%
      }
      % Troisième bande
      \rput(4,0){%
        % Bande
        \multips(0,0)(0.5,0){7}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.1){$a$}
        \rput[B](0.75,0.1){$a$}
        \rput[B](1.25,0.1){$b$}
        \rput[B](1.75,0.1){$c$}
        \rput[B](2.25,0.1){$b$}
        \rput[B](2.75,0.1){$c$}
        \rput[B](3.25,0.1){$\#$}
        % Tête de lecture
        % Partie fixe
        \psline(-2.2,1.8)(-1,1.8)(-1,0.8)
        % Partie variable
        \only<-9>{%
          \psline[arrows=->](-1,0.8)(0.25,0.8)(0.25,0.5)
          \psframe(0,0)(0.5,0.5)
        }%
        \only<10>{%
          \psline[arrows=->](-1,0.8)(0.75,0.8)(0.75,0.5)
          \psframe(0.5,0)(1,0.5)
        }%
        \only<11>{%
          \psline[arrows=->](-1,0.8)(1.25,0.8)(1.25,0.5)
          \psframe(1,0)(1.5,0.5)
        }%
        \only<12>{%
          \psline[arrows=->](-1,0.8)(1.75,0.8)(1.75,0.5)
          \psframe(1.5,0)(2,0.5)
        }%
        \only<13>{%
          \psline[arrows=->](-1,0.8)(2.25,0.8)(2.25,0.5)
          \psframe(2,0)(2.5,0.5)
        }%
        \only<14>{%
          \psline[arrows=->](-1,0.8)(2.75,0.8)(2.75,0.5)
          \psframe(2.5,0)(3,0.5)
        }%
        \only<15->{%
          \psline[arrows=->](-1,0.8)(3.25,0.8)(3.25,0.5)
          \psframe(3,0)(3.5,0.5)
        }%
      }
    \end{pspicture}
  \end{center}
  \begin{itemize}
  \item \alert{sequential} moves of the heads 
  \end{itemize}

  \begin{examples}
    \begin{itemize}
    \item $R = (aA^* \times A^*a) \cup (bA^* \times A^*b)$ is 
      recognizable
    \item $R = \bigcup_{i=1}^n{K_i\times L_i}$ is recognizable
      if the sets $K_i$ and $L_i$ are rational.
    \item the diagonal $\{(u,u) \mid u \in A^* \}$ is not recognizable
    \end{itemize}
  \end{examples}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Automates 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Asynchronous $n$-tapes automata (other view)}

  \begin{center}
    \begin{pspicture}(10,3.5)
      % Contrôle
      \psframe[framearc=.1](0.6,-0.2)(2,3.6)
      \rput[B](0,1.6){$Q$}
      \psline(0.2,1.7)(0.6,1.7)
      % Première bande
      \rput(4,2.4){%
        % Contrôle
        \psframe[framearc=.1](-3.2,0)(-2.2,1)
        \rput[B](-2.7,0.4){$Q_1$}
        % Bande
        \multips(0,0)(0.5,0){6}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.15){$c$}
        \rput[B](0.75,0.15){$a$}
        \rput[B](1.25,0.15){$b$}
        \rput[B](1.75,0.15){$c$}
        \rput[B](2.25,0.15){$a$}
        \rput[B](2.75,0.15){$\#$}
        % Tête de lecture
        \psline[arrows=->](-2.2,0.4)(-1,0.4)(-1,0.8)(-1,0.8)(1.75,0.8)(1.75,0.5)
        \psframe(1.5,0)(2,0.5)
      }
      % Deuxième bande
      \rput(4,1.2){%
        % Contrôle
        \psframe[framearc=.1](-3.2,0)(-2.2,1)
        \rput[B](-2.7,0.4){$Q_2$}
        % Bande
        \multips(0,0)(0.5,0){4}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.1){$b$}
        \rput[B](0.75,0.1){$b$}
        \rput[B](1.25,0.1){$a$}
        \rput[B](1.75,0.1){$\#$}
        % Tête de lecture
        \psline[arrows=->](-2.2,0.4)(-1,0.4)(-1,0.8)(-1,0.8)(0.75,0.8)(0.75,0.5)
        \psframe(0.5,0)(1,0.5)
      }
      % Troisième bande
      \rput(4,0){%
        % Contrôle
        \psframe[framearc=.1](-3.2,0)(-2.2,1)
        \rput[B](-2.7,0.4){$Q_3$}
        % Bande
        \multips(0,0)(0.5,0){7}{\psframe[dimen=middle,linewidth=0.3pt](0,0)(0.5,0.5)}
        % Contenu de la bande
        \rput[B](0.25,0.1){$a$}
        \rput[B](0.75,0.1){$a$}
        \rput[B](1.25,0.1){$b$}
        \rput[B](1.75,0.1){$c$}
        \rput[B](2.25,0.1){$b$}
        \rput[B](2.75,0.1){$c$}
        \rput[B](3.25,0.1){$\#$}
        % Tête de lecture
        \psline[arrows=->](-2.2,0.4)(-1,0.4)(-1,0.8)(-1,0.8)(2.75,0.8)(2.75,0.5)
        \psframe(2.5,0)(3,0.5)
      }
    \end{pspicture}
  \end{center}
  \begin{itemize}
  \item one control state for \alert{each} tape :
    $Q = Q_1 \times\cdots\times Q_n$
  \end{itemize}
  
  The set of relations accepted by asynchronous automata is denoted
  \alert{$\Rec(M)$}.
\end{frame}

\section{Hierarchy}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% La hiérarchie 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{The strict hierarchy}

  \begin{displaymath}
    M = A^*_1\times\cdots\times A^*_n
  \end{displaymath}

  \begin{displaymath}
    \begin{array}{ccccccc}
      \Rec(M)   & \subset  & 
      \Sync(M)  & \subset  &
      \DRat(M)  & \subset  &
      \Rat(M)  \\
      \mathcal{F}_{0}&  &
      \mathcal{F}_{1}&  &
      \mathcal{F}_{2}&  &
      \mathcal{F}_{3}
    \end{array}
  \end{displaymath}

  \textsc{Inclusion-i-in-j}

  Input:  $R\in \mathcal{F}_{j}$

  Output: $R\in \mathcal{F}_{i}$?
  \end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Les différents cas
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{The different cases}

  To avoid trivial cases, it is assumed that
  \begin{itemize}
  \item $n\geq 2$
  \item $|A_i| \ge 1$ for each $1 \le i \le n$.
  \end{itemize}

  \vspace{1cm}
  There are two distinct main cases.
  \begin{itemize}
  \item $|A_1|= \cdots = |A_n|=1$ : all alphabets are of size~$1$. \\ 
    The monoid $M = A_1^* \times\cdots\times A_n^*$ is
    \alert{commutative} : $M \approx \N^n$.
  \item $|A_1| \ge 2$ : $M$ is \alert{not commutative}
  \begin{itemize}
    \item $|A_2|= \cdots = |A_n|=1$ : exactly one the alphabets is of
      size greater or equal to~$2$.
    \item $|A_2| \ge 2$ : at least two of the alphabets are of
      size greater or equal to~$2$.
  \end{itemize}
\end{itemize}
\end{frame}

\section{The non commutative case}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Le paysage actuel (cas non commutatif)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Known results (non commutative case)}

  \begin{center}
    \begin{tabular}{|p{16mm}|p{30mm}|p{30mm}|p{30mm}|} \hline
                   &   $\Rat(M)$   & $\DRat(M)$   & $\Sync(M)$ \\ \hline
      $\DRat(M)$   &
        \begin{tabular}{l}
           undecidable\\
           \alert{Fischer,}\\
           \alert{  Rosenberg 1967} \\
           \alert{Lisovik 1979}
        \end{tabular}  & & \\ \hline
      $\Sync(M)$   &
        \begin{tabular}{l}
          \\  
          undecidable \\
          \alert{idem} \\ \ 
        \end{tabular} &
        \begin{tabular}{l}
          \\ 
         open \\ \ 
        \end{tabular} & \\ \hline
      $\Rec(M)$   &
        \begin{tabular}{l}
          \\  
          undecidable \\
          \alert{idem} \\ \ 
        \end{tabular} &
        \begin{tabular}{l}
          decidable \\
          \alert{Carton, Choffrut}\\
          \alert{Grigorieff 2006}
        \end{tabular} &
        \begin{tabular}{l}
           decidable in $2^{0(n)}$\\
           \alert{Carton, Choffrut}\\
           \alert{Grigorieff 2006}
        \end{tabular} \\ \hline
    \end{tabular}
  \end{center}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Relations comme langages
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Relations as languages (binary case $A^* \times B^*$)}

  Correspondence relation $\leftrightarrow$ language.

  \begin{displaymath}
    R\subseteq A^*\times B^* \mapsto L_{R}\in A^*\#B^*
  \end{displaymath}
  where
  \begin{displaymath}
    L_{R}=\{\tilde{u}\# v\in A^*\#B^*\mid (u,v)\in R\}
  \end{displaymath}
  \begin{itemize}
  \item $R$ is a \alert{rational} relation iff $L_{R}$ is a \alert{linear}
    language with a unique final production $X\rightarrow \#$.
    
  \item If $R$ is a \alert{deterministic} rational, then
    $L_{R}$ is a \alert{deterministic} pushdown language.
    
  \item $R$ is a \alert{recognizable} relation iff $L_{R}$ is a
    \alert{rational} language.
  \end{itemize}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Stearns
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Stearns' results}

  \begin{theorem}[Stearns 1967]
    If can be decided whether a language given by a deterministic pushdown
    automaton is rational.
 \end{theorem}

  \begin{itemize}
  \item Very nice proof (majoration of the stack height)
    
  \item complexity of the procedure: $3$ exponentials
    
  \item The complexity has been lowered to $2$  exponentials by
    Valiant in 1976 (optimal, see Meyer et Fischer 1971)
    
  \item Therefore, it can be decided if a binary deterministic relation is
    recognizable.
\end{itemize}
\end{frame}


\section{The commutative case}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Le paysage actuel (cas commutatif)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Known results (commutative case)}

  \begin{center}
    \begin{tabular}{|p{16mm}|p{40mm}|} \hline
                  &   $\Rat(M)$   \\ \hline
     $\DRat(M)$   &
       \begin{tabular}{l}
          decidable \\
          \alert{Carton, Choffrut}\\
          \alert{Grigorieff 2006} \\ \ 
       \end{tabular}  \\ \hline
     $\Sync(M)$   &
       \begin{tabular}{l}
         \\  
         decidable \\
         \alert{idem} \\ \ 
       \end{tabular} \\ \hline
     $\Rec(M)$   &
       \begin{tabular}{l}
         \\  
         decidable \\
         \alert{Ginsburg, Spanier 67} \\ \ 
       \end{tabular} \\ \hline
    \end{tabular}
  \end{center}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Calcul dans N^2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Run in $\N^2$}
  \begin{center}
    \begin{pspicture}(10,7)
      %\psgrid
      % Type de pointillés
      \psset{dash=1pt 3pt}
      % Axes
      \psline[arrows=->](0,0)(8,0)
      \rput[B](7.9,-0.4){$x$}
      \psline[arrows=->](0,0)(0,7)
      \rput[B](-0.4,6.8){$y$}
      \only<1-3>{%
        % Point (m,n)
        \psdot(3,4)
        \rput[Bl](3.3,4){$(m,n)$}
        \rput[B](3,-0.4){$m$}
        \psline[linestyle=dashed](3,0)(3,4)
        \rput[B](-0.4,4){$n$}
        \psline[linestyle=dashed](0,4)(3,4)
        % Calcul
        \psline[linecolor=blue](0,0)(0,0.2)(0.4,0.2)(0.4,0.4)(0.8,0.4)%
               (0.8,1.6)(1,1.6)(1,1.8) (1.4,1.8)(1.4,2)(1.4,2.2)(2,2.2)%
               (2,2.4)(2.2,2.4)(2.2,2.6) (2.4,2.6)(2.4,3.2)(2.6,3.2)%
               (2.6,3.6)(3,3.6)(3,4)
      }%
      \only<2>{%
        % Flèches de l'état
        \rput[l](5.1,2){same state $p$}
        \psdot(0.8,1.4)
        \pscurve[arrows=->](5,2)(3,1.8)(0.8,1.4)
        \psdot(2.4,2.6)
        \pscurve[arrows=->](5,2)(3,2.3)(2.4,2.6)
      }%
      \only<3>{
        \uput[ul](0.4,0.7){\textcolor{red}{$\vec{u}$}}
        \uput[dr](1.6,2){\textcolor{red}{$\vec{v}$}}
        \rput(5,6){$\forall x \ge u \quad x \in R \iff x+v \in R$}
      }%
      \only<3-4>{%
        % Vecteurs
        \psline[arrows=->,linecolor=red](0,0)(0.8,1.4)
        \psline[arrows=->,linecolor=red](0.8,1.4)(2.4,2.6)
      }%
      \only<4-5>{%
        \psline[linestyle=dashed](0,1.4)(0.8,1.4)
        \psline(0.8,1.4)(7,1.4)
        \psline[linestyle=dashed](0.8,0)(0.8,1.4)
        \psline(0.8,1.4)(0.8,6)
        \psline[linestyle=dashed](0.8,2.6)(2.4,2.6)
        \psline(2.4,2.6)(7,2.6)
        \psline[linestyle=dashed](2.4,1.4)(2.4,2.6)
        \psline(2.4,2.6)(2.4,6)
      }%
      \only<5>{%
        \rput[B](0.4,0.6){$R_0$}
        \rput[B](2.4,0.6){$R_1$}
        \rput[B](0.4,2.6){$R_2$}
        \rput[B](1.6,1.9){$R_3$}
        \rput[B](3.2,1.9){$R_4$}
        \rput[B](1.6,3.3){$R_5$}
        \rput(7,5){%
          \begin{minipage}{6cm}
            $R$ is deterministic iff
            it is ultimately periodic and if 
            $R_1$, $R_2$, $R_4$ et $R_5$ are deterministic.
          \end{minipage}
        }%
      }%

    \end{pspicture}
  \end{center}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Réduction à Presburger
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Reduction to Presburger logic}
  
  Let $R$ be given by the formula $\theta(x;b)$
  \begin{displaymath}
    R=\{x\in\N^k \mid \theta(x;b)\}
  \end{displaymath}
  One constructs the formula $\Psi_\theta(b)$ 
  \begin{align*}
    \Psi_\theta(b) = \exists\mu\;\exists\pi \;\; &
         (\forall x \ge 0 \quad \theta(x+\mu;b) \iff 
                                \theta(x+\mu+\pi;b) \land {} \\
         & \forall u<\mu\;\;\forall v<\pi  \;\;
            \bigwedge_{\emptyset\neq I\subseteq\{1,\ldots,k\}}\\
         & (\zero(\mu-u)=I\ \implies \Psi_{\theta_I'}(b,\mu,u)) \\
         & (\zero(\pi-v)=I\ \implies \Psi_{\theta_I'}(b,\mu+\pi,\mu +v)))
  \end{align*}
  which is satisfiable iff $R$ is deterministic.
\end{frame}
\end{document}
