Hostname: page-component-8448b6f56d-sxzjt Total loading time: 0 Render date: 2024-04-25T06:45:28.252Z Has data issue: false hasContentIssue false
  • English
  • Français

Finite Completion of comma-free codes Part 2

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 a sequel to an earlier paper of the present author, in which it was proved that every finite comma-free code is embedded into a so-called (finite) canonical comma-free code. In this paper, it is proved that every (finite) canonical comma-free code is embedded into a finite maximal comma-free code, which thus achieves the conclusion that every finite comma-free code has finite completions.


Keywords

Comma-free codecompletionfinite maximal comma-free code.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 38 , Issue 2 , April 2004 , pp. 117 - 136
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).
Fine, N.J. and Wilf, H.S., Uniqueness Theorem for Periodic Functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. 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.
Ito, M., Katsura, M., Shyr, H.J. and Automata Accepting Primitive Words, S.S. Yu. Semigroup Forum 37 (1988) 45-52. CrossRef
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 1, in Proc. of DLT 2002. Springer-Verlag, Lect. Notes Comput. Sci. 2450 357-368.
Lyndon, R.C. and Shützenberger, M.-P., The Equation aM = bNcP in a Free Group. Michigan Math. J. 9 (1962) 289-298.
Al.A. Markov, An Example of an Independent 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
H.J. Shyr, Free Monoids and Languages. Lecture Notes, Hon Min Book Company, Taichung, 2001.
Watson, J.D. and Crick, F.C.H., Structure, A for Deoxyribose Nucleic Acid. Nature 171 (1953) 737. CrossRef