Open AccessComplexity of some Problems Concerning L Systems. (Preliminary report)
Author(s) -
Neil D. Jones
Publication year - 1976
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v5i67.6485
Subject(s) - decidability , mathematical proof , turing machine , time hierarchy theorem , emptiness , upper and lower bounds , computer science , computational complexity theory , turing , time complexity , theoretical computer science , mathematics , state (computer science) , discrete mathematics , algorithm , programming language , universal turing machine , philosophy , epistemology , mathematical analysis , geometry , computation
We study the computational complexity of some decidable 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 state both upper and lower bounds on the time or memory required for solution by Turing machines. Two following papers (PB-69 and PB70) will contain detailed constructions and proofs for the upper and lower bounds.