On the complexity of iterated shuffle (Q800086)

It is demonstrated that the following problems are NP complete: (1) Given words w and \(w_ 1,w_ 2,...,w_ n,\) is w in the shuffle of \(w_ 1,w_ 2,...,w_ n?\) (2) Given words w and v, is w in the iterated shuffle of v? From these results we show that the languages \(\{{\$}wc\!| w^ R:w\in\{a,b\}^*\}^{\odot}, \cup_{w\in\{a,b\}^*}({\$}w)^{\odot}, \{ab^ ncde^ nf:n\geq 0\}^{\odot},\) and \(\{a^{n+1}b^ nc^ nf^ n:n\geq 0\}^{\odot}\) are NP complete, where \(\odot\) denotes the iterated shuffle. By representing these languages in various ways using the operations shuffle, iterated shuffle, union, concatenation, intersection, intersection with a regular set, non-erasing homomorphism and inverse homomorphism, results on the complexity of language classes generated using various subsets of these operations are obtained. Finally, it is shown that the iterated shuffle of a regular set can be recognized in deterministic polynomial time. Further results: We can show that \(\{ab^ nc)^ 2:n\geq 0\}^{\odot}\) and \(\{a(a^ nb^ n)^ 2:n\geq 0\}^{\odot}\) are NP-complete.