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

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

Спецкурс проходил по пятницам в 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).

        13.10.2017
Частично упорядоченные полугруппы.
Полугруппы с делением.
Полугруппа идеалов упорядоченной полугруппы.
Языковые модели (L-модели).
Реляционные модели (R-модели).
Домашнее задание:
(1) Образуют ли натуральные числа со сложением и \geq полугруппу с делением?
(2) Доказать монотонность умножения на идеалах упорядоченной полугруппы.

        27.10.2017
Несеквенциальное исчисление LH.
Интерпретация в полугруппе с делением.
Секвенциальное исчисление L.
Домашнее задание:
(1) В L вывести (p_1 / p_2) \cdot p_2 \cdot (p_1 \ p_3) -> p_3.
(2) В LH вывести производные правила про монотонность умножения и деления.
(3) В LH вывести правило замены.

        10.11.2017
Эквивалентность L и LH.

        17.11.2017
Теорема об универсальной L-модели для L(\,/).
Открытый вопрос: есть ли сильная полнота L в случае гипотез, истинных хотя бы в одной L-модели?
Домашнее задание:
(1) Доказать обратимость правила введения левого деления в сукцедент.
(2) Существует ли для L(\,/) универсальная L-модель над 3-буквенным алфавитом?
(3) Существует ли для L(\,/) универсальная L-модель над 2-буквенным алфавитом?
(4) Существует ли для L(\,/) универсальная L-модель над 1-буквенным алфавитом?
(5) Существует ли универсальная L-модель для L(\,/,\cap)?

        24.11.2017
Корректность интерпретации L в свободной группе (без доказательства).
Интерполяционная лемма для L.
Домашнее задание:
(1) В шаге индукции доказательства интерполяционной леммы доказать случай правила введения умножения в сукцедент.
(2) В шаге индукции доказательства интерполяционной леммы доказать случай правила введения умножения в антецедент.

        08.12.2017
Грамматики Ламбека порождают все контекстно-свободные языки без пустого слова.

        15.12.2017
Грамматики Ламбека порождают только контекстно-свободные языки без пустого слова.

        16.02.2018
Мультипликативная циклическая линейная логика.

        02.03.2018
Мультипликативная циклическая линейная логика.

        16.03.2018
Сети доказательства.

        30.03.2018
Сети доказательства.

        13.04.2018
NP-полнота исчисления L(\, /).

        27.04.2018
NP-полнота исчисления L(\, /).

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

  1. Пентус М. Р. Исчисление Ламбека и формальные грамматики // Фундаментальная и прикладная математика. 1995. Т. 1, № 3. С. 729—751.
  2. 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.
  3. 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).
  4. 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.
  5. Lambek J. The mathematics of sentence structure // American Mathematical Monthly. 1958. Vol. 65, N 3. P. 154—170.
    Русский перевод: Ламбек И. Математическое исследование структуры предложения // Математическая лингвистика: Сборник переводов / Под ред. Ю. А. Шрейдера и др. М.: Мир, 1964. С. 47—68.
  6. 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.
  7. 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.
  8. 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/spec2017cglw.htm
Изменения внесены 03.02.2019.
Мати Рейнович Пентус