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), p. 687-702 / Harvested from Numdam

Résumé

We study infinite words $\mathbf {u}$ over an alphabet $\mathcal {A}$ satisfying the property $\mathcal {P} :~\mathcal {P}(n)+ \mathcal {P}(n+1) = 1+ \#\mathcal {A}\ {\rm for\ any}\ n \in \mathbb {N}$, where $\mathcal {P}(n)$ denotes the number of palindromic factors of length $n$ occurring in the language of $\mathbf {u}$. We study also infinite words satisfying a stronger property $ \mathcal {PE}:~{\rm every\ palindrome\ of}\ \mathbf {u}\ {\rm has\ exactly\ one\ palindromic} {\rm extension\ in}\ \mathbf {u}. $ For binary words, the properties $\mathcal {P}$ and $\mathcal {PE}$ coincide and these properties characterize sturmian words, i.e., words with the complexity $\mathcal {C}(n)=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 $\mathbf {u}$, we prove that if $\mathcal {C}(n)=2n+1$ for any $n \in \mathbb {N}$, then $\mathbf {u}$ satisfies the property $\mathcal {P}$ and moreover $\mathbf {u}$ is rich in palindromes. Also a sufficient condition for the property $\mathcal {PE}$ is given. We construct a word demonstrating that $\mathcal {P}$ on a ternary alphabet does not imply $\mathcal {PE}$.

Détail

Publié le : 2009-01-01

MR 2589989 | Zbl pre05650344 | Zbl 1191.68476

DOI : https://doi.org/10.1051/ita/2009016
Classification:  68R15

Bibliographie

[1] P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité $2n+1$. Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | MR 1116845 | Zbl 0789.28011

[2] P. Baláži, Z. Masáková and E. Pelantová, Factor versus palindromic complexity of uniformly recurrent infinite words. Theoret. Comput. Sci. 380 (2007) 266-275. | MR 2330997 | Zbl 1119.68137

[3] L'. Balková, E. Pelantová and W. Steiner, Sequences with constant number of return words. Monatsh. Math. 155 (2008) 251-263. | MR 2461579 | Zbl 1185.68503 | Zbl pre05566999

[4] M. Bucci, A. De Luca, A. Glen and L.Q. Zamboni, A connection between palindromic and factor complexity using return words. Adv. Appl. Math. 42 (2009) 60-74. | MR 2475313 | Zbl 1160.68027

[5] J. Cassaigne, Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67-88. | MR 1440670 | Zbl 0921.68065

[6] X. Droubay, G. Pirillo, Palindromes and Sturmian words. Theoret. Comput. Sci. 223 (1999) 73-85. | MR 1704637 | Zbl 0930.68116

[7] J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281-313. | MR 1896357 | Zbl 1002.68116

[8] M. Morse and G.A. Hedlund, Symbolic dynamics II - Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM 66.0188.03 | MR 745

[9] G. Rote, Sequences with subword complexity $2n$. J. Number Theor. 46 (1993) 196-213. | MR 1269252 | Zbl 0804.11023

[10] L. Vuillon, A characterization of Sturmian words by return words. Eur. J. Combin. 22 (2001) 263-275. | MR 1808196 | Zbl 0968.68124