A Note on the Complexity of General $D0L$ Membership
Neil Deaton Jones, Sven Skyum · SIAM Journal on Computing · 1981
In [Math. Systems Theory, 13 (1979), pp. 29–43], the authors obtained a number of upper and lower bounds for various problems concerning L-systems. In most cases the bounds were rather close; however, for general $D0L$ membership the upper bound was $\mathcal{P}$, and the lower was deterministic log space. In this note we show that membership can be decided deterministically in $\log ^2 n$ space, which makes it very unlikely that the problem is complete for $\mathcal{P}$. We also show that nonmembership is as hard as any problem solvable in nondeterministic log n space. This is an improved lower bound unless ${\textbf{DSPACE}}(\log n) = {\textbf{NSPACE}}(\log n)$, which is also thought to be very unlikely.