A Unique Extension of Rich Words
share
A word w is called rich if it contains | w|+1 palindromic factors, including the empty word. We say that a rich word w can be extended in at least two ways if there are two distinct letters x,y such that wx,wy are rich. Let R denote the set of all rich words. Given w∈ R, let K(w) denote the set of all words such that if u∈ K(w) then wu∈ R and wu can be extended in at least two ways. Let ω(w)=min{| u|t | u∈ K(w)} and let ϕ(n)=max{ω(w)| w∈ R| w|=n}, where n>0. Vesti (2014) showed that ϕ(n)≤ 2n. In other words, it says that for each w∈ R there is a word u with | u|≤ 2| w| such that wu∈ R and wu can be extended in at least two ways. We prove that ϕ(n)≤ n. In addition we prove that for each real constant c>0 and each integer m>0 there is n>m such that ϕ(n)≥ (2/9-c)n. The results hold for each finite alphabet having at least two letters.
READ FULL TEXT