Complexity of some Problems Concerning L Systems. (Preliminary report)

Abstract

We study the computational complexity of some decidable 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 state both upper and lower bounds on the time or memory required for solution by Turing machines. Two following papers (PB-69 and PB70) will contain detailed constructions and proofs for the upper and lower bounds.