\documentclass{beamer}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{xparse}
\usepackage{xstring}
\usepackage[nomessages]{fp}
\usepackage{changepage}%for adjustwidth environment
\usepackage{xcolor}
\usepackage{ifthen,xifthen}
\usepackage{calc}
\usepackage{tikz}
\usepackage{pifont}																				%%% required by macros/utils (?)
\usepackage{graphicx}
\usepackage{calculator}
\usepackage[inline]{enumitem}
\setitemize{%
	label=\usebeamerfont*{itemize item}%
	\usebeamercolor[fg]{itemize item}%
	\usebeamertemplate{itemize item}%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usetikzlibrary{arrows}
\usetikzlibrary{automata}
\tikzset{initial text={}}
\tikzset{every initial by arrow/.style={transition}}
\usetikzlibrary{calc}
\usetikzlibrary{decorations}
\usetikzlibrary{decorations.fractals}
\usetikzlibrary{decorations.pathreplacing}
\usetikzlibrary{fit}
\usetikzlibrary{positioning}
\usetikzlibrary{shapes}
\usetikzlibrary{snakes}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{remark}{Remark}
\newtheorem{proposition}{Proposition}
\newtheorem{question}{Question}
\beamertemplatenavigationsymbolsempty
\setbeamertemplate{footline}[frame number]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% visible and invisible tikz
\tikzset{
  invisible/.style={draw opacity=0,fill opacity=0,text opacity=0},
  visible on/.style={alt={#1{}{invisible}}},
  invisible on/.style={alt={#1{invisible}{}}},
  alt/.code args={<#1>#2#3}{%
    \alt<#1>{\pgfkeysalso{#2}}{\pgfkeysalso{#3}} 
  },
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% emphasis <<<
\DeclareDocumentCommand{\nit}{ O{nit} m O{temph last} }{%
  \tikz[remember picture, baseline]{\node[anchor=base,#1](#3){#2};}%
}
\DeclareDocumentCommand{\temph}{ O{1} m O{temph last} }{%
  \nit[temph#1]{\vphantom{Àg}#2}[#3]%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*\name[1]{{#1}}
\newcommand\defeq{\ensuremath{:=}}
\newcommand{\resp}{resp.}
\renewcommand{\iff}{if and only if}
\newcommand*\mand{\text{ and }}%math and
\newcommand*\mor{\text{ or }}%math or
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\DeclareDocumentCommand\lr{ O{p} O{1} m O{} }{%
	{%
		\ignorespaces%
		\ifthenelse{\equal{#2}{0}}{#3}{%
			\FPeval\recurs{clip(#2-1)}%
			\ifthenelse{\equal{#1}{}\or\equal{#4}{}}{%
				\IfEqCase*{#1,#4}{%
					%parentheses
					{(,}						{\edef\atleft{(}\edef\atright{)}}%
					{),}						{\edef\atleft{(}\edef\atright{)}}%
					{p,}						{\edef\atleft{(}\edef\atright{)}}%
					{parentheses,}			{\edef\atleft{(}\edef\atright{)}}%
					{round brackets,}		{\edef\atleft{(}\edef\atright{)}}%
					{round,}					{\edef\atleft{(}\edef\atright{)}}%
					{,(}						{\edef\atleft{(}\edef\atright{)}}%
					{,)}						{\edef\atleft{(}\edef\atright{)}}%
					{,p}						{\edef\atleft{(}\edef\atright{)}}%
					{,parentheses}			{\edef\atleft{(}\edef\atright{)}}%
					{,round brackets}		{\edef\atleft{(}\edef\atright{)}}%
					{,round}					{\edef\atleft{(}\edef\atright{)}}%
					%brackets
					{[,}						{\edef\atleft{[}\edef\atright{]}}%
					{],}						{\edef\atleft{[}\edef\atright{]}}%
					{b,}						{\edef\atleft{[}\edef\atright{]}}%
					{brackets,}				{\edef\atleft{[}\edef\atright{]}}%
					{,[}						{\edef\atleft{[}\edef\atright{]}}%
					{,]}						{\edef\atleft{[}\edef\atright{]}}%
					{,b}						{\edef\atleft{[}\edef\atright{]}}%
					{,brackets}				{\edef\atleft{[}\edef\atright{]}}%
					%braces
					{\{,}						{\edef\atleft{\{}\edef\atright{\}}}%
					{\},}						{\edef\atleft{\{}\edef\atright{\}}}%
					{a,}						{\edef\atleft{\{}\edef\atright{\}}}%
					{braces,}				{\edef\atleft{\{}\edef\atright{\}}}%
					{curly brackets,}		{\edef\atleft{\{}\edef\atright{\}}}%
					{curly,}					{\edef\atleft{\{}\edef\atright{\}}}%
					{,\}}						{\edef\atleft{\{}\edef\atright{\}}}%
					{,\{}						{\edef\atleft{\{}\edef\atright{\}}}%
					{,a}						{\edef\atleft{\{}\edef\atright{\}}}%
					{,braces}				{\edef\atleft{\{}\edef\atright{\}}}%
					{,curly brackets}		{\edef\atleft{\{}\edef\atright{\}}}%
					{,curly}					{\edef\atleft{\{}\edef\atright{\}}}%
					%chevrons
					{\langle,}				{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{\rangle,}				{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{langle,}				{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{c,}						{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{chevrons,}				{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{angle brackets,}		{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{angle,}					{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{,\langle}				{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{,\rangle}				{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{,langle}				{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{,c}						{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{,chevrons}				{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{,angle brackets}		{\edef\atleft{\langle}\edef\atright{\rangle}}%
					{,angle}					{\edef\atleft{\langle}\edef\atright{\rangle}}%
					%dots
					{.,}						{\edef\atleft{.}\edef\atright{.}}%
					{,.}						{\edef\atleft{.}\edef\atright{.}}%
					{d,}						{\edef\atleft{.}\edef\atright{.}}%
					{,d}						{\edef\atleft{.}\edef\atright{.}}%
					{dot,}					{\edef\atleft{.}\edef\atright{.}}%
					{,dot}					{\edef\atleft{.}\edef\atright{.}}%
					%vertical
					{|,}						{\edef\atleft{|}\edef\atright{|}}%
					{,|}						{\edef\atleft{|}\edef\atright{|}}%
					{v,}						{\edef\atleft{|}\edef\atright{|}}%
					{,v}						{\edef\atleft{|}\edef\atright{|}}%
					{vertical,}				{\edef\atleft{|}\edef\atright{|}}%
					{,vertical}				{\edef\atleft{|}\edef\atright{|}}%
				}[%
					\ifthenelse{\equal{#1}{}}{\edef\atleft{.}}{}%
					\ifthenelse{\equal{#2}{}}{\edef\atright{.}}{}%
				]%
			}{\edef\atleft{#1}\edef\atright{#4}}%
			\lr[\atleft][\recurs]{\left\atleft#3\right\atright}[\atright]%
		}%
	}%
}%
\newcommand*\set[1]{\lr[a]{#1}}%mathematical notation for sets
\newcommand*\card[1]{\lr[|]{#1}[|]}
\newcommand*\length[1]{\lr[|]{#1}[|]}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*\mirror[1]{\ensuremath{\overline{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*\ways[1]{#1-way}
\newcommand*\tapes[1]{#1-tape}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% variables %%%%%
\def\cellheight{1}
\def\cellwidth{1}
%%%%% styles %%%%%
\tikzstyle{tapeBG}=[fill=gray!5]
\tikzstyle{tapeSpaceBG}=[fill=none]
\tikzstyle{tapeH}=[draw=black,thick]
\tikzstyle{tapeHDots}=[tapeH,dashed]
\tikzstyle{tapeV}=[tapeH]
\tikzstyle{tapeVDots}=[tapeH,semithick]
\tikzstyle{tapeCell}=[baseline=(tape lastcell.base)]
\tikzstyle{transition}=[->,>=stealth',shorten >=.25ex]
%%%%% main commands %%%%%
%%% \tape commands <<<
\DeclareDocumentCommand{\tape}{ O{0} O{tape} m O{} m O{0} O{tapeCell} O{0} O{0} }{
	%#1: orientation angle                    optional, default: 0
	%#2: label prefix of node and coordinates	optional, default: tape
	%#3: first cell position                  required
	%#4: tape word                            optional, default:
	%#5: tape length                          required
	%#6: length of additional vertical lines  optional, default: 0
	%#7: style for cells                      optional, default: tapeCell
	%#8: length of dots segments to the left  optional, default: 0
	%#9: length of dots segments to the right optional, default: 0
	\path
		#3 ++(#1:-\cellwidth/2)	++(#1+90:\cellheight/2)                 coordinate (#2 nwcorner)
		(#2 nwcorner)				++(#1:#5*\cellwidth)                    coordinate (#2 necorner)
		(#2 nwcorner)           ++(#1+90:-\cellheight)                  coordinate (#2 swcorner)
		(#2 necorner)           ++(#1+90:-\cellheight)                  coordinate (#2 secorner)
		(#2 secorner)           ++(#1+90:-\cellheight*#6+\cellheight)   coordinate (#2 sespace)
		(#2 swcorner)           ++(#1+90:-\cellheight*#6+\cellheight)   coordinate (#2 swspace)
		coordinate[shape=rectangle,inner sep=0,outer sep=0,fit=(#2 nwcorner) (#2 necorner) (#2 secorner) (#2 swcorner)] (#2)
		;
	\fill[tapeSpaceBG] (#2 nwcorner) -- (#2 necorner) -- (#2 sespace) -- (#2 swspace) -- cycle;
	\fill[tapeBG] (#2 nwcorner) -- (#2 necorner) -- (#2 secorner) -- (#2 swcorner) -- cycle;
	\draw[tapeH] (#2 nwcorner) -- (#2 necorner);
	\draw[tapeH] (#2 swcorner) -- (#2 secorner);
	\draw[tapeHDots] (#2 nwcorner) -- ++(#1:-#8);
	\draw[tapeHDots] (#2 swcorner) -- ++(#1:-#8);
	\draw[tapeHDots] (#2 necorner) -- ++(#1:#9);
	\draw[tapeHDots] (#2 secorner) -- ++(#1:#9);
	\foreach \x in {0,1,...,#5}{
		\path (#2 nwcorner) ++(#1:\x*\cellwidth) edge[tapeV] ++(#1+90:-\cellheight);
		\path (#2 swcorner) ++(#1:\x*\cellwidth) edge[tapeVDots] ++(#1+90:-#6);
	}
	\ifthenelse{\equal{#4}{}}{
		\setNoTapeWord[#1][#2]{#3}{#5}[rotate=#1,fake,#7]
	}
	{
		\setTapeWord[#1][#2]{#3}{#4}[rotate=#1,#7]
	}
}
\DeclareDocumentCommand{\tapeCell}{ O{0} O{tape} O{1} m O{} O{\cellwidth} O{0} O{tapeCell} }{
	%#1: orientation angle                    optional, default: 0
	%#2: label prefix of node and coordinates	optional, default: tape
	%#3: tape cell index								optional, default: 1
	%#4: cell position		                  required
	%#5: tape cell symbol							optional, default: \phantom f
	%#6: cell width									optional, default: \cellwidth
	%#7: length of additional vertical lines  optional, default: 0
	%#8: style for cells                      optional, default: tapeCell
	\path
		#4 ++(#1:-#6/2)	++(#1+90:\cellheight/2)						coordinate (#2 nwcorner)
		(#2 nwcorner)		++(#1:#6)                    				coordinate (#2 necorner)
		(#2 nwcorner)		++(#1+90:-\cellheight)						coordinate (#2 swcorner)
		(#2 necorner)		++(#1+90:-\cellheight)						coordinate (#2 secorner)
		(#2 secorner)		++(#1+90:-\cellheight*#7+\cellheight)	coordinate (#2 sespace)
		(#2 swcorner)		++(#1+90:-\cellheight*#7+\cellheight)	coordinate (#2 swspace)
		coordinate[shape=rectangle,inner sep=0,outer sep=0,fit=(#2 nwcorner) (#2 necorner) (#2 secorner) (#2 swcorner)] (#2)
		;
	\fill[tapeSpaceBG] (#2 nwcorner) -- (#2 necorner) -- (#2 sespace) -- (#2 swspace) -- cycle;
	\fill[tapeBG] (#2 nwcorner) -- (#2 necorner) -- (#2 secorner) -- (#2 swcorner) -- cycle;
	\draw[tapeH] (#2 nwcorner) -- (#2 necorner);
	\draw[tapeH] (#2 swcorner) -- (#2 secorner);
	\path
		(#2 nwcorner)	edge[tapeV]			++(#1+90:-\cellheight)
		++(#1:#6)		edge[tapeV]			++(#1+90:-\cellheight)
		(#2 swcorner)	edge[tapeVDots]	++(#1+90:-#7)
		++(#1:#6)		edge[tapeVDots]	++(#1+90:-#7)
	;
	\setTapeCellSymbol[#1][#2][#3]{#4}[#5][rotate=#1,#8]
}
\DeclareDocumentCommand{\setTapeCellSymbol}{ O{0} O{tape} O{1} m O{\phantom f} O{tapeCell} }{
	%#1: orientation angle            			optional, default: 0
	%#2: label prefix of node and coordinates	optional, default: tape
	%#3: cell index									optional, default: 1
	%#4: cell position		         			required
	%#5: input symbol									optional, default: \phantom f	
	%#6: style for cell symbol        			optional, default: tapeCell
	\path #4 node[#6]	(#2 lastcell)	{#5};
	\ifthenelse{\equal{#3}{1}}{
		\pgfnodealias{#2 firstcell}{#2 lastcell}
		\pgfnodealias{#2 cell first}{#2 lastcell}
	}{}
	\pgfnodealias{#2 cell #3}{#2 lastcell}
	\pgfnodealias{#2 cell last}{#2 lastcell}
}
\DeclareDocumentCommand{\setTapeWord}{ O{0} O{tape} m m O{tapeCell} }{
	%#1: orientation angle            			optional, default: 0
	%#2: label prefix of node and coordinates	optional, default: tape
	%#3: first cell position          			required
	%#4: input word                   			required
	%#5: style for cell symbol        			optional, default: tapeCell
	\foreach \x [count=\xi] in {#4}{
		\ifthenelse{\equal{\xi}{1}}{
			\path #3 node[#5] (#2 lastcell) {\strut\x};
			\pgfnodealias{#2 firstcell}{#2 lastcell}
			\pgfnodealias{#2 cell first}{#2 lastcell}
		}
		{
			\path (#2 lastcell) ++(#1:\cellwidth) node[#5] (#2 lastcell) {\strut\x};
		}
		\pgfnodealias{#2 cell \xi}{#2 lastcell}
		\pgfnodealias{#2 cell last}{#2 lastcell}
	}
}
\DeclareDocumentCommand{\setNoTapeWord}{ O{0} O{tape} m m O{tapeCell} }{
	%#1: orientation angle            			optional, default: 0
	%#2: label prefix of node and coordinates	optional, default: tape
	%#3: first cell position          			required
	%#4: tape length									required
	%#5: style for cell symbol        			optional, default: tapeCell
	\foreach \x in {1,...,#4}{
		\ifthenelse{\equal{\x}{1}}{
			\path #3						node[#5,fake] (#2 lastcell)	{\phantom f};
			\pgfnodealias{#2 firstcell}{#2 lastcell}
			\pgfnodealias{#2 cell first}{#2 lastcell}
		}
		{
			\path (#2 lastcell) ++(#1:\cellwidth)	node[#5,fake] (#2 lastcell)	{\phantom f};
		}
		\pgfnodealias{#2 cell \xi}{#2 lastcell}
		\pgfnodealias{#2 cell last}{#2 lastcell}
	}
}
%% >>>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*\rat[1][]{\ensuremath{\textsc{Rat}\ifthenelse{\equal{#1}{}}{}{\left(#1\right)}}}
\newcommand*\rec[1][]{\ensuremath{\textsc{Rec}\ifthenelse{\equal{#1}{}}{}{\left(#1\right)}}}
\newcommand*\bwrat[1][]{\ensuremath{\textsc{bw}\rat[#1]}}
\newcommand*\Fact[1][]{\ensuremath{\textsc{Fact}\ifthenelse{\equal{#1}{}}{}{\left(#1\right)}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*\compos[2]{\ensuremath{#1\circ #2}}
\newcommand*\domain[1]{\ensuremath{\textsc{domain}\left(#1\right)}}
\newcommand*\image[1]{\ensuremath{\textsc{image}\left(#1\right)}}
\newcommand*\Id[1][]{\ensuremath{\textsc{Id}_{#1}}}
\newcommand*\revId[1][]{\ensuremath{\overline{\textsc{Id}}_{#1}}}
\DeclareDocumentCommand{\lreverse}{		O{\Sigma}	m					}{\ensuremath{\compos{\revId[#1]}{#2}}}
\DeclareDocumentCommand{\rreverse}{						m	O{\Delta}	}{\ensuremath{\compos{#1}{\revId[#2]}}}
\DeclareDocumentCommand{\lrreverse}{	O{\Sigma}	m	O{\Delta}	}{\lreverse[#1]{\rreverse{#2}[#3]}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\CC}[1][Christian]{\name{#1 Choffrut}}
\newcommand{\BG}[1][Bruno]{\name{#1 Guillon}}
\newcommand{\IRIF}{\textsc{IRIF}}
\newcommand{\UPD}[1]{Universit\'e Paris-Diderot\ifthenelse{\equal{#1}{7}}{, Paris 7}{#1}}
\newcommand{\DI}{Dipartimento di Informatica}
\newcommand{\UNIMI}{Universit\`a degli studi di Milano}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\definecolor{outcolor}{HTML}{6600CC}
\definecolor{incolor}{HTML}{009933}
\definecolor{intercolor}{HTML}{DF01D7}%{FA58F4}
\newcommand\inC[1]{\textcolor{incolor}{#1}}
\newcommand\outC[1]{\textcolor{outcolor}{#1}}
\newcommand\interC[1]{\textcolor{intercolor}{#1}}
\newcommand\blackC[1]{\textcolor{black}{#1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tikzstyle{nit}=[inner sep=2pt]%node in text
\tikzstyle{temph0}=[nit,rectangle,rounded corners,fill=white]
\tikzstyle{temph}=[nit,rectangle,rounded corners]
\tikzstyle{temph1}=[temph,fill=red!50]
\tikzstyle{temph2}=[temph,fill=brown!50]
\tikzstyle{temph3}=[temph,fill=yellow!50]
\tikzstyle{fake}=[draw=none,fill=none,text opacity=0]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Both ways rational functions}
\author{\CC\inst1 and \underline{\BG}\inst{1,2}}
\institute{\inst1\IRIF\ -- \UPD7\\\inst2\DI\ -- \UNIMI}
\date{July 25, 2016}
\hypersetup{%
	pdftitle={Both ways rational functions},%
	pdfauthor={Bruno Guillon},%
	pdfsubject={Development in Language Theory},%
	pdfkeywords={rational relations,transducers,two-way transducers,two-tape finite automata,mirror,reverse,transductions,relations on words}%
}

\begin{document}
\section{Introduction}
\maketitle
\begin{frame}
	\frametitle{Transductions}
	\begin{definition}
		A \alert<1>{transduction} is a relation in~\nit{$\inC{\Sigma^*}$}[input alphab]$\times$\nit{$\outC{\Delta^*}$}[output alphab].
	\end{definition}
	\begin{tikzpicture}[remember picture,overlay]
		\path
			(input alphab) ++(120:1cm)
			node[right] {%
				\nit[temph,text=incolor]{input}[input alphab lbl]
				and
				\nit[temph0,text=outcolor]{output}[output alphab lbl]
				alphabets%
			}
			(input alphab.110)		edge[->,draw=incolor,thick]	(input alphab lbl)
			(output alphab.north)	edge[->,draw=outcolor,thick]	(output alphab lbl)
			;
	\end{tikzpicture}
	\begin{examples}<2->
		\begin{center}
			\uncover<2->{
				$R\defeq
				\set{\lr{\inC u,\outC v}\mid\length{\inC u}_a=\length{\outC v}_a}$
			}
			\\[.1\textheight]
			\uncover<3->{
				$S\defeq
				\set{\lr{\inC u,\outC v}\mid\length{\inC u}_a=\length{\outC v}_a\mand\length{\inC u}_b=\length{\outC v}_b}$
			}
		\end{center}
	\end{examples}
\end{frame}
\begin{frame}
	\frametitle{One-way transductions}
	\begin{adjustwidth}{-1cm}{-1cm}
		\begin{itemize}
			\item \alert<1>{\ways[1] transduction} if accepted by a \alert<1>{\ways[1] \tapes[2] automaton}.
		\end{itemize}
	\end{adjustwidth}
	\medbreak
	\uncover<2->{
		\begin{adjustwidth}{-2cm}{-2cm}
			\begin{center}
				\begin{tikzpicture}
					\path
						(180:\cellwidth)		node[left,text=outcolor]	(olbl)	{output:}
						++(90:2*\cellheight)	node[left,text=incolor]		(ilbl)	{input:}
						(ilbl.west)	edge[transition,thick,bend right]
						node[left,text width=10em]	{\textbf{copy vowels} and\linebreak \textbf{duplicate consonants}}
						(olbl.west)
						;
					\setTapeWord[0][itape]{(0,2*\cellheight)}{c,a,n,a,d,a}[tapeCell,text=incolor]
					\setTapeWord[0][otape]{(0:0)}{{c\quad c},a,{n\quad n},a,{d\quad d},a}[tapeCell,text=outcolor]
					\path
						(itape cell first.north)	++(180:\cellwidth/2)	coordinate (itape cell 0)
						(otape cell first.south)	++(180:\cellwidth/2)	coordinate (otape cell 0);
					\foreach \t [count=\x] in {3,...,8}{
						\draw[transition,draw=incolor,thick,visible on={<\t>}]	(itape cell 0.north)	--	(itape cell \x.north);
						\draw[transition,draw=outcolor,thick,visible on={<\t>}]	(otape cell 0.south)	--	(otape cell \x.south);
						\fill[white,opacity=.25,visible on={<\t->}]					(itape cell first.south west)	rectangle (otape cell last.north west);
						\draw[transition,thick,visible on={<\t->}]					(itape cell \x)	-- (otape cell \x);
					}
					\draw[transition,draw=incolor,thick,visible on={<8->}]		(itape cell 0.north)	--	(itape cell last.north);
					\draw[transition,draw=outcolor,thick,visible on={<8->}]		(otape cell 0.south)	--	(otape cell last.south);
				\end{tikzpicture}
			\end{center}
		\end{adjustwidth}
	}
	\uncover<9->{
		\begin{theorem}[Elgot \& Mezei]
			\temph[2]{\ways[1] transductions}
			\temph[1]{$=\joinrel=$}
			\temph[2]{rational relations}[ratrel]
			$\lr\rat$
		\end{theorem}
	}
	\begin{tikzpicture}[remember picture,overlay,visible on={<10->}]
		\path
			(ratrel)	++(270:1cm)	node[temph3]	(ratrel def)
			{%
				\vphantom{Àg}%
				\small closure of \textbf{finite} transductions under \textbf{union}, \textbf{concatenation} and \textbf{Kleene star}%
			}
			(ratrel)	edge[thick,->]	(ratrel def)
			;
	\end{tikzpicture}
	\bigbreak
	\begin{center}
		\uncover<11->{
			$R\defeq
			\set{\lr{\inC u,\outC v}\mid\length{\inC u}_a=\length{\outC v}_a}
			\in\rat$
		}
		\\[.05\textheight]
		\uncover<12->{
			$S\defeq
			\set{\lr{\inC u,\outC v}\mid\length{\inC u}_a=\length{\outC v}_a\mand\length{\inC u}_b=\length{\outC v}_b}
			\notin\rat$
		}
	\end{center}
\end{frame}
\subsection{Examples}
\begin{frame}
	\frametitle{Examples}
	\tikz[overlay]\path (current page.north east) ++(210:4ex) node[below left] {$\inC\Sigma=\outC\Delta=\set{a,c,d,n}$};
	\begin{adjustwidth}{-1cm}{-1cm}
		\begin{center}
			\vspace{-6ex}
			\begin{tabular}{lcr}
				\begin{tabular}{l}%
					\uncover<1->{%
						$\textsc{Id}_\Sigma\defeq\set{\lr{\inC u,\outC u}\mid u\in\Sigma^*}$%
					}%
				\end{tabular}
				&	&
				\begin{tabular}{c}%
					\uncover<1->{%
						\begin{tikzpicture}
							\setTapeWord[0][itape]{(0,3/2*\cellheight)}{c,a,n,a,d,a}[tapeCell,text=incolor]
							\setTapeWord[0][otape]{(0,0)}{c,a,n,a,d,a}[tapeCell,text=outcolor]
							\foreach \x in {1,...,6}{
								\fill[white,opacity=.25]	(itape cell 1.south west)	rectangle (otape cell \x.north west);
								\draw[->,transition,thick]	(itape cell \x)	-- (otape cell \x);
							}
							\path
								(itape cell first.north)	++(180:\cellwidth/2)	coordinate (itape cell 0)
								(otape cell first.south)	++(180:\cellwidth/2)	coordinate (otape cell 0);
							\draw[transition,draw=incolor,thick]	(itape cell 0.north)	--	(itape cell last.north);
							\draw[transition,draw=outcolor,thick]	(otape cell 0.south)	--	(otape cell last.south);
						\end{tikzpicture}
					}%
				\end{tabular}
				\\[.2\textheight]
				\hline
				\\[.1\textheight]
				\begin{tabular}{l}%
					\uncover<2->{%
						$\revId[\Sigma]\defeq\set{\lr{\inC{\mirror u},\outC u}\mid u\in\Sigma^*}$%
					}%
				\end{tabular}
				&	&
				\begin{tabular}{c}%
					\uncover<2->{%
						\begin{tikzpicture}
							\setTapeWord[0][istape]{(0,3/2*\cellheight)}{c,a,n,a,d,a}[tapeCell,text=incolor,visible on={<2->}]
							\setTapeWord[0][ostape]{(0,0)}{a,d,a,n,a,c}[tapeCell,text=outcolor,visible on={<2->}]
							\path
								(istape cell last.north)	++(0:\cellwidth/2)		coordinate	(istape cell -1)
								(istape cell first.north)	++(180:\cellwidth/2)		coordinate	(istape cell 0)
								(ostape cell first.south)	++(180:\cellwidth/2)	coordinate	(ostape cell 0);
							\foreach \t [count=\x] in {3,...,8}{
								\coordinate[shape=rectangle,fill=white,fill opacity=.25,visible on={<\t->},inner ysep=3pt,fit=(istape cell first.south west) (ostape cell last.north east)];
								\ADD{7}{-\x}{\y}
								\draw[transition,draw=incolor,thick,visible on={<\t>}]	(istape cell -1.north)	--	(istape cell \y.north);
								\draw[transition,draw=outcolor,thick,visible on={<\t>}]	(ostape cell 0.south)	--	(ostape cell \x.south);
								\draw[->,transition,thick,visible on={<\t->}]				(istape cell \y.south)	-- (ostape cell \x.north);
							}
						\end{tikzpicture}
					}%
				\end{tabular}
			\end{tabular}
		\end{center}
	\end{adjustwidth}
\end{frame}
\subsection{Mirror operation}
\begin{frame}
	\frametitle{The mirror operations}
	\begin{tabular}{lcr}
		\begin{tabular}{l}%
			$\revId[\Sigma]\defeq\set{\lr{\inC{\mirror u},\outC u}\mid u\in\Sigma^*}$%
		\end{tabular}
		&	&
		\begin{tabular}{c}%
			\begin{tikzpicture}
				\setTapeWord[0][itape]{(0,3/2*\cellheight)}{c,a,n,a,d,a}[tapeCell,text=incolor]
				\setTapeWord[0][otape]{(0,0)}{a,d,a,n,a,c}[tapeCell,text=outcolor]
				\path
					(istape cell last.north)	++(0:\cellwidth/2)	coordinate (istape cell -1)
					(ostape cell first.south)	++(180:\cellwidth/2)	coordinate (ostape cell 0);
				\draw[transition,draw=incolor,thick]	(istape cell -1.north)	--	(istape cell first.north);
				\draw[transition,draw=outcolor,thick]	(ostape cell 0.south)	--	(ostape cell last.south);
				\foreach \x in {1,...,6}{
					\coordinate[shape=rectangle,fill=white,fill opacity=.25,inner ysep=3pt,fit=(istape cell first.south west) (ostape cell last.north east)];
					\ADD{7}{-\x}{\y}
					\draw[->,transition,thick]	(istape cell \y.south)	-- (ostape cell \x.north);
				}
			\end{tikzpicture}
		\end{tabular}
	\end{tabular}
	\bigbreak
	\begin{definition}[Mirror]
		The \alert<1>{mirror} of a relation~$R\subseteq\inC{\Sigma^*}\times\outC{\Delta^*}$ is the relation:
		\[
			\inC{\lreverse{\blackC R}}\defeq
			\set{
				\lr{\inC u,\outC v}
				\mid
				\lr{\inC{\mirror u},\outC v}
				\in R
			}
		\]
	\end{definition}
	\bigbreak
	\pause
	\begin{definition}[$\inC{\lreverse{\blackC\rat}}$]
		$R$ is \alert<2>{mirror rational} if~$\inC{\lreverse{\blackC R}}\in\rat$.
	\end{definition}
\end{frame}
\begin{frame}
	\frametitle{About mirrors}
	\tikz[overlay]\path (current page.north east) ++(-5em,-4ex) node {$R\subseteq\inC{\Sigma^*}\times\outC{\Delta^*}$};
	\begin{proposition}
		\centering
		$\revId[\Sigma]\notin\rat$
		\quad and\quad
		$\textsc{Id}_\Sigma\notin\inC{\lreverse{\blackC\rat}}$
	\end{proposition}
	\bigbreak
	\uncover<2->{
		\begin{proposition}
			\centering
			\begin{tabular}{lcl}
				\begin{tabular}{c}
					$R\in\rat$\\[3ex]
					\begin{tikzpicture}[scale=.5]
						\node[left,inner sep=10pt]	at	(0,.5)	{$\lr{\inC u,\outC v}$};
						\draw[transition,draw=incolor,ultra thick]		(0,1)	--	++(0:5*\cellwidth);
						\draw[transition,draw=outcolor,ultra thick]		(0,0)	--	++(0:5*\cellwidth);
					\end{tikzpicture}
				\end{tabular}
				&$\Longleftrightarrow$&
				\begin{tabular}{c}
					\nit{\outC{\rreverse{\inC{\lreverse{\blackC R}}}}}[revR]$\in\rat$\\[3ex]
					\begin{tikzpicture}[scale=.5]
						\node[right,inner sep=10pt]	at (5*\cellwidth,.5)	{$\lr{\inC{\mirror u},\outC{\mirror v}}$};
						\draw[transition,<-,draw=incolor,ultra thick]	(0,1)	--	++(0:5*\cellwidth);
						\draw[transition,<-,draw=outcolor,ultra thick]	(0,0)	--	++(0:5*\cellwidth);
					\end{tikzpicture}
				\end{tabular}
				
				\\[.25\textheight]

				\uncover<3->{%
					\begin{tabular}{c}
						$\inC{\lreverse{\blackC R}}\in\rat$\\[3ex]
						\begin{tikzpicture}[scale=.5]
							\node[left,inner sep=10pt]	at	(0,.5)	{$\lr{\inC{\mirror u},\outC v}$};
							\draw[transition,<-,draw=incolor,ultra thick]	(0,1)	--	++(0:5*\cellwidth);
							\draw[transition,draw=outcolor,ultra thick]		(0,0)	--	++(0:5*\cellwidth);
						\end{tikzpicture}
					\end{tabular}
					&$\Longleftrightarrow$&
					\begin{tabular}{c}
						$\outC{\rreverse{\blackC R}}\in\rat$\\[3ex]
						\begin{tikzpicture}[scale=.5]
							\node[right,inner sep=10pt]	at	(5*\cellwidth,.5)	{$\lr{\inC u,\outC{\mirror v}}$};
							\draw[transition,draw=incolor,ultra thick]		(0,1)	--	++(0:5*\cellwidth);
							\draw[transition,<-,draw=outcolor,ultra thick]	(0,0)	--	++(0:5*\cellwidth);
						\end{tikzpicture}
					\end{tabular}
				}%
			\end{tabular}
		\end{proposition}
	}
\end{frame}
\subsection{Both ways rationality}
\begin{frame}
	\frametitle{Both ways rational relations}
	\medbreak
	\begin{adjustwidth}{-2cm}{-2cm}
		\begin{center}
			\begin{tikzpicture}
				\begin{scope}[visible on={<4->}]
					\clip							(180:1.85)	circle	(4);
					\fill[orange!50!white]	(0:1.85)		circle	(4);
				\end{scope}
				\begin{scope}[visible on={<1->}]
					\draw[thick]	(180:1.85)	circle	(4);
					\node[left,text=black]		(rat)	at	(180:3.25)	{\huge$\rat$};
					\node[below,inner sep=1pt]			at (rat.south)	{rational};
				\end{scope}
				\begin{scope}[visible on={<2->}]
					\draw[thick]	(0:1.85)		circle	(4);
					\node[right,text=black]	(mofrat)	at	(0:2.55)			{\huge$\lreverse\rat$};
					\node[below,inner sep=1pt]			at (mofrat.south)	{mirror rational};
				\end{scope}
				\begin{scope}[visible on={<3->}]
					\coordinate[shape=circle,inner sep=1pt,fill=black]	(id pt)	at	(150:4.35);
					\coordinate[shape=circle,inner sep=1pt,fill=black]	(j pt)	at	(30:4.35);
					\node[right,inner sep=2pt]	at (id pt.north east)	{\large$\textsc{Id}_\Sigma$};
					\node[right,inner sep=2pt]	at (j pt.north east)		{\large$\revId[\Sigma]$};
				\end{scope}
				\begin{scope}[visible on={<5->}]
					\node (bwrat)	{\huge$\bwrat$};
					\node[below,inner sep=1pt]	at (bwrat.south)	{both ways rational};
					\node[above,inner sep=12pt,text=red] at (bwrat.north)	{\huge[this talk]};
				\end{scope}
			\end{tikzpicture}
		\end{center}
	\end{adjustwidth}
\end{frame}
\begin{frame}
	\frametitle{Examples of both ways rational relations}
	\begin{adjustwidth}{-.5cm}{-.25cm}
		\begin{center}
			\begin{tikzpicture}
				\path
					(180:\cellwidth)		node[left,text=outcolor]	(o1lbl)	{output:}
					++(90:2*\cellheight)	node[left,text=incolor]		(i1lbl)	{input:}
					(i1lbl.west)	edge[transition,thick,bend right]
					node[left]	{$\textsc F:$\quad \textbf{copy only~$a'${\small s}}}
					(o1lbl.west)
					(o1lbl.north)	edge[transition,thick,bend right=10,visible on={<18->}]
					node[right,visible on={<18->}]	{$\textsc F^{-1}$}
					(i1lbl.south)
					;
				\setTapeWord[0][i1tape]{(0,2*\cellheight)}{c,a,n,a,d,a}[tapeCell,text=incolor]
				\setTapeWord[0][o1tape]{(0:0)}{a,a,a}[tapeCell,text=outcolor]
				\path
					(i1tape cell last.north)	++(0:\cellwidth/2)	coordinate	(i1tape cell -1)
					(i1tape cell first.north)	++(180:\cellwidth/2)	coordinate	(i1tape cell 0)
					(o1tape cell first.south)	++(180:\cellwidth/2)	coordinate	(o1tape cell 0);
				\begin{scope}[visible on={<2-4>}]
					\draw[transition,draw=incolor,thick,visible on={<2>}]		(i1tape cell 0.north)	--	(i1tape cell 2.north);
					\draw[transition,draw=incolor,thick,visible on={<3>}]		(i1tape cell 0.north)	--	(i1tape cell 4.north);
					\draw[transition,draw=incolor,thick,visible on={<4>}]		(i1tape cell 0.north)	--	(i1tape cell last.north);
					\draw[transition,draw=outcolor,thick,visible on={<2>}]	(o1tape cell 0.south)	--	(o1tape cell 1.south);
					\draw[transition,draw=outcolor,thick,visible on={<3>}]	(o1tape cell 0.south)	--	(o1tape cell 2.south);
					\draw[transition,draw=outcolor,thick,visible on={<4>}]	(o1tape cell 0.south)	--	(o1tape cell last.south);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i1tape cell last.south east) (o1tape cell first.north west),%
						visible on={<2->}%
					];
					\draw[transition,thick,visible on={<2->}]	(i1tape cell 2.south)	-- (o1tape cell 1.north);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i1tape cell last.south east) (o1tape cell first.north west),%
						visible on={<3->}%
					];
					\draw[transition,thick,visible on={<3->}]	(i1tape cell 4.south)	-- (o1tape cell 2.north);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i1tape cell last.south east) (o1tape cell first.north west),%
						visible on={<4->}%
					];
					\draw[transition,thick,visible on={<4->}]	(i1tape cell 6.south)	-- (o1tape cell 3.north);
				\end{scope}
				\begin{scope}[visible on={<6->}]
					\draw[transition,draw=incolor,thick,visible on={<6>}]		(i1tape cell -1.north)	--	(i1tape cell 6.north);
					\draw[transition,draw=incolor,thick,visible on={<7>}]		(i1tape cell -1.north)	--	(i1tape cell 4.north);
					\draw[transition,draw=incolor,thick,visible on={<8->}]	(i1tape cell -1.north)	--	(i1tape cell first.north);
					\draw[transition,draw=outcolor,thick,visible on={<6>}]	(o1tape cell 0.south)	--	(o1tape cell 1.south);
					\draw[transition,draw=outcolor,thick,visible on={<7>}]	(o1tape cell 0.south)	--	(o1tape cell 2.south);
					\draw[transition,draw=outcolor,thick,visible on={<8->}]	(o1tape cell 0.south)	--	(o1tape cell last.south);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i1tape cell last.south east) (o1tape cell first.north west),%
						visible on={<6->}%
					];
					\draw[transition,thick,visible on={<6->}]	(i1tape cell 6.south)	-- (o1tape cell 1.north);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i1tape cell last.south east) (o1tape cell first.north west),%
						visible on={<7->}%
					];
					\draw[transition,thick,visible on={<7->}]	(i1tape cell 4.south)	-- (o1tape cell 2.north);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i1tape cell last.south east) (o1tape cell first.north west),%
						visible on={<8->}%
					];
					\draw[transition,thick,visible on={<8->}]	(i1tape cell 2.south)	-- (o1tape cell 3.north);
				\end{scope}
			\end{tikzpicture}
			\vfill
			\hrule
			\vfill
			\begin{tikzpicture}[visible on={<9->}]
				\path
					(180:\cellwidth)		node[left,text=outcolor]	(o2lbl)	{output:}
					++(90:3*\cellheight)	node[left,text=incolor]		(i2lbl)	{input:}
					(i2lbl.west)	edge[transition,thick,bend right]
					node[left]	(Rlbl)	{$\textsc R:$\quad\textbf{same $\#$ of~$a'${\small s}}}
					(o2lbl.west)
					;
				\setTapeWord[0][i2tape]{(0,3*\cellheight)}{c,a,n,a,d,a}[tapeCell,text=incolor]
				\setTapeWord[0][o2tape]{(0:0)}{{d\quad n\quad d},a,a,{c\quad c},a,{c\quad n}}[tapeCell,text=outcolor]
				\path
					(i2tape cell last.north)	++(0:\cellwidth/2)	coordinate	(i2tape cell -1)
					(i2tape cell first.north)	++(180:\cellwidth/2)	coordinate	(i2tape cell 0)
					(o2tape cell first.south)	++(180:\cellwidth/2)	coordinate	(o2tape cell 0);
				\begin{scope}[visible on={<9-12>}]
					\draw[transition,draw=incolor,thick,visible on={<10>}]	(i2tape cell 0.north)	--	(i2tape cell 2.north);
					\draw[transition,draw=incolor,thick,visible on={<11>}]	(i2tape cell 0.north)	--	(i2tape cell 4.north);
					\draw[transition,draw=incolor,thick,visible on={<12->}]	(i2tape cell 0.north)	--	(i2tape cell last.north);
					\draw[transition,draw=outcolor,thick,visible on={<10>}]	(o2tape cell 0.south)	--	(o2tape cell 2.south);
					\draw[transition,draw=outcolor,thick,visible on={<11>}]	(o2tape cell 0.south)	--	(o2tape cell 3.south);
					\draw[transition,draw=outcolor,thick,visible on={<12->}]	(o2tape cell 0.south)	--	(o2tape cell last.south);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i2tape cell first.south west) (o2tape cell last.north east),%
						visible on={<10->}%
					];
					\draw[transition,thick,visible on={<10->}]	(i2tape cell 2.south)	-- (o2tape cell 2.north);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i2tape cell first.south west) (o2tape cell last.north east),%
						visible on={<11->}%
					];
					\draw[transition,thick,visible on={<11->}]	(i2tape cell 4.south)	-- (o2tape cell 3.north);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i2tape cell first.south west) (o2tape cell last.north east),%
						visible on={<12->}%
					];
					\draw[transition,thick,visible on={<12->}]	(i2tape cell 6.south)	-- (o2tape cell 5.north);
				\end{scope}
				\begin{scope}[visible on={<13-16>}]
					\draw[transition,draw=incolor,thick,visible on={<14>}]	(i2tape cell -1.north)	--	(i2tape cell 6.north);
					\draw[transition,draw=incolor,thick,visible on={<15>}]	(i2tape cell -1.north)	--	(i2tape cell 4.north);
					\draw[transition,draw=incolor,thick,visible on={<16->}]	(i2tape cell -1.north)	--	(i2tape cell first.north);
					\draw[transition,draw=outcolor,thick,visible on={<14>}]	(o2tape cell 0.south)	--	(o2tape cell 2.south);
					\draw[transition,draw=outcolor,thick,visible on={<15>}]	(o2tape cell 0.south)	--	(o2tape cell 3.south);
					\draw[transition,draw=outcolor,thick,visible on={<16->}]	(o2tape cell 0.south)	--	(o2tape cell last.south);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i2tape cell first.south west) (o2tape cell last.north east),%
						visible on={<14->}%
					];
					\draw[transition,thick,visible on={<14->}]	(i2tape cell 6.south)	-- (o2tape cell 2.north);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i2tape cell first.south west) (o2tape cell last.north east),%
						visible on={<15->}%
					];
					\draw[transition,thick,visible on={<15->}]	(i2tape cell 4.south)	-- (o2tape cell 3.north);
					\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,%
						fit=(i2tape cell first.south west) (o2tape cell last.north east),%
						visible on={<16->}%
					];
					\draw[transition,thick,visible on={<16->}]	(i2tape cell 2.south)	-- (o2tape cell 5.north);
				\end{scope}
				\begin{scope}[visible on={<17->}]
					\path
						(i2lbl.east)	++(270:1.5*\cellheight)	node[left,text=intercolor]	(interlbl)	{inter:}
						(i2lbl)	edge[bend left=10,transition,thick]
						node[right]	{$\textsc F$}
						(interlbl)
						;
					\setTapeWord[0][intertape]{(90:1.5*\cellheight)}{a,a,a}[tapeCell,text=intercolor]
				\end{scope}
				\begin{scope}[visible on={<18->}]
					\path
						(interlbl)	edge[bend left=10,transition,thick]
						node[right]	{$\textsc F^{-1}$}
						(o2lbl)
						(Rlbl.south)	node[below,inner sep=3pt] {$R=\compos{\textsc F}{\textsc F^{-1}}$};
					;
				\end{scope}
			\end{tikzpicture}
		\end{center}
	\end{adjustwidth}
\end{frame}
\subsection{Factorizable relations}
\begin{frame}
	\frametitle{Factorizable relations}
	\begin{definition}[$\Fact$]
		$\textsc R\subseteq\inC{\Sigma^*}\times\outC{\Delta^*}$ is \alert{factorizable} if there exist
		\begin{columns}
			\begin{column}{.45\textwidth}
				\begin{itemize}
					\item $\textsc S\subseteq\inC{\Sigma^*}\times\interC{a^*}$ rational
					\item $\textsc T\subseteq\interC{a^*}\times\outC{\Delta^*}$ rational
				\end{itemize}
			\end{column}
			\begin{column}{.45\textwidth}
				such that \alert{$R=\compos{\textsc S}{\textsc T}$}.
			\end{column}
		\end{columns}
	\end{definition}
	\vfill
	\begin{center}
		\begin{tikzpicture}[transform shape,scale=.85]
			\setTapeWord[0][itape]{(90:3*\cellheight)}{c,a,n,a,d,a}[tapeCell,text=incolor,shape=rectangle]
			\setTapeWord[0][otape]{(0:0)}{{d\quad n\quad d},a,a,{c\quad c},a,{c\quad n}}[tapeCell,text=outcolor,shape=rectangle]
			\setTapeWord[0][intertape]{(90:1.5*\cellheight)}{a,a,a}[tapeCell,text=intercolor,shape=rectangle]
			\path
				(180:\cellwidth)			node[left,text=outcolor]	(olbl)		{output:}
				++(90:3*\cellheight)		node[left,text=incolor]		(ilbl)		{input:}
				++(270:1.5*\cellheight)	node[left,text=intercolor]	(interlbl)	{inter:}
				(ilbl)				edge[bend left=10,transition,thick] node[right]	{$\textsc S$}	(interlbl)
				(interlbl)			edge[bend left=10,transition,thick] node[right]	{$\textsc T$}	(olbl)
				(ilbl.south west)	edge[bend right,transition,thick]	node[left]	{$\textsc R$}	(olbl.north west)
				;

			\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,inner xsep=6pt,%
				fit=(itape cell last.south east) (intertape cell first.north west),%
			];
			\draw[transition,thick]	(itape cell 2.south)	-- (intertape cell 1.north);
			\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,inner xsep=6pt,%
				fit=(itape cell last.south east) (intertape cell first.north west),%
			];
			\draw[transition,thick]	(itape cell 4.south)	-- (intertape cell 2.north);
			\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,inner xsep=6pt,%
				fit=(itape cell last.south east) (intertape cell first.north west),%
			];
			\draw[transition,thick]	(itape cell 6.south)	-- (intertape cell 3.north);

			%%%%

			\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,inner xsep=6pt,%
				fit=(otape cell last.north east) (intertape cell first.south west),%
			];
			\draw[transition,thick]	(intertape cell 1.south)	-- (otape cell 2.north);
			\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,inner xsep=6pt,%
				fit=(otape cell last.north east) (intertape cell first.south west),%
			];
			\draw[transition,thick]	(intertape cell 2.south)	-- (otape cell 3.north);
			\coordinate[shape=rectangle,fill=white,fill opacity=.4,inner ysep=3pt,inner xsep=6pt,%
				fit=(otape cell last.north east) (intertape cell first.south west),%
			];
			\draw[transition,thick]	(intertape cell 3.south)	-- (otape cell 5.north);
		\end{tikzpicture}
	\end{center}
\end{frame}
\section{Main results}
\begin{frame}
	\frametitle{\bwrat\ versus \Fact}
	\begin{proposition}[closure properties]
		If~$R$ and~$S$ belongs to~\Fact\ (\resp~\bwrat), then so do:
		\newline%
		\begin{itemize*}%
			\item%
				$R\cup S$\quad~%
			\item%
				$\compos RS$\quad~%
			\item%
				$R^{-1}$\quad~%
			\item%
				$\inC{\lreverse{\blackC R}}$\quad~%
			\item%
				$\outC{\rreverse{\blackC R}}$%
		\end{itemize*}
		\newline%
		\uncover<2->{
			\begin{itemize*}%
				\item%
					$R\cdot T$\quad~%
				\item%
					$%
					R\cap T$
					\qquad for~$T\in\rec$%
					\uncover<3->{
						\quad
						$\lr{
							T=\bigcup\limits_{finite}
							\nit[text=incolor]{$X_i$}[xi]\times
							\nit[text=outcolor]{$Y_i$}[yi]
						}%
					}
					$
			\end{itemize*}
		}
		\begin{tikzpicture}[remember picture,overlay,visible on={<3->}]
			\draw[->]	(xi)	->	++(250:4ex)	node[below,xshift=-1em]	{$\in\rec\lr{\inC{\Sigma^*}}$};
			\draw[->]	(yi)	--	++(290:4ex)	node[below,xshift=1em]	{$\in\rec\lr{\outC{\Delta^*}}$};
		\end{tikzpicture}
	\end{proposition}
	\begin{columns}[b]
		\begin{column}{.60\textwidth}<4->
			\begin{remark}
				\begin{itemize}[nosep]
					\item $\card{\inC\Sigma}=1\Rightarrow\rat=\Fact=\bwrat$.
					\item $\card{\outC\Delta}=1\Rightarrow\rat=\Fact=\bwrat$.
				\end{itemize}
			\end{remark}
		\end{column}
		\begin{column}{.35\textwidth}<5->
			\begin{corollary}
				\large
				\begin{itemize}[nosep]
					\item	\alert<11>{$\Fact\subseteq\bwrat$}
				\end{itemize}
			\end{corollary}
		\end{column}
	\end{columns}
	\uncover<6->{
		\begin{question}
			Do we have~$\Fact=\bwrat$?
			\qquad
			\uncover<7->{\alert<7>{\textbf{No.}}}
		\end{question}
	}
	\uncover<8->{
		\begin{theorem}
			If~$R$ is a rational (partial) \alert<8-10>{function} then:
			\begin{center}
				\hfill
				$R\in\bwrat$
				\hfill
				\nit{$\Leftrightarrow$}[firsteq]
				\hfill
				$R\in\Fact$
				\hfill
				\uncover<9->{
				\nit{$\Leftrightarrow$}[secondeq]
					\hfill
					$\image R=\bigcup\limits_{\text{finite}}$\nit{$xy^*z$}[xystarz]
				}
				\hfill
			\end{center}
		\end{theorem}
	}
	\begin{tikzpicture}[remember picture,overlay]
		\begin{scope}[visible on={<10->}]
			\path
				(xystarz)	++(105:1.25cm)	node	(xyzin)	{$x,y,z\in\outC{\Delta^*}$}
				(xystarz.north west)	edge[bend left=10]	coordinate	(mstar)	(xystarz.north east)
				(xyzin.south west)	edge[bend right=10]	coordinate	(min)		(xyzin.south east)
				(mstar)					edge[->]												(min)
				;
		\end{scope}
		\begin{scope}
			\path
				(firsteq)	++(270:.75cm)	node[visible on={<11->}] {$\Leftarrow$}
				(secondeq)	++(270:.75cm)	node[visible on={<12->}] {$\Leftarrow$}
				;
		\end{scope}
	\end{tikzpicture}
\end{frame}
\subsection{Proof of main Theorem}
\begin{frame}
	\frametitle{%
		Proof of
		$\alert<7>{\textsc R\in\bwrat}\Rightarrow\image{\textsc R}=\bigcup\limits_{finite}xy^*z$%
	}
	\uncover<2->{%
		Consider the function:
		$\compos{\textsc R^{-1}}{\outC{\rreverse{\blackC{\textsc R}}}}$
	}%
	\uncover<10->{%
		\begin{flushright}
			$=\set{\lr{\outC v,\outC{\mirror v}}\mid\outC v\in\image R}\in\rat$
			\hspace{8em}
		\end{flushright}
	}%
	\uncover<11->{%
		\vspace{2ex}
		\begin{center}%
			$\Longrightarrow$%	
			\nit{$\image R=\bigcup\limits_{\text{finite}}xy^*z$}[image form]%
		\end{center}%
	}%
	\begin{tikzpicture}[remember picture,overlay,visible on={<12->}]%
		\coordinate[shape=rectangle,thick,fit=(image form),draw=red,inner sep=1pt]	(image form box);
		\path
			(image form box.south east)	++(355:2.5cm)	node[text=red]	(image form decide)	{decidable}
			(image form box)	edge[->,thick,draw=red]	(image form decide.west)
			;
	\end{tikzpicture}%
	\begin{center}
		\vspace{-13ex}
		\begin{tikzpicture}
			\edef\cellwidth{8*\cellwidth}
			\large
			\begin{scope}[visible on={<3-8>}]
				\tape[0][tape1]{(0,6*\cellheight)}[v]{1}[0][tapeCell,text=outcolor]
				\tape[0][tape2]{(0,4*\cellheight)}[u]{1}[0][tapeCell,text=incolor]
				\path[transition,thick]
					(tape1.west)	edge[bend right]	node[left]	{$\textsc R^{-1}$}				(tape2.west)
					;
			\end{scope}
			\begin{scope}[visible on={<4-8>}]
				\tape[0][tape3]{(0,2*\cellheight)}[v]{1}[0][tapeCell,text=outcolor]
				\path[transition,thick]
					(tape2.west)	edge[bend right]	node[left]	{$\textsc R$}						(tape3.west)
					;
			\end{scope}
			\begin{scope}[visible on={<5-8>}]
				\tape[0][tape4]{(0,0*\cellheight)}[\mirror v]{1}[0][tapeCell,text=outcolor]
				\path[transition,thick]
					(tape3.west)	edge[bend right]	node[left]	{$\outC{\revId[\Delta]}$}	(tape4.west)
					;
			\end{scope}
			\begin{scope}[visible on={<6-7>}]
				\path[transition,thick]
					(tape1.east)	edge[bend left]	node[right]	{$\in\rat$}							(tape2.east)
					;
			\end{scope}
			\begin{scope}[visible on={<7>}]
				\path[transition,thick]
					(tape2.east)	edge[bend left]	node[right]	{$\in\rat$}							(tape4.east)
					;
			\end{scope}
			\begin{scope}[visible on={<8>}]
				\path[transition,thick]
					(tape1.east)	edge[bend left]	node[right]	{$\in\rat$}							(tape4.east)
					;
			\end{scope}
			\begin{scope}[visible on={<9->}]
				\tape[0][tape1]{(0,3*\cellheight)}[v]{1}[0][tapeCell,text=outcolor]
				\tape[0][tape4]{(0,0*\cellheight)}[\mirror v]{1}[0][tapeCell,text=outcolor]
				\path[transition,thick]
					(tape1.east)	edge[bend left]	node[right]	{$\in\rat$}							(tape4.east)
					;
			\end{scope}
		\end{tikzpicture}
	\end{center}
\end{frame}
\section{Counter example}
\begin{frame}
	\frametitle{Counter example: $\bwrat\nsubseteq\Fact$}
	\begin{center}
		\begin{tikzpicture}[transform shape,scale=.7]
			\tapeCell[0][itape][1]{(90:3*\cellheight)}[\Large$a^i$][4*\cellwidth][0][tapeCell,text=incolor]
			\tapeCell[0][itape][2]{(itape cell 1) ++(0:5*\cellwidth/2)}[\Large$\#$][\cellwidth][0][tapeCell,text=incolor]
			\tapeCell[0][itape][3]{(itape cell 2) ++(0:5*\cellwidth/2)}[\Large$a^j$][4*\cellwidth][0][tapeCell,text=incolor]
			\tapeCell[0][itape][4]{(itape cell 3) ++(0:5*\cellwidth/2)}[\Large$\#$][\cellwidth][0][tapeCell,text=incolor]
			\tapeCell[0][itape][5]{(itape cell 4) ++(0:5*\cellwidth/2)}[\Large$a^k$][4*\cellwidth][0][tapeCell,text=incolor]

			\tapeCell[0][otape][1]{}[\Large$a^n$][4*\cellwidth][0][tapeCell,text=outcolor]
			\tapeCell[0][otape][2]{(otape cell 1) ++(0:5*\cellwidth/2)}[\Large$\#$][\cellwidth][0][tapeCell,text=outcolor]
			\tapeCell[0][otape][3]{(otape cell 2) ++(0:5*\cellwidth/2)}[\Large$a^m$][4*\cellwidth][0][tapeCell,text=outcolor]
			\tapeCell[0][otape][4]{(otape cell 3) ++(0:5*\cellwidth/2)}[\Large$\#$][\cellwidth][0][tapeCell,text=outcolor]
			\tapeCell[0][otape][5]{(otape cell 4) ++(0:5*\cellwidth/2)}[\Large$a^\ell$][4*\cellwidth][0][tapeCell,text=outcolor]

			\path
				(itape cell first)	++(180:7*\cellwidth/3)	coordinate (itape left)
				(otape cell first)	++(180:7*\cellwidth/3)	coordinate (otape left)
				(itape left)	edge[transition,thick,bend right]	node[left]	{\huge$\textsc{Sep}$}	(otape left)
				;

			\path
				(itape cell last.north)		++(0:\cellwidth/2)	++(90:\cellheight/2)		coordinate	(itape cell -1)
				(itape cell first.north)	++(180:\cellwidth/2)	++(90:\cellheight/2)		coordinate	(itape cell 0)
				(otape cell first.south)	++(180:\cellwidth/2)	++(270:\cellheight/2)	coordinate	(otape cell 0)
				(otape cell last.south)		++(0:\cellwidth/2)	++(270:\cellheight/2)	coordinate	(otape cell -1)
				;

			\draw[transition,draw=incolor,thick,visible on={<3-6>}]			(itape cell 0)		--	(itape cell -1);	
			\draw[transition,draw=incolor,thick,visible on={<8-11>}]			(itape cell -1)	--	(itape cell 0);	
			\draw[transition,draw=outcolor,thick,visible on={<3-6,8-11>}]	(otape cell 0)		--	(otape cell -1);	

			\path[transition,ultra thick]
				(itape cell 1.south) edge[draw=green!80,visible on={<4>}]			(otape cell 5.north)
				(itape cell 1.south)	edge[draw=green!30,visible on={<5-6,9-11>}]	(otape cell 5.north)
				(itape cell 5.south)	edge[draw=blue!80,visible on={<5,9>}]			(otape cell 5.north)
				(itape cell 5.south)	edge[draw=blue!30,visible on={<6,10-11>}]		(otape cell 5.north)
				(itape cell 1.south)	edge[draw=red!80,visible on={<6,10>}]			(otape cell 1.north)
				(itape cell 3.south)	edge[draw=orange!80,visible on={<6,10,11>}]	(otape cell 3.north)
				(itape cell 5.south)	edge[draw=brown!80,visible on={<11>}]			(otape cell 1.north)
				;
		\end{tikzpicture}
	\end{center}
	\begin{columns}[T]
		\begin{column}{.45\linewidth}<2->
			belongs to~$\textsc{Sep}$ if
			\begin{itemize}
				\item		\temph[,fill=green!30]{$i\neq\ell$}
				\item or	\temph[,fill=blue!30]{$k\neq\ell$}
				\item or	$\lr{%
						\temph[,fill=red!30]{i=n}\mand%
						\temph[,fill=orange!30]{j=m}%
					}$
			\end{itemize}
		\end{column}
		\begin{column}{.45\linewidth}<9->
			belongs to~$\textsc{Sep}$ \iff
			\begin{itemize}
				\item<9->		\temph[,fill=green!30]{$i\neq\ell$}
				\item<9-> or	\temph[,fill=blue!30]{$k\neq\ell$}
				\item<10-> or	$\lr{%
						\temph[,fill=red!30]{i=n}[ieqn]\mand%
						\temph[,fill=orange!30]{j=m}%
					}$
			\end{itemize}
			$%
			\tikz[remember picture,overlay,visible on={<11->}]%
			\path	(ieqn)	coordinate[temph,fill=brown!30,visible on={<11->},fit=(ieqn),inner sep=2pt]	node[nit]	{k=n};%
			$%
		\end{column}
	\end{columns}
	\vfill
	\begin{proposition}<12->
		\begin{center}
			\vspace{-6ex}
			\qquad
			$\textsc{Sep}\in\bwrat$
			\uncover<13->{
				\qquad but\qquad
				$\textsc{Sep}\notin\Fact$
			}
		\end{center}
	\end{proposition}
\end{frame}
\section{Conclusion}
\begin{frame}
	\frametitle{Conclusion}
	\begin{center}%
		\vspace{-6ex}%
		\uncover<4->{%
			\Large%
			\alert<4>{Functional case}%
		}%
	\end{center}
	\begin{adjustwidth}{-2cm}{-2cm}
		\begin{center}
			\begin{tikzpicture}
				\node[fill=orange!50,shape=rectangle,rounded corners,draw=black,thick,inner sep=4pt,visible on={<5->}]
					at	(270:2.25)					{\phantom{\large$\image F=\bigcup\limits_{\text{finite}}xy^*z$}};
				\begin{scope}[visible on={<1->}]
					\clip					(180:1.85)	circle	(4);
					\fill[orange!50]	(0:1.85)		circle	(4);
				\end{scope}
				\begin{scope}[visible on={<1->}]
					\draw[thick]		(180:1.85)	circle	(4);
					\draw[thick]		(0:1.85)		circle	(4);
					\node[left,text=black]		(rat)	at	(180:3.25)				{\huge$\rat$};
					\node[below,inner sep=1pt]			at (rat.south)				{rational};
					\node[right,text=black]	(mofrat)	at	(0:2.55)					{\huge$\lreverse\rat$};
					\node[below,inner sep=1pt]			at (mofrat.south)			{mirror rational};
					\coordinate[shape=circle,inner sep=1pt,fill=black]	(id pt)	at	(150:4.35);
					\coordinate[shape=circle,inner sep=1pt,fill=black]	(j pt)	at	(30:4.35);
					\node[right,inner sep=2pt]			at (id pt.north east)	{\large$\textsc{Id}_\Sigma$};
					\node[right,inner sep=2pt]			at (j pt.north east)		{\large$\revId[\Sigma]$};
					\node							(bwrat)	at	(90:2.25)				{\huge$\bwrat$};
					\node[below,inner sep=1pt]			at (bwrat.south)			{both ways rational};
				\end{scope}
				\begin{scope}
					\filldraw[fill=white,fill opacity=.25,draw=black,thick,visible on={<2-3>}]		(270:1.25)	ellipse	(1.5 and 2);
					\node[visible on={<2->}]						(fact)						{\huge$\Fact$};
					\node[below,inner sep=1pt,visible on={<2->}]			at	(fact.south)			{factorizable};
					\node[visible on={<4->}]									at	($(bwrat)!.6!(fact)$)	{\Huge$=\joinrel=$};

					\coordinate[shape=circle,inner sep=1pt,fill=black,visible on={<3>}]	(Sep pt)	at	(93:3);
					\node[right,inner sep=2pt,visible on={<3>}]			at	(Sep pt)					{\large$\textsc{Sep}$};
				\end{scope}
				\begin{scope}[visible on={<5->}]
					\node[fill=orange!50,shape=rectangle,rounded corners]		(image simple)	at	(270:2.25)	{\large$\image F=\bigcup\limits_{\text{finite}}xy^*z$};
					\node										at	($(fact)!.6!(image simple)$)	{\Huge$=\joinrel=$};
				\end{scope}
			\end{tikzpicture}
		\end{center}
	\end{adjustwidth}
	\uncover<6->{
		\begin{flushright}
			\vspace{-1ex}
			\nit[fill=white]{Thanks for your attention.}
		\end{flushright}
	}
\end{frame}
\end{document}
%<tp post>: pdftk {out} cat odd output {out}
