NOTES ON THE NP-COMPLETENESS OF THE MEMBERSHIP PROBLEM OF ET0L LANGUAGES

Simple item page
dc.contributor.authorFogarasi, Kinga
dc.contributor.authorNagy, Benedek
dc.date.accessioned2026-02-06T18:22:04Z
dc.date.issued2021
dc.departmentDoğu Akdeniz Üniversitesi
dc.description.abstractThe 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.
dc.identifier.doi10.7546/CRABS.2021.07.02
dc.identifier.endpage971
dc.identifier.issn1310-1331
dc.identifier.issue7
dc.identifier.scopus2-s2.0-85111160373
dc.identifier.scopusqualityQ4
dc.identifier.startpage964
dc.identifier.urihttps://doi.org/10.7546/CRABS.2021.07.02
dc.identifier.urihttps://hdl.handle.net/11129/9585
dc.identifier.volume74
dc.identifier.wosWOS:000684962900002
dc.identifier.wosqualityQ4
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.language.isoen
dc.publisherPubl House Bulgarian Acad Sci
dc.relation.ispartofComptes Rendus De L Academie Bulgare Des Sciences
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/closedAccess
dc.snmzKA_WoS_20260204
dc.subjectET0L-systems
dc.subjectmembership problem
dc.subjectHitting string problem
dc.subjectlongest common subsequence
dc.subjectNP-completeness
dc.subjectunary coding
dc.titleNOTES ON THE NP-COMPLETENESS OF THE MEMBERSHIP PROBLEM OF ET0L LANGUAGES
dc.typeArticle

Files

Collections

WoS Indexed Publications Collection
Scopus İndeksli Yayınlar Koleksiyonu