Finite completion of comma-free codes. Part 1
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 2, pp. 91-115.

This paper is the first step in the solution of the problem of finite completion of comma-free codes. We show that every finite comma-free code is included in a finite comma-free code of particular kind, which we called, for lack of a better term, canonical comma-free code. Certainly, finite maximal comma-free codes are always canonical. The final step of the solution which consists in proving further that every canonical comma-free code is completed to a finite maximal comma-free code, is intended to be published in a forthcoming paper.

DOI : https://doi.org/10.1051/ita:2004006
Classification : 68R15,  68S05
Mots clés : comma-free code, completion, finite maximal comma-free code
@article{ITA_2004__38_2_91_0,
author = {Lam, Nguyen Huong},
title = {Finite completion of comma-free codes. {Part} 1},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {91--115},
publisher = {EDP-Sciences},
volume = {38},
number = {2},
year = {2004},
doi = {10.1051/ita:2004006},
zbl = {1058.94009},
mrnumber = {2060772},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2004006/}
}
TY  - JOUR
AU  - Lam, Nguyen Huong
TI  - Finite completion of comma-free codes. Part 1
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2004
DA  - 2004///
SP  - 91
EP  - 115
VL  - 38
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2004006/
UR  - https://zbmath.org/?q=an%3A1058.94009
UR  - https://www.ams.org/mathscinet-getitem?mr=2060772
UR  - https://doi.org/10.1051/ita:2004006
DO  - 10.1051/ita:2004006
LA  - en
ID  - ITA_2004__38_2_91_0
ER  - 
Lam, Nguyen Huong. Finite completion of comma-free codes. Part 1. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 2, pp. 91-115. doi : 10.1051/ita:2004006. http://www.numdam.org/articles/10.1051/ita:2004006/

[1] J. Berstel and D. Perrin, Theory of Codes. Academic Press, Orlando (1985). | MR 797069 | Zbl 0587.68066

[2] F.H.C. Crick, J.S. Griffith and L.E. Orgel, Codes without Commas. Proc. Natl. Acad. Sci. USA 43 (1957) 416-421. | MR 86734

[3] S.W. Golomb, B. Gordon and L.R. Welch, Comma-free Codes. Canad. J. Math. 10 (1958) 202-209. | MR 95091 | Zbl 0081.14601

[4] S.W. Golomb, L.R. Welch and M. Delbrück, Construction and Properties of Comma-free Codes. Biol. Medd. Dan. Vid. Selsk 23 (1958) 3-34.

[5] W.L. Eastman, On the Construction of Comma-free Codes. IEEE Trans. Inform. Theory IT-11 (1965) 263-267. | MR 188006 | Zbl 0138.15102

[6] C.M. Fan and H.J. Shyr, Some Properties of Maximal Comma-free Codes. Tamkang J. Math. 29 (1998) 121-135. | MR 1644395 | Zbl 0978.68088

[7] M. Ito, H. Jürgensen, H.J. Shyr and G. Thierrin, Outfix and Infix Codes and Related Classes of Languages. J. Comput. Syst. Sci. 43 (1991) 484-508. | MR 1135474 | Zbl 0794.68087

[8] B.H. Jiggs, Recent Results in Comma-free Codes. Canad. J. Math. 15 (1963) 178-187. | MR 143672 | Zbl 0108.14304

[9] N.H. Lam, Finite Completion of Comma-free Codes. Part I, in Proc. DLT. Springer-Verlag, Lect. Notes Comput. Sci. 2450 (2002) 357-368. | Zbl 1022.94005

[10] Al. A. Markov, An Example of an Idependent System of Words Which Cannot Be Included in a Finite Complete System. Mat. Zametki 1 (1967) 87-90. | MR 210594 | Zbl 0154.00703

[11] A. Restivo, On Codes Having No Finite Completions. Discret Math. 17 (1977) 306-316. | MR 498922 | Zbl 0357.94011

[12] R.A. Scholtz, Maximal and Variable Word-length Comma-free Codes. IEEE Trans. Inform. Theory IT-15 (1969) 555-559. | MR 250754 | Zbl 0172.43104

[13] H.J. Shyr, Free Monoids and Languages. Lecture Notes, Hon Min Book Company, Taichung (1991). | MR 1090325 | Zbl 0746.20050

[14] J.D. Watson and F.C.H. Crick, A Structure for Deoxyribose Nucleic Acid. Nature 171 (1953) 737.

Cité par Sources :