A connection between palindromic and factor complexity using return words

Bucci, M., Deluca, A., Glen, A. and Zamboni, L. (2009) A connection between palindromic and factor complexity using return words. Advances in Applied Mathematics, 42 (1). pp. 60-74.

PDF - Authors' Version Download (234kB)

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.