Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420671 | Discrete Applied Mathematics | 2009 | 7 Pages |
We study some properties of palindromic (scattered) subwords of binary words. In view of the classical problem on subwords, we show that the set of palindromic subwords of a word characterizes the word up to reversal.Since each word trivially contains a palindromic subword of length at least half of its length–a power of the prevalent letter–we call a word that does not contain any palindromic subword longer than half of its length minimal palindromic. We show that every minimal palindromic word is abelian unbordered, that is, no proper suffix of the word can be obtained by permuting the letters of a proper prefix.We also propose to measure the degree of palindromicity of a word ww by the ratio |rws|/|w||rws|/|w|, where the word rwsrws is minimal palindromic and rsrs is as short as possible. We prove that the ratio is always bounded by four, and construct a sequence of words that achieves this bound asymptotically.