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

We study infinite words $𝐮$ over an alphabet $𝒜$ satisfying the property $𝒫:\phantom{\rule{3.33333pt}{0ex}}𝒫\left(n\right)+𝒫\left(n+1\right)=1+#𝒜\phantom{\rule{4pt}{0ex}}\mathrm{for}\phantom{\rule{4pt}{0ex}}\mathrm{any}\phantom{\rule{4pt}{0ex}}n\in ℕ$, 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{𝒫ℰ}:\phantom{\rule{3.33333pt}{0ex}}\mathrm{every}\phantom{\rule{4pt}{0ex}}\mathrm{palindrome}\phantom{\rule{4pt}{0ex}}\mathrm{of}\phantom{\rule{4pt}{0ex}}𝐮\phantom{\rule{4pt}{0ex}}\mathrm{has}\phantom{\rule{4pt}{0ex}}\mathrm{exactly}\phantom{\rule{4pt}{0ex}}\mathrm{one}\phantom{\rule{4pt}{0ex}}\mathrm{palindromic}\mathrm{extension}\phantom{\rule{4pt}{0ex}}\mathrm{in}\phantom{\rule{4pt}{0ex}}𝐮.$ 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 ℕ$. 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 ℕ$, 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{𝒫ℰ}$.

DOI: 10.1051/ita/2009016
Classification: 68R15
Keywords: 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},
zbl = {1191.68476},
mrnumber = {2589989},
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
DA  - 2009///
SP  - 687
EP  - 702
VL  - 43
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2009016/
UR  - https://zbmath.org/?q=an%3A1191.68476
UR  - https://www.ams.org/mathscinet-getitem?mr=2589989
UR  - https://doi.org/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 https://doi.org/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, Volume 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

Cited by Sources: