On Recognizing Words That Are Squares for the Shuffle ProductComputer Science – Theory and Applications

The shuffle of two words u and v of A* is the language u ш v consisting of all words u 1 v 1 u 2 v 2 …u k v k , where k ≥ 0 and the u i and the v i are the words of A* such that u = u 1 u 2 …u k and v = v 1 v 2 …v k . A word u ∈ A* is a square for the shuffle product if it is the shuffle of two identical words (i.e., u ∈ v ш v for some v ∈ A *). Whereas, it can be tested in polynomial-time whether or not u ∈ v 1 ш v 2 for given words u, v 1 and v 2 [J.-C. Spehner, Le Calcul Rapide des Mélanges de Deux Mots, Theoretical Computer Science, 1986], we show in this paper that it is NP-complete to determine whether or not a word u 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