Abstract | ||
---|---|---|
We study the palindrome complexity of infinite sequences on finite alphabets, i.e., the number of palindromic factors (blocks) of given length occurring in a given sequence. We survey the known results and obtain new results for some sequences, in particular for Rote sequences and for fixed points of primitive morphisms of constant length belonging to "class P" of Hof-Knill-Simon. We also give an upper bound for the palindrome complexity of a sequence in terms of its (block-)complexity. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1016/S0304-3975(01)00212-2 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
fixed point,known result,new result,Rote sequence,class P,palindrome complexity,Palindrome complexity,palindromic factor,finite alphabet,infinite sequence,constant length | Journal | 292 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 33 |
PageRank | References | Authors |
2.68 | 15 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jean-Paul Allouche | 1 | 324 | 49.98 |
Michael Baake | 2 | 33 | 3.01 |
Julien Cassaigne | 3 | 282 | 40.80 |
David Damanik | 4 | 97 | 11.19 |