Finite completion of comma-free codes. Part 2

Lam, Nguyen Huong

doi:10.1051/ita:2004007

Lam, Nguyen Huong

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 2, pp. 117-136.

Résumé

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.

MR Zbl

DOI : 10.1051/ita:2004007

Classification : 68R15, 68S05
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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ita:2004007/

Bibliographie
Cité par

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

[2] N.J. Fine and H.S. Wilf, Uniqueness Theorem for Periodic Functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. | MR | Zbl

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

[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] M. Ito, M. Katsura, H.J. Shyr and S.S. Yu, Automata Accepting Primitive Words. Semigroup Forum 37 (1988) 45-52. | MR | Zbl

[6] 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 | Zbl

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

[8] 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.

[9] R.C. Lyndon and M.-P. Shützenberger, The Equation $a^{M} = b^{N} c^{P}$ in a Free Group. Michigan Math. J. 9 (1962) 289-298. | MR | Zbl

[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] A. Restivo, On Codes Having No Finite Completions. Discret Math. 17 (1977) 306-316. | MR | Zbl

[12] H.J. Shyr, Free Monoids and Languages. Lecture Notes, Hon Min Book Company, Taichung, 2001. | MR | Zbl

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

Cité par Sources :