Open AccessComplexity of Some Problems Concerning Lindenmayer Systems. (Revised version)
Author(s) -
Neil D. Jones,
Sven Skyum
Publication year - 1979
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v7i85.6501
Subject(s) - turing , computational complexity theory , mathematics , turing machine , emptiness , computer science , algorithm , discrete mathematics , computation , programming language , philosophy , theology
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 )