On recognising words that are squares for the shuffle product

Romeo Rizzi (1) , Stéphane Vialette (2)

1 UNIVR - Università degli studi di Verona = University of Verona
2 LIGM - Laboratoire d'Informatique Gaspard-Monge

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\dots u_k{v}_k$, where $k\ge 0$ and the $u_i$ and $v_i$ are words of $A^{⁎}$ such that $u=u_1{u}_2\dots u_k$ and $v=v_1{v}_2\dots v_k$. In other words, $u⧢v$ is the finite set of all words obtainable from merging the words u and v from left to right, but choosing the next symbol arbitrarily from u or v. A word $u\in A^{⁎}$ is a square for the shuffle product if it is the shuffle of two identical words (i.e., $u\in v⧢v$ for some $v\in A^{⁎}$).

Whereas it can be decided in polynomial-time whether or not $u\in v_1⧢v_2$ for given words u, $v_1$ and $v_2$ (J.-C. Spehner, 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. 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.

Mots clés: combinatorics on words; shuffle operator; complexity

Domaines: Algorithme et structure de données [cs.DS]

Romeo Rizzi, Stéphane Vialette. On recognising words that are squares for the shuffle product. Theoretical Computer Science, 2023, 956, pp.111156.1-16. ⟨10.1016/j.tcs.2017.04.003⟩. ⟨hal-04498180⟩