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.
Mots-clés : comma-free code, completion, finite maximal comma-free code
@article{ITA_2004__38_2_117_0, author = {Lam, Nguyen Huong}, title = {Finite completion of comma-free codes. {Part} 2}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {117--136}, publisher = {EDP-Sciences}, volume = {38}, number = {2}, year = {2004}, doi = {10.1051/ita:2004007}, mrnumber = {2060773}, zbl = {1058.94010}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2004007/} }
TY - JOUR AU - Lam, Nguyen Huong TI - Finite completion of comma-free codes. Part 2 JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2004 SP - 117 EP - 136 VL - 38 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2004007/ DO - 10.1051/ita:2004007 LA - en ID - ITA_2004__38_2_117_0 ER -
%0 Journal Article %A Lam, Nguyen Huong %T Finite completion of comma-free codes. Part 2 %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2004 %P 117-136 %V 38 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2004007/ %R 10.1051/ita:2004007 %G en %F ITA_2004__38_2_117_0
Lam, Nguyen Huong. Finite completion of comma-free codes. Part 2. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 2, pp. 117-136. doi : 10.1051/ita:2004007. http://archive.numdam.org/articles/10.1051/ita:2004007/
[1] Theory of Codes. Academic Press, Orlando (1985). | MR | Zbl
and ,[2] Uniqueness Theorem for Periodic Functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. | MR | Zbl
and ,[3] Comma-free Codes. Canad. J. Math. 10 (1958) 202-209. | MR | Zbl
, and ,[4] Construction and Properties of Comma-free Codes. Biol. Medd. Dan. Vid. Selsk. 23 (1958) 3-34.
, and ,[5] Automata Accepting Primitive Words. Semigroup Forum 37 (1988) 45-52. | MR | Zbl
, , and ,[6] Outfix and Infix Codes and Related Classes of Languages. J. Comput. Syst. Sci. 43 (1991) 484-508. | MR | Zbl
, , and ,[7] Recent Results in Comma-free Codes. Canad. J. Math. 15 (1963) 178-187. | MR | Zbl
,[8] Finite Completion of Comma-Free Codes. Part 1, in Proc. of DLT 2002. Springer-Verlag, Lect. Notes Comput. Sci. 2450 357-368.
,[9] The Equation in a Free Group. Michigan Math. J. 9 (1962) 289-298. | MR | Zbl
and ,[10] 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. | MR | Zbl
[11] On Codes Having No Finite Completions. Discret Math. 17 (1977) 306-316. | MR | Zbl
,[12] Free Monoids and Languages. Lecture Notes, Hon Min Book Company, Taichung, 2001. | MR | Zbl
,[13] A Structure for Deoxyribose Nucleic Acid. Nature 171 (1953) 737.
and ,Cité par Sources :