Palindromic factorization of rich words
share
A finite word w is called rich if it contains | w|+1 distinct palindromic factors including the empty word. For every finite rich word w there are distinct nonempty palindromes w_1, w_2,…,w_p such that w=w_pw_p-1⋯ w_1 and w_i is the longest palindromic suffix of w_pw_p-1⋯ w_i, where 1≤ i≤ p. This palindromic factorization is called UPS-factorization. Let luf(w)=p be the length of UPS-factorization of w. In 2017, it was proved that there is a constant c such that if w is a finite rich word and n=| w| then luf(w)≤ cn/lnn. We improve this result as follows: There are constants μ, π such that if w is a finite rich word and n=| w| then luf(w)≤μn/e^π√(lnn) The constants c,μ,π depend on the size of the alphabet.
READ FULL TEXT