NOTES ON THE NP-COMPLETENESS OF THE MEMBERSHIP PROBLEM OF ET0L LANGUAGES - Fogarasi, Kinga; Nagy, Benedek (Publ House Bulgarian Acad Sci, 2021)
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.
Keywords: ET0L-systems; membership problem; Hitting string problem; longest common subsequence; NP-completeness; unary coding