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.

### On recognising words that are squares for the shuffle product

#### Abstract

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.
##### Scheda breve Scheda completa Scheda completa (DC)
2023
shuffle product, square of the shuffle product, shuffle product of two words, shuffle product of two strings, NP-complete
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11562/1117629`
• ND
• 0
• 0