Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-23T02:53:15.419Z Has data issue: false hasContentIssue false

Palindromes in infinite ternary words

Published online by Cambridge University Press:  15 September 2009

L'ubomíra Balková
Affiliation:
Doppler Institute & Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, Praha 2 120 00, Czech Republic; [email protected]
Edita Pelantová
Affiliation:
Doppler Institute & Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, Praha 2 120 00, Czech Republic; [email protected]
Štěpán Starosta
Affiliation:
Institut de Mathématiques de Luminy, Campus de Luminy, Case 907, 13288 Marseille Cedex 9, France. Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, Praha 2 120 00, Czech Republic; [email protected]
Get access

Abstract

We study infinite words 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 ofpalindromic factors of length n occurring in the language of u.We study also infinite words satisfying a strongerproperty $\mathcal{PE}$ : every palindrome of u has exactly one palindromic extension in u. For binary words, the properties $\mathcal{P}$ and $\mathcal{PE}$ coincide and these properties characterize Sturmian words, i.e.,words with the complexity C(n) = n + 1 for any $n \in \mathbb{N}$ . In this paper, we focus on ternary infinite wordswith the language closed under reversal. For such words u,we prove that if C(n) = 2n + 1 for any $n \in \mathbb{N}$ ,then u satisfies the property $\mathcal{P}$ andmoreover 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 ternaryalphabet does not imply $\mathcal{PE}$ .

Type
Research Article
Copyright
© EDP Sciences, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arnoux, P. and Rauzy, G., Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France 119 (1991) 199215. CrossRef
Baláži, P., Masáková, Z. and Pelantová, E., Factor versus palindromic complexity of uniformly recurrent infinite words. Theoret. Comput. Sci. 380 (2007) 266275. CrossRef
L'. Balková, E. Pelantová and W. Steiner, Sequences with constant number of return words. Monatsh. Math. 155 (2008) 251–263.
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.
Cassaigne, J., Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 6788.
Droubay, X., Pirillo, G., Palindromes and Sturmian words. Theoret. Comput. Sci. 223 (1999) 7385. CrossRef
Justin, J. and Pirillo, G., Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002) 281313. CrossRef
Morse, M. and Hedlund, G.A., Symbolic dynamics II – Sturmian trajectories. Amer. J. Math. 62 (1940) 142. CrossRef
Rote, G., Sequences with subword complexity 2n. J. Number Theor. 46 (1993) 196213. CrossRef
Vuillon, L., A characterization of Sturmian words by return words. Eur. J. Combin. 22 (2001) 263275. CrossRef