K-Comma Codes and Their Generalizations

• Autorzy: Cui, B. , Kari, L. , Seki, S.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we introduce the notion of k-comma codes - a proper generalization of the notion of comma-free codes. For a given positive integer k, a k-comma code is a set L over an alphabet Σ with the property that LΣ^kL ∩Σ^+LΣ^+ = ∅. Informally, in a k-comma code, no codeword can be a subword of the catenation of two other codewords separated by a "comma" of length k. A k-comma code is indeed a code, that is, any sequence of codewords is uniquely decipherable. We extend this notion to that of k-spacer codes, with commas of length less than or equal to a given k. We obtain several basic properties of k-comma codes and their generalizations, k-comma intercodes, and some relationships between the families of k-comma intercodes and other classical families of codes, such as infix codes and bifix codes. Moreover, we introduce the notion of n-k-comma intercodes, and obtain, for each k ≥ 0, several hierarchical relationships among the families of n-k-comma intercodes, as well as a characterization of the family of 1-k-comma intercodes.

Słowa kluczowe

EN

K-comma codes; K-comma intercodes; N-k-comma intercodes

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 107, nr 1
• Strony: 1-18
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Cui, B.

autor

Kari, L.

autor

Seki, S.

• Department of Computer Science, University of Western Ontario, London, Ontario, Canada, N6A 5B7,

Bibliografia

• [1] Berstel, J., Perrin, D.: Theory of Codes. Academic Press. Inc., Orlando, Toronto. (1985)
• [2] Crick, H.C., Griffith, J.S., Orgel, L.E.: Codes without commas. Proc. Nat. Acad. Sci. 43 (1957) 416-421
• [3] Cui, B., Kari, L., Seki, S.: On the reversibility of parallel insertion, and its relation to comma codes. Proc. Of, CAI 2009. LNCS 5725, 204-219
• [4] Eastman, W. L.: On the construction of comma-free codes. IEEE Trans. Inform. Theory. 11 (1965) 263-267
• [5] Golomb, S.W., Gordon, B., Welch, L.R.: Comma-free codes. Canadian Journal of Mathematics. 10 (1958) 202-209
• [6] Han, Y.-S., Salomaa, K., Wood, D.: Intercode regular languages. Fundamenta Informaticae. 76 (2007) 113-128
• [7] Hayes, B.: The invention of the genetic code. American Scientist. 86:8-14, 1998
• [8] Hsieh, C. Y., Hsu, S. C., Shyr, H. J.: Some algebraic properties of comma-free codes. RIMS Kenkyuroku. 697 Japan (1989) 57-66
• [9] Ito, M., Jürgensen, H., Shyr, H. J., Thierrin, G.: Anti-commutative languages and n-codes. Discrete Applied Math. 24 (1989) 187-196
• [10] Ito, M., Jürgensen, H., Shyr, H. J., Thierrin, G.: N-prefix-suffix languages. Intern. J. Computer Math. 30(1989) 37-56
• [11] Jürgensen, H., Konstantinidis, S.: Codes. In Rozenberg, G., Salomaa, A. (eds): Handbook of Formal Languages, vol. I, 511-607. Springer-Verlag, Berlin, 1997.
• [12] Jürgensen, H., Yu, S. S.: Relations on free monoids, their independent sets, and codes. Intern. J. ComputerMath. 40 (1991) 17-46
• [13] Lewin, B.: Genes IX. Jones and Bartlett Publishers, 2007
• [14] Parikh, R.J.: On context-free languages. Journal of the Association for Computing Machinery. 13 (1966) 570- 581
• [15] Shyr, H. J.: FreeMonoids and Languages. Lecture Notes, Institute of AppliedMathematics, National Chung-Hsing University, Taichung, Taiwan. (2001)
• [16] Shyr, H. J., Yu, S. S.: Intercodes and some related properties. Soochow J. Math. 16 No.1 (1990) 95-107
• [17] Watson, J.: Genes, Girls and Gamow: After the Double Helix, Oxford University Press, 2001
• [18] Yu, S. S.: Languages and Codes. Lecture Notes, Department of Computer Science, National Chung-Hsing University, Taichung, Taiwan 402. (2005)
• [19] Yu, S. S.: A characterization of intercodes. Intern. J. Computer Math. 36 (1990) 39-48