Complexity of Some Problems Concerning Lindenmayer Systems. (Revised version)
DOI:
https://doi.org/10.7146/dpb.v7i85.6501Abstract
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)
Downloads
Published
1979-01-01
How to Cite
Jones, N. D., & Skyum, S. (1979). Complexity of Some Problems Concerning Lindenmayer Systems. (Revised version). DAIMI Report Series, 7(85). https://doi.org/10.7146/dpb.v7i85.6501
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.