Upper Bounds on the Complexity of Some Problems Concerning L Systems

Abstract

We determine the computational complexity of some decidable problems concerning several types of Lindenmayer systems. The problems are membership, emptiness and finiteness; the L systems are the ED0L, E0L, EDT0L and ET0L systems. For each problem and type of system we establish upper bounds on the time or memory required for solution by Turing machines. This paper contains algorithms achieving the upper bounds, and a companion paper (PB-70) contains proofs of lower bounds.