Upper bound for palindromic and factor complexity of rich words

Department of Mathematics, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, 166 36 Prague 6, Czechia.

^* Corresponding author: josef.rukavicka@seznam.cz

Received: 23 October 2019
Accepted: 11 December 2020

Abstract

A finite word w of length n contains at most n + 1 distinct palindromic factors. If the bound n + 1 is attained, the word w is called rich. An infinite word w is called rich if every finite factor of w is rich.

Let w be a word (finite or infinite) over an alphabet with q > 1 letters, let Fac_w(n) be the set of factors of length n of the word w, and let Pal_w(n) ⊆ Fac_w(n) be the set of palindromic factors of length n of the word w.

We present several upper bounds for |Fac_w(n)| and |Pal_w(n)|, where w is a rich word. Let δ = . In particular we show that

In 2007, Baláži, Masáková, and Pelantová showed that

where w is an infinite word whose set of factors is closed under reversal. We prove this inequality for every finite word v with |v| ≥ n + 1 and _v(n + 1) closed under reversal.