Hostname: page-component-76fb5796d-dfsvx Total loading time: 0 Render date: 2024-04-25T09:32:16.042Z Has data issue: false hasContentIssue false
  • English
  • Français

Finite Completion of comma-free codes Part 1

Published online by Cambridge University Press:  15 June 2004

Nguyen Huong Lam
Nguyen Huong Lam*
Affiliation:
Hanoi Institute of Mathematics, 18 Hoang Quoc Viet Road, 10 307 Hanoi, Vietnam; nhlam@math.ac.vn.
Get access

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.

Keywords

Comma-free codecompletionfinite maximal comma-free code.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 38 , Issue 2 , April 2004 , pp. 91 - 115
Copyright
© EDP Sciences, 2004

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Berstel and D. Perrin, Theory of Codes. Academic Press, Orlando (1985).
Crick, F.H.C., Griffith, J.S. and Orgel, L.E., Codes without Commas. Proc. Natl. Acad. Sci. USA 43 (1957) 416-421. CrossRef
Golomb, S.W., Gordon, B. and Welch, L.R., Comma-free Codes. Canad. J. Math. 10 (1958) 202-209. CrossRef
Golomb, S.W., Welch, L.R. and Delbrück, M., Construction and Properties of Comma-free Codes. Biol. Medd. Dan. Vid. Selsk 23 (1958) 3-34.
W.L. Eastman, On the Construction of Comma-free Codes. IEEE Trans. Inform. Theory IT-11 (1965) 263-267.
Fan, C.M. and Shyr, H.J., Some Properties of Maximal Comma-free Codes. Tamkang J. Math. 29 (1998) 121-135.
Ito, M., Jürgensen, H., Shyr, H.J. and Thierrin, G., Outfix and Infix Codes and Related Classes of Languages. J. Comput. Syst. Sci. 43 (1991) 484-508. CrossRef
Jiggs, B.H., Recent Results in Comma-free Codes. Canad. J. Math. 15 (1963) 178-187. CrossRef
N.H. Lam, Finite Completion of Comma-free Codes. Part I, in Proc. DLT. Springer-Verlag, Lect. Notes Comput. Sci. 2450 (2002) 357-368.
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.
Restivo, A., Having No Finite Completions, On Codes. Discret Math. 17 (1977) 306-316. CrossRef
R.A. Scholtz, Maximal and Variable Word-length Comma-free Codes. IEEE Trans. Inform. Theory IT-15 (1969) 555-559.
H.J. Shyr, Free Monoids and Languages. Lecture Notes, Hon Min Book Company, Taichung (1991).
Watson, J.D. and Crick, F.C.H., Structure, A for Deoxyribose Nucleic Acid. Nature 171 (1953) 737. CrossRef