- Код статьи
- S3034504925040024-1
- DOI
- 10.7868/S3034504925040024
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 524 / Номер выпуска
- Страницы
- 11-18
- Аннотация
- В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и контекстно-зависимых грамматик она разрешима за полиномиальное время для слов длины 1 и является NP-полной для любого фиксированного слова длины не менее 2. Аналогичные результаты получены и для варианта проблемы тотальной выводимости с нижним ограничением на число использований нетерминалов в выводе.
- Ключевые слова
- контекстно-свободная грамматика неукорачивающая грамматика контекстно-зависимая грамматика тотальная выводимость вычислительная сложность NP-полная проблема
- Дата публикации
- 27.11.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 8
Библиография
- 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.
