Shuffle languages are in P (Q1589415)

In this paper we show that shuffle languages are contained in one-way-NSPACE\((\log n)\) thus in P. We consider the class of shuffle languages which emerges from the class of finite languages through regular operations (union, concatenation, Kleene star) and shuffle operations (shuffle and shuffle closure). For every shuffle expression \(E\) we construct a shuffle automaton which accepts the language generated by \(E\) and we show that the automaton can be simulated by a one-way nondeterministic Turing machine in logarithmic space.