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

Abstract

top
We study infinite words u over an alphabet 𝒜 satisfying the property 𝒫 : 𝒫 ( n ) + 𝒫 ( n + 1 ) = 1 + # 𝒜 for any n , where 𝒫 ( 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 𝒫ℰ : 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 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 , 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 𝒫ℰ .

How to cite

top

Balková, 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
  1. P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France119 (1991) 199–215.  Zbl0789.28011
  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.  Zbl1119.68137
  3. L'. Balková, E. Pelantová and W. Steiner, Sequences with constant number of return words. Monatsh. Math. 155 (2008) 251–263.  Zbl1185.68503
  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.  Zbl1160.68027
  5. J. Cassaigne, Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.  Zbl0921.68065
  6. X. Droubay, G. Pirillo, Palindromes and Sturmian words. Theoret. Comput. Sci.223 (1999) 73–85.  Zbl0930.68116
  7. J. Justin and G. Pirillo, Episturmian words and episturmian morphisms. Theoret. Comput. Sci.276 (2002) 281–313.  Zbl1002.68116
  8. M. Morse and G.A. Hedlund, Symbolic dynamics II – Sturmian trajectories. Amer. J. Math.62 (1940) 1–42.  Zbl0022.34003
  9. G. Rote, Sequences with subword complexity 2n. J. Number Theor.46 (1993) 196–213.  Zbl0804.11023
  10. L. Vuillon, A characterization of Sturmian words by return words. Eur. J. Combin.22 (2001) 263–275.  Zbl0968.68124

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.