On codes with a finite deciphering delay: Constructing uncompletable words (Q5941067)
From MaRDI portal
scientific article; zbMATH DE number 1635232
Language | Label | Description | Also known as |
---|---|---|---|
English | On codes with a finite deciphering delay: Constructing uncompletable words |
scientific article; zbMATH DE number 1635232 |
Statements
On codes with a finite deciphering delay: Constructing uncompletable words (English)
0 references
20 August 2001
0 references
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].
0 references
code
0 references
prefix code
0 references
uniform code
0 references
deciphering delay
0 references
complete subset
0 references
right uncompletable word
0 references
uncompletable word
0 references