Lower Bounds on the Complexity of Some Problems: Concerning L Systems

Abstract

This is the second of two papers on the complexity of deciding membership, emptiness and finiteness of four basic types of Lindenmayer systems: the ED0L, E0L, EDT0L and ET0L systems. For each problem and type of system we establish lower bounds on the time or memory required for solution by Turing machines, using reducibility techniques. These bounds, combined with the upper bounds of the preceding paper, show many of these problems to be complete for NP or PSPACE.