Construction Of A Rich Word Containing Given Two Factors

Abstract

A finite word $w$ with $|w|=n$ contains at most $n+1$ distinct palindromic factors. If the bound $n+1$ is attained, the word $w$ is called \emph{rich}. Let $\Factor(w)$ be the set of factors of the word $w$. It is known that there are pairs of rich words that cannot be factors of a common rich word. However it is an open question how to decide for a given pair of rich words $u,v$ if there is a rich word $w$ such that $\{u,v\}\subseteq \Factor(w)$. We present a response to this open question:\\ If $w_1,w_2,w$ are rich words, $m=\max \{|w_1|,|w_2|\}$, and $\{w_1,w_2\}\subseteq \Factor(w)$ then there exists also a rich word $\bar{w}$ such that $\{w_1,w_2\}\subseteq \Factor(\bar w)$ and $|\bar{w}|\le m{2}^{k(m)+2}$, where $k(m)=(q+1)m^2(4q^{10}m{)}^{{\log }_{2}m}$ and $q$ is the size of the alphabet. Hence it is enough to check all rich words of length equal or lower to $m{2}^{k(m)+2}$ in order to decide if there is a rich word containing factors $w_1,w_2$.