Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-27T09:36:12.849Z Has data issue: false hasContentIssue false
  • English
  • Français

A hierarchy for circular codes

Published online by Cambridge University Press:  22 January 2008

Giuseppe Pirillo
Giuseppe Pirillo*
Affiliation:
IASI CNR, Viale Morgagni 67/A, 50134 Firenze, Italy; [email protected] Université de Marne-la-Vallée 5, boulevard Descartes Champs sur Marne 77454 Marne-la-Vallée Cedex 2, France. Bigollo (Leonardo Pisano).
Get access

Abstract

We first prove an extremal property of the infinite Fibonacci* word f: the family of the palindromic prefixes {hn | n ≥ 6} of f is not only a circular code but “almost” a comma-free one (see Prop. 12 in Sect. 4). We also extend to a more general situation the notion of a necklace introduced for the study of trinucleotides codes on the genetic alphabet, and we present a hierarchy relating two important classes of codes, the comma-free codes and the circular ones.

Keywords

Theory of codescomma-free codescircular codes.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 42 , Issue 4: Fibonacci words , October 2008 , pp. 717 - 728
Copyright
© EDP Sciences, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arquès, D.G. and Michel, C.J., A complementary circular code in the protein coding genes. J. Theor. Biol. 182 (1996) 45–58. CrossRef
Arquès, D.G. and Michel, C.J., A circular code in the protein coding genes of mitochondria. J. Theor. Biol. 189 (1997) 273–290. CrossRef
J. Berstel, Mots de Fibonacci. Séminaire d'informatique théorique. LITP, Paris (1980–81) 57–78.
J. Berstel and D. Perrin, Theory of codes. Academic Press (1985).
J. Berstel and P. Seebold, Sturmian words, in Algebraic Combinatorics on words, edited by M. Lothaire. Cambridge University Press (2002).
Crick, F.H.C., Griffith, J.S. and Orgel, L.E., Codes without commas. Proc. Natl. Acad. Sci. USA 43 (1957) 416–421. CrossRef
de Luca, A., A combinatorial property of the Fibonacci words. Inform. Process. Lett. 12 (1981) 193–195. CrossRef
de Luca, A., Sturmian words: structure, combinatorics, and their arithmetics. Theoret. Comput. Sci. 183 (1997) 45–82. CrossRef
Droubay, X., Palindromes in the Fibonacci word. Inform. Process Lett. 55 (1995) 217–221. CrossRef
Justin, J. and Pirillo, G., On some factorizations of infinite words by elements of codes. Inform. Process. Lett. 62 (1997) 289–294. CrossRef
Karhumäki, J., On cube–free ω–words generated by binary morphism. Discrete Appl. Math. 5 (1983) 279–297. CrossRef
D.E. Knuth, The Art of Computer Programming. Addison–Wesley, Reading, Mass. (1968).
Knuth, D.E., Morris, J.H. and Pratt, V.R., Fast pattern matching in strings. SIAM J. Comput. 6 (1977) 323–350. CrossRef
M. Lothaire, Combinatorics on words. Addison-Wesley (1983).
C.J. Michel, G. Pirillo and M.A. Pirillo, Varieties of comma-free codes. Comput. Math. Appl. (in press).
Mignosi, F. and Pirillo, G., Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl. 26 (1992) 199–204. CrossRef
G. Pirillo, Infinite words and biprefix codes. Inform. Process Lett. 50 293–295 (1994).
Pirillo, G., Fibonacci numbers and words. Discrete Math. 173 (1997) 197–207. CrossRef
Pirillo, G., Some factorizations of the Fibonacci word. Algebra Colloquium 6 (1999) 361–368.
G. Pirillo, A characterization for a set of trinucleotides to be a circular code, In Determinism, Holism, and Complexity, edited by C. Pellegrini, P. Cerrai, P. Freguglia, V. Benci and G. Israel. Kluwer (2003).
Pirillo, G. and Pirillo, M.A., Growth function of self-complementary circular codes. Biology Forum 98 (2005) 97–110.
P.P. Séébold, Propriétés combinatoires des mots infinis engendrés par certains morphismes. PhD. thesis, L.I.T.P., Paris. (1985).