On shuffled-square-free words
Résumé
A word u is a shuffle of words v and w, which we denote by u ∈ v⧢w, if u can be obtained by mixing the letters from v and w in a way that preserves the left-to-right ordering of the letters from v and w. In case u∈v⧢v for some word v, the word u is called a shuffled-square. A word u is shuffled-square-free if it does not have a non-empty factor (i.e., non-empty sequence of adjacent letters) that is a shuffled-square. Our contribution in this context is two-fold. First, we prove that there exist arbitrarily long shuffled-square-free words in any alphabet with six letters or more, thereby improving on a previous result of Guégan and Ochem. Furthermore, we show that recognizing shuffled-square-free words on arbitrary alphabets is NP-complete.
Domaines
Informatique [cs]Origine | Fichiers produits par l'(les) auteur(s) |
---|