L Systems and Nlog — Reductions

Jones and Skyum in [J Sk 77], [J Sk 79], and [J Sk 81], as well as, van Leeuwen in [vL] and Sudborough in [Su77] classified the complexities of various problems concerning L systems. This was done by showing these problems, formulated as languages, to be complete for complexity classes like NSPACE(log n), DTIME(Poly), NTIME(Poly), or DSPACE(Poly) with respect to deterministic logarithmic space-bounded many-one reductions. The aim of this paper is to do the same for fixed membership problems of context-free L systems with respect to nondeterministic log-space bounded many-one reductions (see [Lan 84]).