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

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

DOI : 10.1051/ita/2009016
Classification : 68R15
Mots clés : ternary infinite words, palindromes, generalized sturmian words, rich words
@article{ITA_2009__43_4_687_0,
     author = {Balkov\'a, L'ubom{\'\i}ra and Pelantov\'a, Edita and Starosta, \v{S}t\v{e}p\'an},
     title = {Palindromes in infinite ternary words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {687--702},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {4},
     year = {2009},
     doi = {10.1051/ita/2009016},
     mrnumber = {2589989},
     zbl = {1191.68476},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2009016/}
}
TY  - JOUR
AU  - Balková, L'ubomíra
AU  - Pelantová, Edita
AU  - Starosta, Štěpán
TI  - Palindromes in infinite ternary words
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
SP  - 687
EP  - 702
VL  - 43
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2009016/
DO  - 10.1051/ita/2009016
LA  - en
ID  - ITA_2009__43_4_687_0
ER  - 
%0 Journal Article
%A Balková, L'ubomíra
%A Pelantová, Edita
%A Starosta, Štěpán
%T Palindromes in infinite ternary words
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2009
%P 687-702
%V 43
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2009016/
%R 10.1051/ita/2009016
%G en
%F ITA_2009__43_4_687_0
Balková, L'ubomíra; Pelantová, Edita; Starosta, Štěpán. Palindromes in infinite ternary words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 4, pp. 687-702. doi : 10.1051/ita/2009016. http://www.numdam.org/articles/10.1051/ita/2009016/

[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. | EuDML | Numdam | MR | Zbl

[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 | Zbl

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

[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 | Zbl

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

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

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

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

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

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

Cité par Sources :