Спецкурс "Сложность исчисления Ламбека"

М. Р. Пентус
Осень 2018

Это полугодовой спецкурс по выбору кафедры на механико-математическом факультете МГУ. Лекции проходили по пятницам в 16:45-18:20 в аудитории 14-02. Первая лекция состоялась 21 сентября 2018 г. Последняя лекция состоялась 7 декабря 2018 г.

Краткий конспект старого спецкурса "Исчисление Ламбека" 2005/2006 года: pdf.

Программа спецкурса

Синтаксическое исчисление Ламбека, некоммутативная линейная логика, алгоритмические проблемы, проблема выводимости, понятие NP-сложности, понятие NP-полноты, сложность проблемы выводимости в мультипликативном фрагменте некоммутативной линейной логики и во фрагментах синтаксического исчисления Ламбека.

Прошедшие лекции

Лекция 1 (21.09.2018)

Пример грамматики Ламбека.
Секвенциальное исчисление L.
Теорема об устранимости сечения (без доказательства).
Несеквенциальное исчисление LH.
Теорема об эквивалентности L и LH.
Домашнее задание:
(1) Узнать и понять определения классов сложности P и NP.
(2) Найти два эквивалентных типа в исчислении L.

Материал 1-й лекции, достаточный для понимания следующих лекций, изложен в разделе 1.2 конспекта 2018 года.

Лекция 2 (05.10.2018)

Лекция 3 (12.10.2018)

Лекция 4 (19.10.2018)

Лекция 5 (26.10.2018)

Лекция 6 (02.11.2018)

Лекция 7 (09.11.2018)

Лекция 8 (16.11.2018)

Лекция 9 (23.11.2018)

Лекция 10 (07.12.2018)

Основная литература

  1. Крупский В. Н. Введение в сложность вычислений. М.: Факториал Пресс, 2006. 128 с.
  2. W. Buszkowski. Lambek calculus with nonlogical axioms. In: Language and Grammar, Studies in Mathematical Linguistics and Natural Language, CSLI Publications, 2002. pp. 77--93. http://buszko.home.amu.edu.pl/NONLOG1.pdf
  3. Lambek J. The mathematics of sentence structure // American Mathematical Monthly. 1958. Vol. 65, N 3. P. 154-170.
    Русский перевод: Ламбек И. Математическое исследование структуры предложения // Математическая лингвистика: Сборник переводов / Под ред. Ю. А. Шрейдера и др. М.: Мир, 1964. С. 47-68.
  4. Pentus M. Lambek calculus is NP-complete // Theoretical Computer Science. 2006. Vol. 357, no. 1-3. P. 186-201.
    Препринт 2003 года доступен со страницы http://www.cs.gc.cuny.edu/tr/techreport.php?id=79.
  5. Pentus M. Algorithmic complexity of the Lambek syntactic calculus. Slides of a talk given at the Moscow Russian-French conference "Foundations of Internet", November 15-19, 2004.
  6. Pentus M. A polynomial-time algorithm for Lambek grammars of bounded order // Linguistic Analysis. 2010. Vol. 36, No 1-4. P. 441-471.

Дополнительная литература

  1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
  2. Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо, 1999. 192 с.
  3. Хопкрофт Дж. Э., Мотвани Р., Ульман Дж. Д. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002. 528 с.
  4. Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 1995. 264 с.
  5. Carpenter B. Type-Logical Semantics. The MIT Press, 1997. 575 pp.
  6. Pentus M. Free monoid completeness of the Lambek calculus allowing empty premises // Logic Colloquium '96: proceedings of the colloquium held in San Sebastian, Spain, July 9--15, 1996 / Editors J. M. Larrazabal, D. Lascar, and G. Mints. Berlin: Springer, 1998. P. 171-209. (Lecture Notes in Logic; vol. 12).
  7. Savateev Y. Product-free Lambek calculus is NP-complete // Logical Foundations of Computer Science, International Symposium, LFCS 2009, Deerfield Beach, FL, USA, January 3-6, 2009. Proceedings / Editors S. N. Artemov and A. Nerode. Berlin: Springer, 2009. P. 380-394. (Lecture Notes in Computer Science; vol. 5407).

Адрес: https://fervo.ru/mr/spec2018w.htm
Изменения внесены 07.06.2019.
Мати Рейнович Пентус