NOTES ON THE NP-COMPLETENESS OF THE MEMBERSHIP PROBLEM OF ET0L LANGUAGES
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Publ House Bulgarian Acad Sci
Access Rights
info:eu-repo/semantics/closedAccess
Abstract
The membership problem for EDT0L-languages is known to be polynomial, while for ET0L-languages is known to be NP-complete. We present a new proof for the latter fact based on a reduction to the Hitting String problem. We also give an example that introducing a single nondeterministic rule in an EDT0L-system is enough to cross the barrier between P and NP-complete, if such a frontier exists.
Description
Keywords
ET0L-systems, membership problem, Hitting string problem, longest common subsequence, NP-completeness, unary coding
Journal or Series
Comptes Rendus De L Academie Bulgare Des Sciences
WoS Q Value
Scopus Q Value
Volume
74
Issue
7
