Palindromes in infinite ternary words

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

doi:10.1051/ita/2009016

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 $𝒫 : 𝒫 (n) + 𝒫 (n + 1) = 1 + # 𝒜 for any n \in ℕ$ , 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 ℕ$ . In this paper, we focus on ternary infinite words with the language closed under reversal. For such words $𝐮$ , we prove that if $𝒞 (n) = 2 n + 1$ for any $n \in ℕ$ , 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 $𝒫ℰ$ .

EuDML MR Zbl | 1 citation dans Numdam

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/

Bibliographie
Cité par

[1] P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité $2 n + 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 $2 n$ . 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 :