Palindromes in infinite ternary words
L'ubomíra Balková; Edita Pelantová; Štěpán Starosta
RAIRO - Theoretical Informatics and Applications (2009)
- Volume: 43, Issue: 4, page 687-702
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topBalková, L'ubomíra, Pelantová, Edita, and Starosta, Štěpán. "Palindromes in infinite ternary words." RAIRO - Theoretical Informatics and Applications 43.4 (2009): 687-702. <http://eudml.org/doc/250572>.
@article{Balková2009,
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 of
palindromic factors of length n occurring in the language of u.
We study also infinite words satisfying a stronger property
$\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 words
with 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\}$ and
moreover 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 ternary
alphabet does not imply $\mathcal\{PE\}$.
},
author = {Balková, L'ubomíra, Pelantová, Edita, Starosta, Štěpán},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Ternary infinite words; palindromes; generalized Sturmian words; rich words.; ternary infinite words; rich words},
language = {eng},
month = {9},
number = {4},
pages = {687-702},
publisher = {EDP Sciences},
title = {Palindromes in infinite ternary words},
url = {http://eudml.org/doc/250572},
volume = {43},
year = {2009},
}
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
DA - 2009/9//
PB - EDP Sciences
VL - 43
IS - 4
SP - 687
EP - 702
AB -
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 of
palindromic factors of length n occurring in the language of u.
We study also infinite words satisfying a stronger property
$\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 words
with 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}$ and
moreover 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 ternary
alphabet does not imply $\mathcal{PE}$.
LA - eng
KW - Ternary infinite words; palindromes; generalized Sturmian words; rich words.; ternary infinite words; rich words
UR - http://eudml.org/doc/250572
ER -
References
top- P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France119 (1991) 199–215.
- 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.
- 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.
- J. Cassaigne, Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.
- X. Droubay, G. Pirillo, Palindromes and Sturmian words. Theoret. Comput. Sci.223 (1999) 73–85.
- J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theoret. Comput. Sci.276 (2002) 281–313.
- M. Morse and G.A. Hedlund, Symbolic dynamics II – Sturmian trajectories. Amer. J. Math.62 (1940) 1–42.
- G. Rote, Sequences with subword complexity 2n. J. Number Theor.46 (1993) 196–213.
- L. Vuillon, A characterization of Sturmian words by return words. Eur. J. Combin.22 (2001) 263–275.
Citations in EuDML Documents
topNotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.