Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Исчисление Ламбека и формальные грамматики Пентус Мати Рейнович

Данная диссертационная работа должна поступить в библиотеки в ближайшее время
Уведомить о поступлении

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Пентус Мати Рейнович. Исчисление Ламбека и формальные грамматики : автореферат дис. ... кандидата физико-математических наук : 01.01.06 / МГУ им. М. В. Ломоносова.- Москва, 1996.- 12 с.: ил. РГБ ОД, 9 96-2/2433-3

Введение к работе

Актуальность темы. Вопрос о месте категориальных грамматик в иерархии Хомского возник в конце 50-х — начале 60-х годов. В 1960 году Бар-Хиллел, Гайфман и Шамир [1] доказали, что формальный язык может быть задан некоторой базовой категориальной грамматикой тогда и только тогда, когда он является контекстно-свободным. Они высказали гипотезу о том, что то же самое имеет место для грамматик Ламбека, т. е. для категориальных грамматик, основанных на введенном в 1958 году И. Ламбе-ком [2] синтаксическом исчислении с тремя связками (умножение или конкатенация языков, левое деление и правое деление).

. Доказательство одной половины вышеуказанной гипотезы (а именно, того, что любой контекстно-свободный язык задается некоторой грамматикой Ламбека) фактически совпадает с соответствующим доказательством для базовых категориальных грамматик. Вопрос об обратном включении оставался открытым в течение многих лет. В. Бушковским [3,4,5] были получепы частичные результаты, относящиеся к фрагменту с одним делением и к фрагменту без умножения с ограничением на вложенность разносторонних делений.

1. Bar-Hillel Y., Gaifman С, and Shamir Е. On categorial and
phrase-structure grammars // Bull. Res. Council Israel Sect. F.

1960. — 9F. — P. 1-16.

2. Lambek J. The mathematics of sentence structure // American
Mathematical Monthly.
— 1958. — Vol. 65, № 3. — P. 154-170.

  1. Buszkowski W. The equivalence of unidirectional Lambek categorial grammars and context-free grammars // Zeitschrift fur mathematische Logik und Grundlagen aer Mathematik. — 1985. — Vol. 31. — P. 369-384.

  2. Buszkowski W. Generative power of categorial grammars // Categorial Grammars and Natural Language Structures I Editors 11. T. Oehrle, E. Bach, and D. Wheeler. — Dordrecht: Reidel, 1988. — P. 69-94.

  3. Buszkowski W. On generative capacity of the Lambek calculus II Logics in AI / Editor J. van Eijck. — Berlin: Springer, 1991. — P. 139-152.

И. ван Бентхем в книге [6] приводит вышеупомянутую гипотезу в качестве открытой проблемы современной математической лингвистики.

С логической точки зрения, исчисление Ламбека представляет больший интерес, чем исчисление, на котором основаны базовые категориальные грамматики. В частности, в исчислении Ламбека допустимо правило замены эквивалентных подформул. Известно, что исчисление Ламбека вкладывается в некоторые фрагменты некоммутативной и циклической линейных логик.

Цель работы — доказать гипотезу о контекстно-свободно-сти всех языков, порождаемых грамматиками Ламбека.

Методы исследования. В диссертации использована разработанная автором техника изучения некоммутативной линейной логики посредством интерпретации в свободной группе, модификация метода Маехары и Шютте доказательства интерполяционного свойства Крейга, а также комбинаторные методы.

Научная новизна и практическая ценность. Все результаты диссертации являются новыми.

Доказано, что категориальные грамматики, основанные на любом из перечисленных ниже исчислений:

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

исчислении Ламбека с пустыми антецедентами,

исчислении Ламбека с единицей,

мультипликативном фрагменте циклической линейной логики,

порождают в точности все контекстно-свободные языки.

Доказано, что все элементарные фрагменты исчисления Ламбека обладают интерполяционным свойством Крейга.

Доказана разрешимость отношения совместимости синтаксических типов и его полнота относительно интерпретации в свободной группе.

6. Benthem J. van. Language in Action. Categories, Lambdas and Dynamic Logic: Studies in Logic and the Foundations of Mathematics. Vol. 130. — Amsterdam: North-Holland, 1991. — X, 350 p.

Теоретическая и практическая ценность. Работа носит теоретический характер. Ее методы и результаты могут быть полезны специалистам Московского государственного университета, Новосибирского государственного университета, Санкт-Петербургского государственного университета, Математического института им. В. А. Стеклова РАН, Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН.

Апробация работы. Основные результаты, полученные в диссертации, докладывались на общемосковском научно-исследовательском семинаре по математической логике (руководители семинара — проф. С. И. Адян, проф. В. А. Успенский), на семинаре "Логические методы в информатике" (руководитель семинара — проф. С. II. Артёмов) и на международных конференциях в России, Голландии, Швейцарии, Франции, Канаде и Израиле.

Публикации. Результаты диссертации опубликованы в шести работах, перечисленных в конце автореферата.

Структура и объем работы. Диссертация состоит из введения и 9 глав. Текст диссертации изложен на 69 страницах. Список литературы содержит 20 наименований.