Codes and Length-Increasing Transitive Binary Relations

  • Do Long Van
  • Kieu Van Hung
  • Phan Trung Huy
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3722)


Classes of codes defined by binary relations are considered. It turns out that many classes of codes can be defined by length-increasing transitive binary relations. By introducing a general embedding schema we show that the embedding problem can be solved in a unified way for many classes of codes defined in such a way. Several among these classes of codes can be characterized by means of variants of Parikh vectors. This is very useful in constructing many-word concrete codes, maximal codes in corresponding classes of codes. Also, this allows to establish procedures to generate all maximall codes as well as algorithms to embed a code in a maximal one in some classes of codes.


Code binary relation embedding problem Parikh vector 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Berstel, J., Perrin, D.: Theory of Codes. Academic Press, New York (1985)zbMATHGoogle Scholar
  2. 2.
    Bruyère, V., Latteux, M.: Variable-length maximal codes. Theoretical Computer Science 98, 321–337 (1992)CrossRefMathSciNetGoogle Scholar
  3. 3.
    Bruyère, V., Wang, L., Zhang, L.: On completion of codes with finite deciphering delay. European Journal of Combinatorics 11, 513–521 (1990)zbMATHMathSciNetGoogle Scholar
  4. 4.
    Ehrenfeucht, A., Rozenberg, G.: Each regular code is included in a maximal regular code. RAIRO Theoretical Informatics and Applications 20, 89–96 (1986)zbMATHMathSciNetGoogle Scholar
  5. 5.
    Grätzer, G.: Universal Algebra. Van Nostrand, Princeton (1968)zbMATHGoogle Scholar
  6. 6.
    Hung, K.V., Huy, P.T., Van, D.L.: On some classes of codes defined by binary relations. Acta Mathematica Vietnamica 29, 163–176 (2004)zbMATHMathSciNetGoogle Scholar
  7. 7.
    Hung, K.V., Huy, P.T., Van, D.L.: Codes concerning roots of words. Vietnam Journal of Mathematics 32, 345–359 (2004)zbMATHMathSciNetGoogle Scholar
  8. 8.
    Hopcroft, J., Ullman, J.: Formal Languages and Their Relation to Automata. Addison-Wesley Publishing Company, Massachussetts (1969)zbMATHGoogle Scholar
  9. 9.
    Ito, M., Jürgensen, H., Shyr, H., Thierrin, G.: Outfix and infix codes and related classes of languages. Journal of Computer and System Science 43, 484–508 (1991)zbMATHCrossRefGoogle Scholar
  10. 10.
    Ito, M., Thierrin, G.: Congruences, infix and cohesive prefix codes. Theoretical Computer Science 136, 471–485 (1994)zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Jürgensen, H., Konstatinidis, S.: Codes. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 511–607. Springer, Berlin (1997)Google Scholar
  12. 12.
    Lam, N.H.: Finite maximal infix codes. Semigroup Forum 61, 346–356 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Markov, A.A.: An example of an independent system of words which cannot be included in a finite complete system. Matematicheskie Zametki 1, 87–90 (1967) (in Russian)zbMATHMathSciNetGoogle Scholar
  14. 14.
    Perrin, D.: Completing biprefix codes. Theoretical Computer Science 28, 329–336 (1984)zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    Restivo, A.: On codes having no finite completion. Discrete Mathematics 17, 309–316 (1977)zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    Restivo, A., Salemi, S., Sportelli, T.: Completing codes. RAIRO Theoretical Informatics and Applications 23, 135–147 (1989)zbMATHMathSciNetGoogle Scholar
  17. 17.
    Shyr, H.: Free Monoids and Languages. Hon Min Book Company, Taichung (1991)zbMATHGoogle Scholar
  18. 18.
    Shyr, H., Thierrin, G.: Codes and binary relations. In: Lecture Notes 586 “Sèminarie d’Algèbre, Paul Dubreil, Paris, pp. 180–188. Springer, Heidelberg (1975-1976)Google Scholar
  19. 19.
    Van Embedding, D.L.: problem for codes defined by binary relations. Preprint 98/A22, Institute of Mathematics, Hanoi (1998)Google Scholar
  20. 20.
    Van, D.L.: On a class of hypercodes. In: Ito, M., Imaoka, T. (eds.) Words, Languages and Combinatorics III, pp. 171–183. World Scientific, Singapore (2003)CrossRefGoogle Scholar
  21. 21.
    Van, D.L., Hung, K.V.: On codes defined by binary relations, Part I: Embedding problem (submitted)Google Scholar
  22. 22.
    Van, D.L., Hung, K.V.: On codes defined by binary relations, Part II: Vector characterizations and maximality (submitted)Google Scholar
  23. 23.
    Zhang, L., Shen, Z.: Completion of recognizable bifix codes. Theoretical Computer Science 145, 345–355 (1995)zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Do Long Van
    • 1
  • Kieu Van Hung
    • 2
  • Phan Trung Huy
    • 3
  1. 1.Institute of MathematicsHanoiVietnam
  2. 2.Hanoi Pedagogical UniversityVinh PhucVietnam
  3. 3.Hanoi Polytechnic UniversityHanoiVietnam

Personalised recommendations