Upper Bounds on the Complexity of Some Problems Concerning L Systems
DOI:
https://doi.org/10.7146/dpb.v6i69.6487Abstract
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.Downloads
Published
1977-02-01
How to Cite
Jones, N. D., & Skyum, S. (1977). Upper Bounds on the Complexity of Some Problems Concerning L Systems. DAIMI Report Series, 6(69). https://doi.org/10.7146/dpb.v6i69.6487
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.