Extending regular expressions with iterated shuffle

AbstractIt is shown that every finite expression which uses the operations union, product, Kleene star, and iterated shuffle in any order, starting with finite sets, defines a language which can be recognized non-deterministically by some multicounter machine in quasirealtime. It is known that this family is in general not closed with respect to iterated shuffle. As a consequence of the characterization each such language is in NSPACE(log n) and thus in P. However, if P ≠ NP, then also neither P nor NSPACE(log n) are closed under iterated shuffle. The proof uses the new concept of so-called shuffle schemes and a number of results on algebraic language theory