Extending regular expressions with iterated shuffle (Q1063422)

By using the result operations (union, product, and star), the shuffle operation {Russian{Sh}}, and its closure, the iterated shuffle \(\dag\), the three slip-families \(Shuf:=(v,\text{Russian{Sh}},\dag)(Fin)\), \(ER:=(v,\cdot,*,\dag)(Fin)\) and \(SE:=(v,\cdot,*,\text{Russian{Sh}},\dag)(Fin)\) are studied. While there exists a simple one-counter language L, whose iterated shuffle \(L^{\dag}\) is an NP-complete set [\textit{M. K. Warmuth} and \textit{D. Haussler}, J. Comput. Syst. Sci. 28, 345-358 (1984; Zbl 0549.68039)], it is here shown that the family ER defines only sets that are acceptable by some multicounter language in quasi-realtime, thus are acceptable in nondeterministic logarithmic space and consequently are in P. The result obtained corrects Corollary 3.11 in the author's paper in Theor. Comput. Sci. 14, 127-154 (1981; Zbl 0477.68034), generalizes Theorem 5.1 in the paper of Warmuth and Haussler (loc. cit.), and adds to the research by Shaw, Riddle, Kimura, Araki and Tokura, Slutzki, and others.