Синтаксическое исчисление Ламбека

Синтаксическое исчисление Ламбека было введено в 1958 году. Оно используется в математической лингвистике для математически строгого описания синтаксиса формальных и естественных языков. При этом грамматические категории моделируются формулами, построенными из переменных с помощью трёх бинарных операций – левого деления, правого деления и умножения. Доклад затрагивает несколько тем, связанных с этим исчислением.
Формулируется теорема о том, что грамматики, основанные на исчислении Ламбека, задают в точности класс всех контекстно-свободных языков без пустого слова.
Рассматриваются теоремы о корректности и полноте исчисления Ламбека относительно языковых и реляционных моделей (в языковой модели каждой формуле соответствует какое-то множество слов, а в реляционной модели – какое-то бинарное отношение).
Изучается алгоритмическая сложность проблемы распознавания выводимости в исчислении Ламбека и его фрагментах, получающихся при отбрасывании части бинарных операций, используемых в определении формулы. При этом оказывается полезным вложение исчисления Ламбека в некоммутативную линейную логику.