Palindromic factorization of rich words

Abstract: A finite word

w

is called emph{rich} if it contains

v e r t w v e r t + 1

distinct palindromic factors including the empty word. For every finite rich word

w

there are distinct nonempty palindromes

w_{1}, w_{2}, d o t s, w_{p}

such that

w = w_{p} w_{p - 1} c d o t s w_{1}

and

w_{i}

is the longest palindromic suffix of

w_{p} w_{p - 1} c d o t s w_{i}

, where

1 l e q i l e q p

. This palindromic factorization is called emph{UPS-factorization}. Let

l u f (w) = p

be emph{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 = v e r t w v e r t

then

l u f (w) l e q c f r a c n l n n

. We improve this result as follows: There are constants

m u, p i

such that if

w

is a finite rich word and

n = v e r t w v e r t

then [luf(w)leq mufrac{n}{e^{pisqrt{ln{n}}}}mbox{.}] The constants

c, m u, p i

depend on the size of the alphabet.

This page was built for publication: Palindromic factorization of rich words