ON COMPLEXITY OF TOTAL DERIVABILITY PROBLEM IN NONCONTRACTING AND CONTEXT-FREE GRAMMARS
Доклады Российской академии наук. Математика, информатика, процессы управления / Doklady Mathematics · 2025 · 524 (1) · 11
DOI: 10.7868/s3034504925040024 ↗Kurz gefasst
Fachartikel in der Zeitschrift Доклады Российской академии наук. Математика, информатика, процессы управления / Doklady Mathematics, 2025. Verfasst von S.M. Dudakov und 1 weiteren Autor:innen.
Abstract (Originalsprache)
In this paper we study the problem of total derivability in context-free, noncontracting, and context-sensitive grammars. Given a grammar and a terminal word, one has to determine whether there exists a derivation of this word which uses each production no less than a given number of times. It is proved that the problem of total derivability of the emptyword in a context-free grammar is NP-complete. For noncontracting and context-sensitive grammars it is polynomially decidable for words of length 1, and it is NP-complete for every fixed word of length at least 2. Analagous results are obtained for another variant of the problem of total derivability when restrictions are placed on the amount of uses of nonterminals in the derivation.
Zitieren
APA
Dudakov, S., & Karlov, B. (2025). ON COMPLEXITY OF TOTAL DERIVABILITY PROBLEM IN NONCONTRACTING AND CONTEXT-FREE GRAMMARS. Доклады Российской академии наук. Математика, информатика, процессы управления / Doklady Mathematics, 524(1), 11. https://doi.org/10.7868/s3034504925040024
Vancouver
Dudakov S, Karlov B. ON COMPLEXITY OF TOTAL DERIVABILITY PROBLEM IN NONCONTRACTING AND CONTEXT-FREE GRAMMARS. Доклады Российской академии наук. Математика, информатика, процессы управления / Doklady Mathematics. 2025;524(1):11. doi:10.7868/s3034504925040024
BibTeX
@article{Dudakov2025,
author = {Dudakov, S.M. and Karlov, B.N.},
title = {ON COMPLEXITY OF TOTAL DERIVABILITY PROBLEM IN NONCONTRACTING AND CONTEXT-FREE GRAMMARS},
journal = {Доклады Российской академии наук. Математика, информатика, процессы управления / Doklady Mathematics},
year = {2025},
volume = {524},
number = {1},
pages = {11},
doi = {10.7868/s3034504925040024}
}
EUVIMED