Название спецкурса на русском языке
Сложность исчисления Ламбека
Перевод названия курса на английский язык
Complexity of the Lambek calculus
Целевая аудитория
2 курс
3 курс
4 курс
5 курс
6 курс
Аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Полгода (осень)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2021/22
Аудитория
[Неприменимо]
Аннотация
В курсе рассматриваются свойства исчисления Ламбека, одного из математических формализмов, используемых для описания синтаксиса естественных языков. Исчисление Ламбека вкладывается в некоммутативную линейную логику. Излагаются различные критерии выводимости, основанные на сетях доказательства. Проблема распознавания выполнимости в классической логике высказываний сводится к проблеме распознавания выводимости в некоммутативной линейной логике. Даются полиномиальные алгоритмы для проблемы распознавания выводимости в некоторых фрагментах исчисления Ламбека.