A Note on the Complexity of General D0L Membership
DOI:
https://doi.org/10.7146/dpb.v8i93.6509Abstract
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.Downloads
Published
1979-01-01
How to Cite
Jones, N. D. (1979). A Note on the Complexity of General D0L Membership. DAIMI Report Series, 8(93). https://doi.org/10.7146/dpb.v8i93.6509
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.