Conjecture de Restivo

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

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

Un mot ${\displaystyle m\in \Sigma ^{*}}$ est dit incomplétable pour un ensemble ${\displaystyle M\subseteq \Sigma ^{*}}$si ${\displaystyle m\in Fact(M^{*})\backslash \Sigma ^{*}}$, autrement dit tel que si on prend une suite finie quelconque de mots de ${\displaystyle M}$, et qu'on concatène pour en former un nouveau ${\displaystyle u=u_{1}u_{2}...u_{n}}$, ${\displaystyle m}$ n’apparaîtra pas dans ${\displaystyle u}$.

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

On peut remarquer que ${\displaystyle M\subseteq \Sigma ^{\leq l(M)}}$donc ${\displaystyle |M|\leq |\Sigma ^{\leq l(m)}|={\frac {|\Sigma |^{l(M)+1}-1}{|\Sigma |-1}}=O(|\Sigma |^{l(M)})}$ et ${\displaystyle 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 ${\displaystyle M}$ayant un mot incomplétable en a, en particulier, un de longueur au plus ${\displaystyle 2l(M)^{2}}$et que de plus ce mot est de la forme ${\displaystyle m_{1}um_{2}u...m_{l(M)-1}u}$où ${\displaystyle u}$est un mot de longueur ${\displaystyle l(M)}$ n'appartenant pas à ${\displaystyle M}$et les ${\displaystyle m_{i}}$sont des mots de longueur au plus ${\displaystyle l(M)}$. Ceci est vrai dans le cas où ${\displaystyle M=\Sigma ^{k}\backslash \{w\}}$avec ${\displaystyle w}$de longueur ${\displaystyle k}$, mais pas en général[3].

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

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

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