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 languagesare contained in one-way-NSPACE(log n) and in P.In this paper we show that nondeterministic one-way logarithmic spaceis in some sense the lower bound for accepting shuffle languages.Namely, we show that there exists a shuffle language which is notaccepted by any deterministic one-way Turing machine with space bounded bya sublinear function, and that there exists a shuffle language which isnot accepted with less than logarithmic space even if we allow two-waynondeterministic Turing machines.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 1999