Спецкурс "Категориальные грамматики Ламбека"

М. Р. Пентус
2017/2018

Внимание! 20 октября лекции не будет.

В осеннем семестре спецкурс проходит по пятницам в 15:00-16:35 в аудитории 14-04. Первая лекция состоялась 29 сентября 2017 г.

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

Краткое содержание прошедших лекций

        29.09.2017
Пример грамматики Ламбека с алфавитом {John, Mary, smiles, hates, charmingly}.
Умножение и деление формальных языков (подмножеств \Sigma^*).
Лемма. A(A\B) \subseteq B.
Домашнее задание:
(1) Доказать монотонность умножения и деления языков.
(2) Доказать равносильность D \subseteq F/E, DE \subseteq F и E \subseteq D\F.
(3) Всегда ли ((B/A)A)/A = B/A?
(4) Всегда ли ((BA)/A)A = BA?
(5) Всегда ли (BA)/A = B?
(6) Всегда ли (A\B)/C = A\(B/C)?
(7) Для случая подмножеств \Sigma^+ снова задачи (1)-(6).

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

  1. Abrusci V. M. Phase semantics and sequent calculus for pure noncommutative classical linear propositional logic // Journal of Symbolic Logic. 1991. Vol. 56, N 4. P. 1403—1451.
  2. Buszkowski W. On the Equivalence of Lambek Categorial Grammars and Basic Categorial Grammars. Amsterdam: Institute for Logic, Language and Computation, University of Amsterdam, 1993. 21 p. (ILLC Prepublication Series; LP—93—07).
  3. Galatos N., Ono. H. Cut elimination and strong separation for substructural logics: an algebraic approach // Annals of Pure and Applied Logic. 2010. Vol. 161, N 9. P. 1097—1133.
  4. Lambek J. The mathematics of sentence structure // American Mathematical Monthly. 1958. Vol. 65, N 3. P. 154—170.
    Русский перевод: Ламбек И. Математическое исследование структуры предложения // Математическая лингвистика: Сборник переводов / Под ред. Ю. А. Шрейдера и др. М.: Мир, 1964. С. 47—68.
  5. Lecomte A. Towards efficient parsing with proof-nets // EACL 1993, 6th Conference of the European Chapter of the Association for Computational Linguistics, April 21—23, 1993. Utrecht: OTS — Research Institute for Language and Speech, Utrecht University, 1993. P. 269—276.
  6. Moortgat M. Categorial type logics // Handbook of Logic and Language / Editors J. van Benthem and A. ter Meulen. Eslevier/MIT Press, 1997. P. 93—177. 1997.
  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).

Адрес: http://lpcs.math.msu.su/~pentus/spec2017cglw.htm
Изменения внесены 12.10.2017.
Мати Рейнович Пентус