Lower Space Bounds for Accepting Shuffle Languages
In [6] it was shown that shuffle languages are contained in one-way-NSPACE(log n) and in P. In this paper we show that nondeterministic one-way logarithmic space is in some sense the lower bound for accepting shuffle languages. Namely, we show that there exists a shuffle language which is not accepted by any deterministic one-way Turing machine with space bounded by a sublinear function, and that there exists a shuffle language which is not accepted with less than logarithmic space even if we allow...