Let X a non-complete code with a finite dechiphering delay. We prove that an uncompletable word w of length O(n²d²) exists, where d stands for the delay and m stands for the length of the longest word in X. The proof leads to an explicit construction of w. This result partially resolves a conjecture proposed by Antonio Restivo in 1979.
Publié le : 2001-02-26
Classification:
Code,
Prefix code,
Uniform code,
Dechiphering delay,
Complet subset,
Uncompletable word,
[INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL],
[INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT],
[MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT]
@article{hal-00460320,
author = {Selmi, Carla and N\'eraud, Jean},
title = {On codes with a finite deciphering delay: constructing uncompletable words},
journal = {HAL},
volume = {2001},
number = {0},
year = {2001},
language = {en},
url = {http://dml.mathdoc.fr/item/hal-00460320}
}
Selmi, Carla; Néraud, Jean. On codes with a finite deciphering delay: constructing uncompletable words. HAL, Tome 2001 (2001) no. 0, . http://gdmltest.u-ga.fr/item/hal-00460320/