# Finite completion of comma-free codes. Part 2

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

- Volume: 38, Issue: 2, page 117-136
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topLam, Nguyen Huong. "Finite completion of comma-free codes. Part 2." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 38.2 (2004): 117-136. <http://eudml.org/doc/245676>.

@article{Lam2004,

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.},

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 = {117-136},

publisher = {EDP-Sciences},

title = {Finite completion of comma-free codes. Part 2},

url = {http://eudml.org/doc/245676},

volume = {38},

year = {2004},

}

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

PB - EDP-Sciences

VL - 38

IS - 2

SP - 117

EP - 136

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

LA - eng

KW - comma-free code; completion; finite maximal comma-free code

UR - http://eudml.org/doc/245676

ER -

## References

top- [1] J. Berstel and D. Perrin, Theory of Codes. Academic Press, Orlando (1985). Zbl0587.68066MR797069
- [2] N.J. Fine and H.S. Wilf, Uniqueness Theorem for Periodic Functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. Zbl0131.30203MR174934
- [3] S.W. Golomb, B. Gordon and L.R. Welch, Comma-free Codes. Canad. J. Math. 10 (1958) 202-209. Zbl0081.14601MR95091
- [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. Zbl0646.20055MR929442
- [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. Zbl0794.68087MR1135474
- [7] B.H. Jiggs, Recent Results in Comma-free Codes. Canad. J. Math. 15 (1963) 178-187. Zbl0108.14304MR143672
- [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. Zbl1022.94005
- [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. Zbl0106.02204MR162838
- [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. Zbl0154.00703MR210594
- [11] A. Restivo, On Codes Having No Finite Completions. Discret Math. 17 (1977) 306-316. Zbl0357.94011MR498922
- [12] H.J. Shyr, Free Monoids and Languages. Lecture Notes, Hon Min Book Company, Taichung, 2001. Zbl0746.20050MR1090325
- [13] J.D. Watson and F.C.H. Crick, A Structure for Deoxyribose Nucleic Acid. Nature 171 (1953) 737.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.