Алгоритмические вопросы для формальных грамматик
Название спецкурса на английском языке
Algorithmic questions for formal grammars
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Математический институт имени В. А. Стеклова РАН]
Семестр
Полгода (осень)
Семестр
Осень
Тип курса
Спецкурс по выбору студента
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Контекстно-свободные грамматики. Нормальная форма Хомского. Алгоритм Кока-Янгера-Касами.
Грамматики присоединения деревьев (TAG), полиномиальный алгоритм разбора.
Нормальная форма Грейбах.
Исчисление Ламбека, категориальные грамматики Ламбека. Совпадение классов языков, задаваемых грамматиками Ламбека и контекстно-свободными грамматиками (теорема Пентуса).
NP-полнота задачи выводимости в исчислении Ламбека.
Полиномиальный алгоритм для грамматик Ламбека с ограниченной глубиной типов.
Полиномиальное преобразование грамматик Ламбека с одним делением в контекстно-свободные грамматики.
Порождающие грамматики общего вида (грамматики типа 0). Алгоритмическая неразрешимость задачи синтаксического разбора для грамматик Ламбека с дополнительными аксиомами (в т.ч. во фрагменте с одним делением).
Неукорачивающие грамматики, порождение ими PSPACE-полных языков. Полиномиальный алгоритм разбора для фиксированной удлиняющей грамматики.
Алгоритмическая неразрешимость задачи тотальности (порождения всех слов в данном алфавите) для контекстно-свободных грамматик. Языки, задаваемые грамматиками Ламбека с итерацией Клини.
Грамматики присоединения деревьев (TAG), полиномиальный алгоритм разбора.
Нормальная форма Грейбах.
Исчисление Ламбека, категориальные грамматики Ламбека. Совпадение классов языков, задаваемых грамматиками Ламбека и контекстно-свободными грамматиками (теорема Пентуса).
NP-полнота задачи выводимости в исчислении Ламбека.
Полиномиальный алгоритм для грамматик Ламбека с ограниченной глубиной типов.
Полиномиальное преобразование грамматик Ламбека с одним делением в контекстно-свободные грамматики.
Порождающие грамматики общего вида (грамматики типа 0). Алгоритмическая неразрешимость задачи синтаксического разбора для грамматик Ламбека с дополнительными аксиомами (в т.ч. во фрагменте с одним делением).
Неукорачивающие грамматики, порождение ими PSPACE-полных языков. Полиномиальный алгоритм разбора для фиксированной удлиняющей грамматики.
Алгоритмическая неразрешимость задачи тотальности (порождения всех слов в данном алфавите) для контекстно-свободных грамматик. Языки, задаваемые грамматиками Ламбека с итерацией Клини.
Список источников
А. Л. Семенов, М. А. Бабенко, А. Я. Белов, Н. К. Верещагин, М. Е. Вишникин, Е. Е. Золин, В. Н. Крупский, С. Л. Кузнецов, В. А. Любецкий, А. А. Оноприенко, М. Р. Пентус, С. Ф. Сопрунов, А. А. Сорокин, В. Б. Шехтман, Т. Л. Яворская, “Кафедра математической логики и теории алгоритмов”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2025, № 1, 23–32
С. Л. Кузнецов, “Алгоритмическая сложность теорий коммутативных алгебр Клини”, Изв. РАН. Сер. матем., 88:2 (2024), 44–79
С. Л. Кузнецов, “Алгоритмическая сложность теорий коммутативных алгебр Клини”, Изв. РАН. Сер. матем., 88:2 (2024), 44–79
Дополнительная информация
Ссылка на страницу спецкурса: https://www.mathnet.ru/conf2632
День недели
четверг
Время
16:45-18:20
Аудитория
Внешняя площадка
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.