RAIRO-Theor. Inf. Appl.
Volume 43, Number 4, October-December 2009
|Page(s)||687 - 702|
|Published online||15 September 2009|
Palindromes in infinite ternary words
Doppler Institute & Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, Praha 2 120 00, Czech Republic; email@example.com
2 Doppler Institute & Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, Praha 2 120 00, Czech Republic; firstname.lastname@example.org
3 Institut de Mathématiques de Luminy, Campus de Luminy, Case 907, 13288 Marseille Cedex 9, France.
4 Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, Praha 2 120 00, Czech Republic; email@example.com
Accepted: 9 June 2009
We study infinite words u over an alphabet satisfying the property , where denotes the number of palindromic factors of length n occurring in the language of u. We study also infinite words satisfying a stronger property : every palindrome of u has exactly one palindromic extension in u. For binary words, the properties and coincide and these properties characterize Sturmian words, i.e., words with the complexity C(n) = n + 1 for any . In this paper, we focus on ternary infinite words with the language closed under reversal. For such words u, we prove that if C(n) = 2n + 1 for any , then u satisfies the property and moreover u 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 .
Mathematics Subject Classification: 68R15
Key words: Ternary infinite words / palindromes / generalized Sturmian words / rich words.
© EDP Sciences, 2009
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.