Open AccessLower Bounds on the Complexity of Some Problems: Concerning L Systems
Author(s) -
Neil D. Jones,
Sven Skyum
Publication year - 1977
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v6i70.6488
Subject(s) - turing machine , pspace , turing , mathematics , upper and lower bounds , time hierarchy theorem , emptiness , time complexity , dtime , discrete mathematics , computer science , type (biology) , computational complexity theory , combinatorics , theoretical computer science , algorithm , universal turing machine , computation , mathematical analysis , ecology , philosophy , theology , biology , programming language
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.