Conjecture de Restivo

Modèle:Voir homonymes 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 {\mathrm{\Sigma }}^{*}$. L'ensemble des facteurs de S, noté Fact(S), est l'ensemble suivant :

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

Un mot $m\in {\mathrm{\Sigma }}^{*}$ est dit incomplétable pour un ensemble $M\subseteq {\mathrm{\Sigma }}^{*}$si $m\in {\mathrm{\Sigma }}^{*}\mathrm{\setminus }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)=\underset{w\in M}{\max }|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 {\mathrm{\Sigma }}^{\le l(M)}$ donc $|M|\le |{\mathrm{\Sigma }}^{\le l(m)}|=\frac{|\mathrm{\Sigma }{|}^{l(M)+1}-1}{|\mathrm{\Sigma }|-1}=O(|\mathrm{\Sigma }{|}^{l(M)})$ et $sl(M)\le \sum _{m\in M}l(M)=|M|l(M)=O(l(M)|\mathrm{\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}u{m}_{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={\mathrm{\Sigma }}^k\mathrm{\setminus }\{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\le 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)$.

Notes et références

Modèle:Portail