Palindrome complexity

2001/06/14 by Jean-Paul Allouche, Michael Baake, Julien Cassaigne +1 · 2 citations
Mathematics · #math.CO

paper · pdf

published as Theor. Comput. Science 292 (2003) 9 - 31 · 24 pages, dedicated to Jean Berstel for his 60th birthday

arxiv created 2001/06/14 · arxiv updated 2009/11/30

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 the class P substitutions of Hof-Knill-Simon. We also give an upper bound for the palindrome complexity of a sequence in terms of its (block-)complexity.

Cited by

• On some 2-binomial coefficients of binary words: geometrical interpretation, partitions of integers, and fair words
• Density Characterization with The Upper Bound of Density of Fibonacci Word

Related

• Factor versus palindromic complexity of uniformly recurrent infinite words
• Palindromic length complexity and a generalization of Thue-Morse sequences
• Palindromic length of words and morphisms in class P
• Palindromic complexity of infinite words associated with non-simple Parry numbers
• Palindromic complexity of infinite words associated with simple Parry numbers