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 \Sigma ^{*}\backslash Fact(M^{*})}$. Autrement dit, si l'on considère une suite finie de mots de ${\displaystyle M}$, alors ${\displaystyle m}$ n'apparaîtra jamais comme facteur de la concaténation de ces mots.

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)}$.

• Portail des télécommunications
• Portail des mathématiques