О СЛОЖНОСТИ ПРОБЛЕМЫ ТОТАЛЬНОЙ ВЫВОДИМОСТИ В НЕУКОРАЧИВАЮЩИХ И КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИКАХ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и контекстно-зависимых грамматик она разрешима за полиномиальное время для слов длины 1 и является NP-полной для любого фиксированного слова длины не менее 2. Аналогичные результаты получены и для варианта проблемы тотальной выводимости с нижним ограничением на число использований нетерминалов в выводе.

Об авторах

С. М Дудаков

Тверской государственный университет; Национальный исследовательский университет «Высшая школа экономики»

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

Б. Н Карлов

Тверской государственный университет

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
Скачать

© Российская академия наук, 2025