Generalized trapezoidal words (Q490909)

The factor complexity \(C_w(n)\) of a word \(w\) of length \(\ell\) is the function that, for each \(n\in\{0,1,\dots,\ell\}\), returns the number of distinct factors of \(w\) of length \(n\). The word \(w\) is called trapezoidal if \(C_w(n)\) increases by 1 for each \(n\) in the interval \([0,r]\) for some \(r\leq\ell/2\), is constant for each \(n\) in the interval \([r,\ell-r]\), and decreases by 1 for each \(n\) in the interval \([\ell-r,\ell]\). Any trapezoidal word is necessarily over a binary alphabet. The authors suggest the following generalization. A word \(w\) of length \(\ell\) is called a generalized trapezoidal word (GT-word) if there exist positive integers \(m, M\) with \(m\leq M\leq\ell\) such that \(C_w(n)\) increases by 1 for each \(n\) in the interval \([1,m]\), is constant for each \(n\) in the interval \([m,M]\), and decreases by 1 for each \(n\) in the interval \([M,\ell]\). GT-words exist over any alphabet and the binary GT-words are precisely the trapezoidal words. The first main result of the paper (Theorem 17) nicely characterizes GT-words in terms of their hearts where the heart of a word \(w\) that contains at least two occurrences of some letter is the unique factor of \(w\) that remains if one erases the longest prefix and the longest suffix of \(w\) that contain letters only occurring once in \(w\). A word of length \(\ell\) is rich if it has \(\ell+1\) distinct palindromic factors. The second main result (Theorem 27) gives a complete characterization of the rich GT-words in terms of the hearts and the longest palindromic prefixes and suffixes of the hearts; its proof in the paper is very technical.