Lower Bounds on the Complexity of Some Problems: Concerning L Systems
DOI:
https://doi.org/10.7146/dpb.v6i70.6488Resumé
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.Downloads
Publiceret
1977-02-01
Citation/Eksport
Jones, N. D., & Skyum, S. (1977). Lower Bounds on the Complexity of Some Problems: Concerning L Systems. DAIMI Report Series, 6(70). https://doi.org/10.7146/dpb.v6i70.6488
Nummer
Sektion
Articles
Licens
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.