No CrossRef data available.
Article contents
Lower Space Bounds for Accepting Shuffle Languages
Published online by Cambridge University Press: 15 August 2002
Abstract
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 two-way nondeterministic Turing machines.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 1999