A hierarchy for circular codes
- 22 January 2008
- journal article
- research article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 42 (4) , 717-728
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
This publication has 13 references indexed in Scilit:
- A Circular Code in the Protein Coding Genes of MitochondriaJournal of Theoretical Biology, 1997
- Fibonacci numbers and wordsDiscrete Mathematics, 1997
- Sturmian words: structure, combinatorics, and their arithmeticsTheoretical Computer Science, 1997
- On some factorizations of infinite words by elements of codesInformation Processing Letters, 1997
- A Complementary Circular Code in the Protein Coding GenesJournal of Theoretical Biology, 1996
- Palindromes in the Fibonacci wordInformation Processing Letters, 1995
- Infinite words and biprefix codesInformation Processing Letters, 1994
- On cube-free ω-words generated by binary morphismsDiscrete Applied Mathematics, 1983
- A combinatorial property of the Fibonacci wordsInformation Processing Letters, 1981
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977