Issue |
RAIRO-Theor. Inf. Appl.
Volume 43, Number 4, October-December 2009
|
|
---|---|---|
Page(s) | 687 - 702 | |
DOI | https://doi.org/10.1051/ita/2009016 | |
Published online | 15 September 2009 |
Palindromes in infinite ternary words
1
Doppler Institute & Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, Praha 2 120 00, Czech Republic; l.balkova@centrum.cz
2
Doppler Institute & Department of Mathematics, FNSPE, Czech Technical University in
Prague, Trojanova 13, Praha 2 120 00, Czech Republic; edita.pelantova@fjfi.cvut.cz
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; starosta@iml.univ-mrs.fr
Received:
3
February
2009
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.