\documentclass[a4paper, 11pt]{article}
\usepackage[utf8]{inputenc} 
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{graphicx}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{stmaryrd}
\usepackage{algpseudocode}
\usepackage{fullpage}
\usepackage{tikz}
\usepackage[trim]{tokenizer}
\usepackage{enumitem}
\usetikzlibrary{snakes,arrows,shapes}

\newtheorem{theo}{Théorème}
\newtheorem{lemme}[theo]{Lemme}
\begin{document}

\title{Réécriture et jetons sur un graphe}
\author{Paul Melotti}
\date{juin 2014}
\maketitle
\section{Réécritures de mots}
On considère l'ensemble des mots sur un alphabet $\Sigma$. Une \textit{règle de réécriture} $r\rightarrow r'$ est constituée de deux mots $r$ et $r'$. La réécriture signifie que dans un mot contenant le facteur $r$ on peut le remplacer par $r'$.
Autrement dit, la règle s'applique au mot $t$ ssi $t$ s'écrit $t=urv$ où $u$ et $v$ sont deux mots, et on note alors $t\rightarrow t'$ où $u'=ur'v$.

Un \textit{système de réécriture} est un ensemble de règles de réécriture.

\medskip

Si $t_0\rightarrow t_1 \rightarrow \dots \rightarrow t_n$, on note $t_0 \rightarrow^{*} t_n$.

Un mot $t$ est dit \textit{forme normale} s'il n'existe pas de $s$ tel
que $t\rightarrow s$. Si $t\rightarrow u$ et $u$ est une forme normale, on dit que $u$ est une \textit{forme normale de} $t$.

Un système de réécriture satisfait la \textit{propriété de terminaison} s'il n'existe pas de suite infinie de réécritures $t_0\rightarrow \dots \rightarrow t_n \rightarrow \dots $.
\begin{enumerate}
\item Montrer que si le système satisfait la propriété de terminaison, tout mot admet une forme normale.
\item Dans cette question, $\Sigma = \{a,b\}$. Pour chacun des systèmes de réécriture suivants, dire si la propriété de terminaison est satisfaite :
\begin{itemize}
\item $a \rightarrow ab$
\item $ab \rightarrow a$
\item $a \rightarrow b $ et $b \rightarrow a$
\item $ab \rightarrow bba$
\end{itemize}
\end{enumerate}
Soient les deux propriétés suivantes sur les systèmes de réécriture :
\begin{itemize}
\item \textit{confluence} : si $t \rightarrow^{*} u$ et $t \rightarrow^{*} v$, alors il existe $w$ tel que $u \rightarrow^{*} w$ et $v \rightarrow^{*} w$.
\item \textit{confluence locale} : si $t \rightarrow u$ et $t \rightarrow v$, alors il existe $w$ tel que $u \rightarrow^{*} w$ et $v \rightarrow^{*} w$.
\end{itemize}
\begin{enumerate}[resume]
\item Montrer que si on a la propriété de terminaison et la propriété de confluence, tout mot admet une unique forme normale.
\end{enumerate}
L'objectif de cette partie va être le lemme suivant :
\begin{lemme}[Newman]
Pour un système de réécriture satisfaisant la propriété de terminaison, les propriétés de confluence locale et de confluence sont équivalentes.
\end{lemme}
\begin{enumerate}[resume]
\item Montrer un sens facile du lemme.
\end{enumerate}
Prouvons maintenant l'autre sens. On dit qu'un mot $t$ est confluent si pour tous mots $u$ et $v$ tels que $t \rightarrow^{*} u$ et $t \rightarrow^{*} v$, alors il existe $w$ tel que $u \rightarrow^{*} w$ et $v \rightarrow^{*} w$.

Supposons par l'absurde qu'il existe un mot $t$ non confluent.
\begin{enumerate}[resume]
\item Montrer qu'on peut supposer $t$ ``maximal parmi les mots non
confluents'', c'est-à-dire que pour tout $u$ tel que $t \rightarrow u$, $u$ est confluent.
\item En déduire une contradiction.
\end{enumerate}

\section{Réécritures générales}
Un système de réécriture est un ensemble de \textit{règles de réécriture} de la forme $$r\rightarrow r'.$$ Si un objet $t$ contient une \textit{instance} de $r$, c'est-à-dire un sous-objet qui s'identifie à $r$, on appelle $t'$ l'objet obtenu en remplaçant l'instance de $r$ par $r'$ dans $t$. Pour dire que ``$t$ se réécrit en $t'$'', on note $$t\rightarrow t'.$$
\begin{enumerate}[resume]
\item Que dire des résultats de la section précédente dans le cas général ?
\end{enumerate}

\section{Jetons sur un graphe}
Soit $G$ un graphe non orienté connexe. On note $d_s$ le degré du sommet $s$, c'est-à-dire son nombre de voisins. On place une pile de jetons sur chaque sommet du graphe ; le nombre de jetons sur le sommet $s$ sera noté $c_s$.

On joue à un jeu dont la règle est la suivante : si $c_s \geq d_s$ pour un sommet $s$, on peut retirer $d_s$ jetons au-dessus de $s$ et en donner un à chaque sommet voisin de $s$. La partie se poursuit tant qu'il est possible de jouer l'un des sommets (on peut avoir des parties infinies). Si plusieurs coups sont jouables il n'y a pas de contrainte sur lequel jouer en premier.
\begin{enumerate}[resume]
\item Montrer que si une partie est infinie, tous les sommets ont été joués une infinité de fois.
\item Montrer que si une partie est finie, au moins un sommet n'a pas été joué.
\item Donner une condition nécessaire simple sur le nombre de jetons pour espérer une partie finie.
\item Montrer que pour une configuration de départ donnant une partie finie, toutes les autres parties jouées sur cette configuration sont finies.
\item Montrer de plus que leur configuration finale est la même.

\textit{Indication :} On pourra considérer ce jeu comme un système de réécriture
\end{enumerate}
\end{document}