UPPER BOUND FOR PALINDROMIC AND FACTOR COMPLEXITY OF RICH WORDS

摘要

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) subset of 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 delta = 3/2(ln3-ln2). In particular we show thatvertical bar Fac(w)(n)vertical bar = (4q(2)n)(delta ln 2n+2).In 2007, Balazi, Masakova, and Pelantova showed thatvertical bar Pal(w)(n)vertical bar + vertical bar Pal(w)(n+1)vertical bar = vertical bar Fac(w)(n+1) - vertical bar Fac(w)(n)vertical bar+2,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.