Palindromes in infinite ternary words

Balková, L'ubomíra ; Pelantová, Edita  ; Starosta, Štěpán

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 4, pp. 687-702

Résumé

We study infinite words $𝐮$ over an alphabet $𝒜$ satisfying the property $𝒫:𝒫\left(n\right)+𝒫(n+1)=1+\#𝒜\mathrm{for}\mathrm{any}n\in \mathbb{N}$, where $𝒫\left(n\right)$ denotes the number of palindromic factors of length $n$ occurring in the language of $𝐮$. We study also infinite words satisfying a stronger property $\mathrm{𝒫ℰ}:\mathrm{every}\mathrm{palindrome}\mathrm{of}𝐮\mathrm{has}\mathrm{exactly}\mathrm{one}\mathrm{palindromic}\mathrm{extension}\mathrm{in}𝐮.$ For binary words, the properties $𝒫$ and $\mathrm{𝒫ℰ}$ coincide and these properties characterize sturmian words, i.e., words with the complexity $𝒞\left(n\right)=n+1$ for any $n\in \mathbb{N}$. In this paper, we focus on ternary infinite words with the language closed under reversal. For such words $𝐮$, we prove that if $𝒞\left(n\right)=2n+1$ for any $n\in \mathbb{N}$, then $𝐮$ satisfies the property $𝒫$ and moreover $𝐮$ is rich in palindromes. Also a sufficient condition for the property $\mathrm{𝒫ℰ}$ is given. We construct a word demonstrating that $𝒫$ on a ternary alphabet does not imply $\mathrm{𝒫ℰ}$.

Détail

DOI : 10.1051/ita/2009016

Classification : 68R15
Keywords: ternary infinite words, palindromes, generalized sturmian words, rich words