On recognising words that are squares for the shuffle product - Models and Algorithms
Journal Articles Theoretical Computer Science Year : 2023

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

Romeo Rizzi
• Function : Author
• PersonId : 1011885
Stéphane Vialette

#### Abstract

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.

#### Domains

Data Structures and Algorithms [cs.DS]

### Dates and versions

hal-04498180 , version 1 (11-03-2024)

### Identifiers

• HAL Id : hal-04498180 , version 1
• DOI :

### Cite

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⟩

### Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

173 View