On codes with a finite deciphering delay: Constructing uncompletable words (Q5941067)

Let \(X\) be a non-complete code with a finite deciphering delay. We prove that an uncompletable word \(w\) of length \(O(m^{2}d^{2})\) exists, where \(d\) stands for the delay and \(m\) stands for the length of the longest words in \(X.\) The proof leads to an explicit construction of \(w.\) This result partially resolves a conjecture proposed by \textit{A. Restivo} in [Codes and complete sets, in: D. Perrin (ed.), Théorie des codes, Actes de la septième École de Printemps d'informatique théorique, Jougne 1979, Édité par le LITP et le centre d'édition et de documentation de l'ENSTA].