On recognising words that are squares for the shuffle product

The shuffle of two strings u and v is the language consisting of all strings obtainable by merging u and v from left to right, while choosing the next symbol arbitrarily from u or v. All strings in the shuffle of u and v have length |u|+|v|. A word is a square for the shuffle product if it is the shuffle of two identical words. Whereas it can be decided in polynomial-time whether or not a string s belongs to the shuffle of two strings u and v (J.-C. Spehner, 1986 [19]), we show in this paper that it is NP-complete to determine whether or not a string s is a square for the shuffle product. The novelty in our approach lies in representing words as linear graphs, in which deciding whether or not a given word is a square for the shuffle product reduces to computing some inclusion-free perfect matching. Finally, we prove that it is NP-complete to determine whether or not an input word is in the shuffle of a word with its reverse.