Введение к работе
Актуальность темы. Вопрос о месте категориальных грамматик в иерархии Хомского возник в конце 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.
-
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.
-
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.
-
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 наименований.