On the complexity of iterated shuffle

摘要

It is demonstrated that the following problems are NP complete: 1.(1) Given words w and w1, w2, …, wn, is w in the shuffle of w1, w2, …, wn?2.(2) Given words w and v, is w in the iterated shuffle of v? From these results we show that the languages {$w¢wR: w σ {a, b}∗}∅, wσ{a,b}∗ $w)∅, {abncdenf: n ⩾ 0}∅, and {an+1bncnfn: n ⩾ 0∅ are NP complete, where ∅ 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.