A connection between palindromic and factor complexity using return words
arXiv:0802.1332 · doi:10.1016/j.aam.2008.03.005
Abstract
In this paper we prove that for any infinite word W whose set of factors is closed under reversal, the following conditions are equivalent: (I) all complete returns to palindromes are palindromes; (II) P(n) + P(n+1) = C(n+1) - C(n) + 2 for all n, where P (resp. C) denotes the palindromic complexity (resp. factor complexity) function of W, which counts the number of distinct palindromic factors (resp. factors) of each length in W.
17 pages; minor adjustment to the main theorem and other minor changes (particularly in Sections 3 and 4); accepted by "Advances in Applied Mathematics"
References in corpus (1)
Cited by in corpus (20)
- Palindromic Richness
- A new characteristic property of rich words
- Rich, Sturmian, and trapezoidal words
- On the least number of palindromes contained in an infinite word
- Languages invariant under more symmetries: overlapping factors versus palindromic richness
- Extensions of rich words
- Infinite Words with Finite Defect
- On Theta-palindromic Richness
- Palindromic richness for languages invariant under more symmetries
- Proof of Brlek-Reutenauer conjecture
- Upper Bound for Palindromic and Factor Complexity of Rich Words
- On Brlek-Reutenauer conjecture
- Constructions of words rich in palindromes and pseudopalindromes
- Morphic images of episturmian words having finite palindromic defect
- Infinite words rich and almost rich in generalized palindromes
- Generalized Thue-Morse words and palindromic richness
- On Words with the Zero Palindromic Defect
- On the Zero Defect Conjecture
- Sturmian Jungle (or Garden?) on Multiliteral Alphabets
- Palindromes In Sturmian Strings