Notes on the NP-completeness of the Membership Problem of ET0L LanguagesЕ
Kinga Fogarasi, Benedek Nagi · 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.