On codes with a finite deciphering delay: Constructing uncompletable words (Q5941067): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4430300 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimal complete sets of words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On completion of codes with finite deciphering delay / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On synchronizing unambiguous automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Construction of a family of finite maximal codes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Each regular code is included in a maximal regular code / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3659988 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5610821 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Completing codes / rank | |||
Normal rank |
Revision as of 19:19, 3 June 2024
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