Исчисление Ламбека
Исчисление Ламбека (англ. Lambek calculus, обозначается
Формальное определение
Исчисление Ламбека можно определить несколькими эквивалентными способами. Ниже представлено определение секвенциального исчисления Ламбека в генценовском виде.
Исчисление Ламбека работает с типами (с точки зрения лингвистики, типы соответствуют определённым категориям слов). Фиксируется множество
Примитивные типы принято обозначать строчными латинскими буквами, типы — заглавными латинскими буквами, последовательности типов — заглавными греческими буквами (
Секвенцией называется строка вида
Аксиомы и правила исчисления Ламбека объясняют, какие секвенции являются выводимыми. Единственная аксиома (точнее, схема аксиом) имеет вид:
В исчислении Ламбека имеется 6 правил вывода, по два на каждую операцию[2]:
Секвенция
Примеры выводимых секвенций
- Секвенция
(называемая поднятием типа ) выводима в исчислении Ламбека:
- Секвенция
выводима в исчислении Ламбека:
. , .
Категориальные грамматики Ламбека
Понятие категориальных грамматик Ламбека относится к теории формальных грамматик; они представляют собой частный случай категориальных грамматик. Рассматривается конечное непустое множество
Категориальная грамматика Ламбека — структура
— алфавит; — выделенный тип в грамматике; — конечное бинарное отношение, ставящее в соответствие каждому символу алфавита конечное число типов исчисления Ламбека.
Язык, распознаваемый грамматикой
Пример. Пусть
Примеры из лингвистики
Если в качестве
- Английскому предложению John loves Mary "Джон любит Мэри" можно поставить в соответствие секвенцию
[3]. Здесь именам собственным John, Mary соответствует примитивный тип "noun phrase", обозначающий именные группы, а переходному глаголу loves соответствует сложный тип . Примитивный тип "sentence" соответствует повествовательным предложениям. Данная секвенция выводима в исчислении Ламбека:
- Более сложному английскому предложению John loves but Bill hates Mary "Джон любит, а Билл ненавидит Мэри" ставится в соответствие выводимая секвенция
[4].
Чтобы связать примеры выше с данным в начале раздела формальным определением категориальных грамматик, возьмём в качестве выделенного типа примитивный тип
Свойства
- В исчислении Ламбека допустимо правило сечения[1]. Иначе говоря, из выводимости секвенций вида
и следует выводимость секвенции . - Класс языков, порождаемых грамматиками Ламбека, совпадает с классом контекстно-свободных языков без пустого слова[5].
- Задача проверки выводимости секвенции в исчислении Ламбека NP-полна[6].
- Исчисление Ламбека корректно и полно относительно моделей полугрупп с делением, причём существует универсальная модель. Также оно полно относительно
-моделей (языковые модели, англ. language models), и относительно -моделей (реляционные модели, англ. relational models) [7]. - В исчисление Ламбека можно добавить аппарат лямбда-исчисления, так что выводы в исчислении Ламбека будут сопровождаться преобразованиями лямбда-типов[8]. С лингвистической точки зрения это позволяет моделировать семантику предложений.
Модификации
Существует ряд вариантов исчисления Ламбека, основанных на добавлении операций, отличных от делений и умножения, и добавлении новых аксиом и правил вывода. Ниже рассмотрены некоторые из вариантов.
- Исчисление Ламбека с единицей (
). В нём допускаются секвенции вида (у которых 0 типов в антецеденте). В набор допустимых символов, из которых строятся типы, добавляется единица ( ). Для неё вводятся одна аксиома и одно правило:
- Мультипликативно-аддитивное исчисление Ламбека (multiplicative-additive Lambek calculus) — расширение
, в рамках которого типы строятся не только с помощью делений и умножения, но и с помощью конъюнкции и дизъюнкции . Для них вводятся следующие 6 правил:
См. также
Примечания
- ↑ Перейти обратно: 1,0 1,1 Lambek, 1958.
- ↑ Пентус, 1995, с. 732.
- ↑ Moortgat, 1988, p. 14.
- ↑ Moortgat, 1988, p. 36.
- ↑ Пентус, 1995.
- ↑ Pentus, 2006.
- ↑ Пентус, 1999.
- ↑ Moortgat, 1988.
Литература
- Lambek, J. The Mathematics of Sentence Structure (англ.) // The American Mathematical Monthly. — 1958. — Vol. 65, no. 3. — P. 154-170. — ISSN 0002-9890. — doi:10.2307/2310058.
- Moortgat, M. Categorial Investigations: Logical and Linguistic Aspects of the Lambek Calculus : [англ.]. — Foris Publications. — 1988. — ISBN 9789067653879.
- Пентус М. Р. Исчисление Ламбека и формальные грамматики // Фундаментальная и прикладная математика. — 1995. — Т. 1, № 3. — С. 729-751.
- Пентус М. Р. Полнота синтаксического исчисления Ламбека // Фундаментальная и прикладная математика. — 1999. — Т. 5, № 1. — С. 193-219.
- Pentus, M. Lambek calculus is NP-complete (англ.) // Theoretical Computer Science. — 2006. — Vol. 357, no. 1. — P. 186-201. — ISSN 0304-3975. — doi:10.1016/j.tcs.2006.03.018.