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

Romeo Rizzi;
2023-01-01

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.
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
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact