ON COMPLEXITY OF TOTAL DERIVABILITY PROBLEM IN NONCONTRACTING AND CONTEXT-FREE GRAMMARS

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅或者付费存取

详细

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.

作者简介

S. Dudakov

Tver State University; National Research University «Higher School of Economics»

Email: sergeydudakov@yandex.ru
Тверь, Россия; Москва, Россия

B. Karlov

Tver State University

Email: bnkarlov@gmail.com
Тверь, Россия

参考

  1. Shallit J. A second course in formal languages and automata theory. Cambridge: Cambridge University Press, 2008.
  2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  3. Valiant L.G. General context-free recognition in less than cubic time // J. Comput. Syst. Sci. 1975. V. 10. P. 308—315. https://doi.org/10.1016/S0022-0000(75)80046-8
  4. Дудаков С.М., Карлов Б.Н., Кузнецов С.Л., Фофанова Е.М. Сложность исчислений Ламбека с модальностями и тотальной выводимости в грамматиках // Алгебра и логика. 2021. Т. 60. № 5. С. 471—496. https://doi.org/10.33048/alglog.2021.60.502
  5. Event-Based Control and Signal Processing / ed. Miskowicz M. Boca Raton, FL: CRC Press, 2018. https://doi.org/10.1201/b19013
  6. Harrison M.A. Introduction to formal language theory. Reading, MA: Addison-Wesley, 1978.
  7. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
  8. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. 2–e изд. М.: Вильямс, 2011.

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © Russian Academy of Sciences, 2025