Lower Space Bounds for Accepting Shuffle Languages
Institute of Mathematics,
University of Gdańsk,
ul Wita Stwosza 57, 80952 Gdańsk, Poland
Accepted: 18 July 1999
In  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 two-way nondeterministic Turing machines.
Mathematics Subject Classification: 68Q15 / 68Q45
© EDP Sciences, 1999