Factor versus palindromic complexity of uniformly recurrent infinite words

Simple item page
dc.creatorBaláži, Peter
dc.creatorMasáková, Zuzana
dc.creatorPelantová, Edita
dc.date2006-03-26
dc.date.accessioned2026-07-07T07:07:14Z
dc.date.available2026-07-07T07:07:14Z
dc.descriptionWe 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 Δ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 π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.
dc.description16 pages, submitted to Theoretical Computer Science
dc.identifierhttps://arxiv.org/abs/math/0603607
dc.identifierhttp://arxiv.org/abs/math/0603607
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/110317
dc.subjectCombinatorics
dc.subject68R15
dc.titleFactor versus palindromic complexity of uniformly recurrent infinite words
dc.typetext

Files

Collections

arXiv