Mathematics – Combinatorics
Scientific paper
2006-03-26
Mathematics
Combinatorics
16 pages, submitted to Theoretical Computer Science
Scientific paper
We study the relation between the palindromic and factor complexity of infinite words. We show that for uniformly recurrent words one has P(n)+P(n+1) \leq \Delta C(n) + 2, for all n \in N. For a large class of words it is a better estimate of the palindromic complexity in terms of the factor complexity then the one presented by Allouche et al. We provide several examples of infinite words for which our estimate reaches its upper bound. In particular, we derive an explicit prescription for the palindromic complexity of infinite words coding r-interval exchange transformations. If the permutation \pi connected with the transformation is given by \pi(k)=r+1-k for all k, then there is exactly one palindrome of every even length, and exactly r palindromes of every odd length.
Baláži Peter
Masáková Zuzana
Pelantová Edita
No associations
LandOfFree
Factor versus palindromic complexity of uniformly recurrent infinite words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Factor versus palindromic complexity of uniformly recurrent infinite words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Factor versus palindromic complexity of uniformly recurrent infinite words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-607935