Complexity of Some Problems Concerning Lindenmayer Systems. (Revised version)

Abstract

We determine the computational complexity of membership, emptiness and infiniteness for several types of L systems. The L systems we consider are EDOL, EOL, EDTOL, and ETOL, with and without empty productions. For each problem and each type of system we establish both upper and lower bounds on the time or memory required for solution by Turing machines.

Revised version (first version 1978 under the title Complexity of Some Problems Concerning: Lindenmayer Systems)