Open AccessA Note on the Complexity of General D0L Membership
Author(s) -
Neil D. Jones
Publication year - 1979
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v8i93.6509
Subject(s) - nondeterministic algorithm , upper and lower bounds , mathematics , combinatorics , space (punctuation) , discrete mathematics , computer science , mathematical analysis , operating system
A number of upper and lower bounds have been obtained for various problems concerning L systems (see PB-85). In most cases the bounds were rather close; however, for the general membership problem the upper bound was P, and the lower was deterministic log space. In this note we show that membership can be decided deterministically in log^2 n space, which makes it very unlikely that the problem is complete for P. We also show that non-membership is as hard as any problem solvable in nondeterministic log n space. Thus both bounds are improved.