A connection between palindromic and factor complexity using return words

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:

  1. all complete returns to palindromes are palindromes;

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

Publication
Advances in Applied Mathematics