On shuffled-square-free words

Laurent Bulteau (1) , Vincent Jugé (1) , Stéphane Vialette (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

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]

Laurent Bulteau, Vincent Jugé, Stéphane Vialette. On shuffled-square-free words. Theoretical Computer Science, 2023, 941, pp.91-103. ⟨10.1016/j.tcs.2022.10.028⟩. ⟨hal-04290576⟩