Mathematics – Combinatorics
Scientific paper
2009-01-27
RAIRO - Theor. Inform. Appl. 43 (2009), 687-702
Mathematics
Combinatorics
12 pages
Scientific paper
We study infinite words u over an alphabet A satisfying the property P : P(n)+ P(n+1) = 1+ #A for any n in N, where 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 PE: every palindrome of u has exactly one palindromic extension in u. For binary words, the properties P and PE coincide and these properties characterize Sturmian words, i.e., words with the complexity C(n)=n+1 for any n in 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 N, then u satisfies the property P and moreover u is rich in palindromes. Also a sufficient condition for the property PE is given. We construct a word demonstrating that P on a ternary alphabet does not imply PE.
Balková Lubomíra
Pelantová Edita
Starosta Štěpán
No associations
LandOfFree
Palindromes in infinite ternary words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Palindromes in infinite ternary words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Palindromes in infinite ternary words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-362225