Conjecture de Restivo

La conjecture de Restivo est une assertion de la théorie des codes due à Antonio Restivo en 1981. Son énoncé original a été contredit en 2010 , cependant des versions plus faibles demeurent aujourd'hui ouvertes.

Énoncé

On se donne un alphabet fini Σ et un ensemble de mots sur cet alphabet $S\subseteq \Sigma ^{*}$. L'ensemble des facteurs de S, noté Fact(S), est l'ensemble suivant :

$Fact(S)=\{w\in \Sigma ^{*}|\exists u,v\in \Sigma ^{*},uwv\in S^{*}\}$

Un mot $m\in \Sigma ^{*}$ est dit incomplétable pour un ensemble $M\subseteq \Sigma ^{*}$si $m\in \Sigma ^{*}\backslash Fact(M^{*})$. Autrement dit, si l'on considère une suite finie de mots de $M$, alors $m$ n'apparaîtra jamais comme facteur de la concaténation de ces mots.

On note $l(M)=\max _{w\in M}|w|$ la longueur maximale d'un mot de $M$ et $sl(M)=\sum _{m\in M}|m|$ la somme des longueurs des mots de $M$.

On peut remarquer que $M\subseteq \Sigma ^{\leq l(M)}$ donc $|M|\leq |\Sigma ^{\leq l(m)}|={\frac {|\Sigma |^{l(M)+1}-1}{|\Sigma |-1}}=O(|\Sigma |^{l(M)})$ et $sl(M)\leq \sum _{m\in M}l(M)=|M|l(M)=O(l(M)|\Sigma |^{l(M)})$.

En 1981 Restivo conjecture que tout ensemble $M$ ayant un mot incomplétable en a, en particulier, un de longueur au plus $2l(M)^{2}$ et que de plus ce mot est de la forme $m_{1}um_{2}u...m_{l(M)-1}u$ où $u$ est un mot de longueur $l(M)$ n'appartenant pas à $M$ et les $m_{i}$ sont des mots de longueur au plus $l(M)$. Ceci est vrai dans le cas où $M=\Sigma ^{k}\backslash \{w\}$ avec $w$ de longueur $k$, mais pas en général.

Énoncés plus faibles

On ne sait pas si la longueur du plus petit mot incomplétable de $M$ est polynomiale en $l(M)$, ni même si elle est polynomiale en $sl(M)$.

On dit que $M$ est un code si pour tous $u_{1},...,u_{n},v_{1},...,v_{m}\in M$, si $u_{1}...u_{n}=v_{1}...v_{m}$alors $n=m$ et pour tout $0<i\leq n$, $u_{i}=v_{i}$.

Dans ce cas on ne sait pas si la longueur du plus petit mot incomplétable est polynomiale en $l(M)$.