Finite completion of comma-free codes. Part 1

Nguyen Huong Lam

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2004)

  • Volume: 38, Issue: 2, page 91-115
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Lam, Nguyen Huong. "Finite completion of comma-free codes. Part 1." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 38.2 (2004): 91-115. <http://eudml.org/doc/245677>.

@article{Lam2004,
abstract = {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.},
author = {Lam, Nguyen Huong},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {comma-free code; completion; finite maximal comma-free code},
language = {eng},
number = {2},
pages = {91-115},
publisher = {EDP-Sciences},
title = {Finite completion of comma-free codes. Part 1},
url = {http://eudml.org/doc/245677},
volume = {38},
year = {2004},
}

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
PB - EDP-Sciences
VL - 38
IS - 2
SP - 91
EP - 115
AB - 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.
LA - eng
KW - comma-free code; completion; finite maximal comma-free code
UR - http://eudml.org/doc/245677
ER -

References

top
  1. [1] J. Berstel and D. Perrin, Theory of Codes. Academic Press, Orlando (1985). Zbl0587.68066MR797069
  2. [2] F.H.C. Crick, J.S. Griffith and L.E. Orgel, Codes without Commas. Proc. Natl. Acad. Sci. USA 43 (1957) 416-421. MR86734
  3. [3] S.W. Golomb, B. Gordon and L.R. Welch, Comma-free Codes. Canad. J. Math. 10 (1958) 202-209. Zbl0081.14601MR95091
  4. [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. [5] W.L. Eastman, On the Construction of Comma-free Codes. IEEE Trans. Inform. Theory IT-11 (1965) 263-267. Zbl0138.15102MR188006
  6. [6] C.M. Fan and H.J. Shyr, Some Properties of Maximal Comma-free Codes. Tamkang J. Math. 29 (1998) 121-135. Zbl0978.68088MR1644395
  7. [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. Zbl0794.68087MR1135474
  8. [8] B.H. Jiggs, Recent Results in Comma-free Codes. Canad. J. Math. 15 (1963) 178-187. Zbl0108.14304MR143672
  9. [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. 
  10. [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. Zbl0154.00703MR210594
  11. [11] A. Restivo, On Codes Having No Finite Completions. Discret Math. 17 (1977) 306-316. Zbl0357.94011MR498922
  12. [12] R.A. Scholtz, Maximal and Variable Word-length Comma-free Codes. IEEE Trans. Inform. Theory IT-15 (1969) 555-559. Zbl0172.43104MR250754
  13. [13] H.J. Shyr, Free Monoids and Languages. Lecture Notes, Hon Min Book Company, Taichung (1991). Zbl0746.20050MR1090325
  14. [14] J.D. Watson and F.C.H. Crick, A Structure for Deoxyribose Nucleic Acid. Nature 171 (1953) 737. 

NotesEmbed ?

top

You must be logged in to post comments.