A hierarchy for circular codes
RAIRO - Theoretical Informatics and Applications (2008)
- Volume: 42, Issue: 4, page 717-728
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topPirillo, Giuseppe. "A hierarchy for circular codes." RAIRO - Theoretical Informatics and Applications 42.4 (2008): 717-728. <http://eudml.org/doc/250358>.
@article{Pirillo2008,
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.
},
author = {Pirillo, Giuseppe},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Theory of codes; comma-free codes; circular codes.; theory of codes; circular codes},
language = {eng},
month = {1},
number = {4},
pages = {717-728},
publisher = {EDP Sciences},
title = {A hierarchy for circular codes},
url = {http://eudml.org/doc/250358},
volume = {42},
year = {2008},
}
TY - JOUR
AU - Pirillo, Giuseppe
TI - A hierarchy for circular codes
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/1//
PB - EDP Sciences
VL - 42
IS - 4
SP - 717
EP - 728
AB -
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.
LA - eng
KW - Theory of codes; comma-free codes; circular codes.; theory of codes; circular codes
UR - http://eudml.org/doc/250358
ER -
References
top- D.G. Arquès and C.J. Michel, A complementary circular code in the protein coding genes. J. Theor. Biol.182 (1996) 45–58.
- D.G. Arquès and C.J. Michel, A circular code in the protein coding genes of mitochondria. J. Theor. Biol.189 (1997) 273–290.
- 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).
- F.H.C. Crick, J.S. Griffith and L.E. Orgel, Codes without commas. Proc. Natl. Acad. Sci. USA43 (1957) 416–421.
- A. de Luca, A combinatorial property of the Fibonacci words. Inform. Process. Lett.12 (1981) 193–195.
- A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics. Theoret. Comput. Sci.183 (1997) 45–82.
- X. Droubay, Palindromes in the Fibonacci word. Inform. Process Lett.55 (1995) 217–221.
- J. Justin and G. Pirillo, On some factorizations of infinite words by elements of codes. Inform. Process. Lett.62 (1997) 289–294.
- J. Karhumäki, On cube–free ω–words generated by binary morphism. Discrete Appl. Math.5 (1983) 279–297.
- D.E. Knuth, The Art of Computer Programming. Addison–Wesley, Reading, Mass. (1968).
- D.E. Knuth, J.H. Morris and V.R. Pratt, Fast pattern matching in strings. SIAM J. Comput.6 (1977) 323–350.
- 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).
- F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl.26 (1992) 199–204.
- G. Pirillo, Infinite words and biprefix codes. Inform. Process Lett.50 293–295 (1994).
- G. Pirillo, Fibonacci numbers and words. Discrete Math.173 (1997) 197–207.
- G. Pirillo, Some factorizations of the Fibonacci word. Algebra Colloquium6 (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).
- G. Pirillo and M.A. Pirillo, Growth function of self-complementary circular codes. Biology Forum98 (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).
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.