We study infinite words over an alphabet satisfying the property , where denotes the number of palindromic factors of length occurring in the language of . We study also infinite words satisfying a stronger property For binary words, the properties and coincide and these properties characterize sturmian words, i.e., words with the complexity for any . In this paper, we focus on ternary infinite words with the language closed under reversal. For such words , we prove that if for any , 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 .
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2009016/
[1] Représentation géométrique de suites de complexité . Bull. Soc. Math. France 119 (1991) 199-215. | EuDML | Numdam | MR | Zbl
and ,[2] Factor versus palindromic complexity of uniformly recurrent infinite words. Theoret. Comput. Sci. 380 (2007) 266-275. | MR | Zbl
, and ,[3] Sequences with constant number of return words. Monatsh. Math. 155 (2008) 251-263. | MR | Zbl
, and ,[4] A connection between palindromic and factor complexity using return words. Adv. Appl. Math. 42 (2009) 60-74. | MR | Zbl
, , and ,[5] Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67-88. | EuDML | MR | Zbl
,[6] Palindromes and Sturmian words. Theoret. Comput. Sci. 223 (1999) 73-85. | MR | Zbl
, ,[7] Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281-313. | MR | Zbl
and ,[8] Symbolic dynamics II - Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM | MR
and ,[9] Sequences with subword complexity . J. Number Theor. 46 (1993) 196-213. | MR | Zbl
,[10] A characterization of Sturmian words by return words. Eur. J. Combin. 22 (2001) 263-275. | MR | Zbl
,Cité par Sources :