کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438368 | 690265 | 2007 | 10 صفحه PDF | دانلود رایگان |
We study the relation between the palindromic and factor complexity of infinite words. We show that for uniformly recurrent words one has , for all n∈N. For a large class of words this is a better estimate of the palindromic complexity in terms of the factor complexity than the one presented in [J.-P. Allouche, M. Baake, J. Cassaigne, D. Damanik, Palindrome complexity, Theoret. Comput. Sci. 292 (2003) 9–31]. 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 π connected with the transformation is given by π(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.
Journal: Theoretical Computer Science - Volume 380, Issue 3, 28 June 2007, Pages 266-275