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⊆Σ∗. L'ensemble des facteurs de S, noté Fact(S), est l'ensemble suivant :

Fact(S)={w∈Σ∗|∃u,v∈Σ∗,uwv∈S∗}

Un mot m∈Σ∗ est dit incomplétable pour un ensemble M⊆Σ∗si m∈Σ∗∖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)=maxw∈M|w| la longueur maximale d'un mot de M et sl(M)=∑m∈M|m| la somme des longueurs des mots de M.

On peut remarquer que M⊆Σ≤l(M) donc |M|≤|Σ≤l(m)|=|Σ|l(M)+1−1|Σ|−1=O(|Σ|l(M)) et sl(M)≤∑m∈Ml(M)=|M|l(M)=O(l(M)|Σ|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 m1um2u...ml(M)−1u où u est un mot de longueur l(M) n'appartenant pas à M et les mi sont des mots de longueur au plus l(M). Ceci est vrai dans le cas où M=Σk∖{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 u1,...,un,v1,...,vm∈M, si u1...un=v1...vmalors n=m et pour tout 0<i≤n, ui=vi.

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