Combinatorical and Algebraic Structures Seminar
Session details
| Date: | 27.4.2007 |
| Speaker: | Edita Pelantová, FJFI, České vysoké učení technické |
| Title: | Factor versus palindromic complexity of uniformly reccurent infinite words |
| Abstract: | (spoluautoři: P. Baláži, Z. Masáková) We study the relation between the palindromic and factor complexity of infinite words. We show that for uniformly recurrent words one has $\mathcal{P}(n)+\mathcal{P}(n+1) \leq \Delta {\mathcal 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 than the estimate given by Allouche, Baake, Cassaigne and Damanik. 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. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož