О СЛОЖНОСТИ ПРОБЛЕМЫ ТОТАЛЬНОЙ ВЫВОДИМОСТИ В НЕУКОРАЧИВАЮЩИХ И КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИКАХ
- Авторы: Дудаков С.М1,2, Карлов Б.Н1
-
Учреждения:
- Тверской государственный университет
- Национальный исследовательский университет «Высшая школа экономики»
- Выпуск: Том 524, № 1 (2025)
- Страницы: 11-18
- Раздел: МАТЕМАТИКА
- URL: https://journals.rcsi.science/2686-9543/article/view/311977
- DOI: https://doi.org/10.7868/S3034504925040024
- ID: 311977
Цитировать
Аннотация
Об авторах
С. М Дудаков
Тверской государственный университет; Национальный исследовательский университет «Высшая школа экономики»
Email: sergeydudakov@yandex.ru
Тверь, Россия; Москва, Россия
Б. Н Карлов
Тверской государственный университет
Email: bnkarlov@gmail.com
Тверь, Россия
Список литературы
- Shallit J. A second course in formal languages and automata theory. Cambridge: Cambridge University Press, 2008.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
- 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
- Дудаков С.М., Карлов Б.Н., Кузнецов С.Л., Фофанова Е.М. Сложность исчислений Ламбека с модальностями и тотальной выводимости в грамматиках // Алгебра и логика. 2021. Т. 60. № 5. С. 471—496. https://doi.org/10.33048/alglog.2021.60.502
- Event-Based Control and Signal Processing / ed. Miskowicz M. Boca Raton, FL: CRC Press, 2018. https://doi.org/10.1201/b19013
- Harrison M.A. Introduction to formal language theory. Reading, MA: Addison-Wesley, 1978.
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
- Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. 2–e изд. М.: Вильямс, 2011.
Дополнительные файлы
