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

• Автор: Пентус, Мати Рейнович
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2000
• Место защиты: Москва
• Количество страниц: 165 с.

Оглавление
Введение
1 Определения
1.1 Исчисление Ламбека
1.2 Грамматики Ламбека и контекстно-свободные
грамматики
1.3 Модели на частичных полугруппах
2 Известные свойства исчисления Ламбека
2.1 Устранимость сечения
2.2 Простые теоретико-доказательственные свойства
2.3 Интерпретация в свободной группе
2.4 Интерполяционное свойство
2.5 Корректность исчисления Ламбека
2.6 Полнота фрагмента исчисления Ламбека
3 Грамматики Ламбека
3.1 Одно свойство свободных групп
•3.2 Тонкие секвенции
3.3 Исчисление Ьси<;т
3.4 Контекстно-свободность языков, порождаемых
грамматиками Ламбека
4 Квазимодели
4.1 Определение Тр(ш)-квазимоделей
4.2 Консервативные расширения

4.3 Свидетели
5 Веса
5.1 Исчисление I
5.2 Эквивалентность исчислений Т/ и Т
5.3 Определение весов
5.4 Обратимость правил (—> ) и ( —$)
6 Сращивание выводов
7 Правило сечения
8 Построение квазимоделей
9 R-полнота
9.1 Основная лемма
9.2 Засвидетельствованность класса конечных линейных R-фреймов
10 L-полнота
10.1 Засвидетельствованность класса
10.2 Нспустота класса
10.3 Основная теорема
Заключение
Указатель обозначений и терминов
Список литературы

Введение
Актуальность темы. Категориальная грамматика — раздел математической лингвистики, описывающий формальные законы синтаксических категорий в естественных и искусственных языках. Одно из центральных мест в нём занимает исчисление Ламбека, которое было введено в статье [36] для изучения свойств формальных языков. Формальным языком называется произвольное множество непустых слов (конечных последовательностей символов) над некоторым конечным алфавитом. В лингвистических приложениях при описании синтаксиса естественного языка алфавитом (в математическом смысле) является множество всех словоформ рассматриваемого фрагмента естественного языка. При этом множество всех грамматически правильных предложений образует формальный язык. Другие важные примеры формальных языков над тем же алфавитом — множество всех именных групп, множество всех групп сказуемого и т. д.
Исчисление Ламбека описывает свойства трёх бинарных операций над формальными языками: операции умножения, операции правого деления и операции левого деления (эти операции обозначаются соответственно , / и ). Произведение языков состоит из всевозможных попарных конкатенаций их элементов. Результат правого деления языка Л на В (обозначается А/В и читается «А над В») определяется как множество всех таких непустых слов 7, что {у}*В С А. Результат левого деления языка А на В (обозначается ВА и читается «В под А») определяется как множество всех таких

данной диссертации, теорема о полноте относительно класса всех Ь-моделей, усиливает теорему Бушковского, так как Ь-модели — частный случай моделей на полугруппах (см. [7,51]).
Полнота относительно класса всех Н-молелей доказана С. Ми-кулашом (ем. [41]). В данной диссертации получено усиление результата Микулаша, устанавливающее полноту относительно меньшего класса моделей, а именно, относительно класса 11-моделей, основанных на обычном отношении порядка на множестве целых чисел (см. [7,46]).