О классах категориальных грамматик зависимостей тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

Карлов Борис Николаевич

О классах категориальных грамматик зависимостей

Специальность 01.01.06 — математическая логика, алгебра п теория

чисел

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук.

- 1 НОЯ 2012

Ярославль — 2012

005054077

005054077

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Тверской государственный университет».

Научный руководитель — доктор физико-математических наук,

доцент Дехтярь Михаил Иосифович

Официальные оппоненты: Соколов Валерий Анатольевич, доктор

физико-математических наук, профессор, заведующий кафедрой теоретической информатики Ярославского государственного университета им. П. Г. Демидова

Валиев Марс Котдусович, кандидат физико-математичсских наук, старший научный сотрудник Института прикладной математики им. М. В. Келдыша РАН

Ведущая организация — Московский государственный университет

им. М. В. Ломоносова

Защита диссертации состоится 23 ноября 2012 г. в 14.00 на заседании диссертационного совета Д 212.002.03 при Ярославском государственном университете им. П. Г. Демидова по адресу: Российская Федерация, 150008, Ярославль, ул. Союзная, 144, ауд. 426.

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им. П. Г. Демидова.

Автореферат разослан » октября 2012 г.

Учёный секретарь Яблокова

диссертационного совета Светлана Ивановна

Общая характеристика работы

Актуальность. Формальные способы описания синтаксической структуры предложения имеют первостепенную важность для большинства задач информатики, связанных с обработкой информации на естественном языке. После основополагающих работ Н. Хомского, определившего четыре базовых класса порождающих грамматик, был определен ещё целый ряд типов грамматик, позволяющих вычислять синтаксическую структуру предложения в ходе его вывода или доказательства его правильности. В частности, грамматики зависилюстей (специальный тип грамматик) присваивают структуры зависимостей (структуры подчинения) предложениям языка, который они определяют. Теории синтаксиса естественных языков, основанные на понятии зависимости, имеют давнюю традицию, восходящую к средним векам. Тсньер впервые систематически описал структуру предложения в терминах именованных бинарных отношений между словами (зависимостей). Когда два слова и>1 и и>2 связаны в предложении посредством зависимости <1 (обозначение Юх IV2), является главным словом, а 102 — зависимым словом. Содержательно, зависимость (I задаёт ограничения на грамматические и лексические свойства тих и и)2, на их порядок, контекст н т.п., которые вместе означают, что "гих управляет Например, в структуре зависимостей предложения "Летом здесь играют дети", приведённой на рис. 1, отношение играют дети показывает предикатную зависимость между сказуемым играют и подлежащим дети, в котором главным словом является глагол.

В этом предложении, как и в большинстве обычных предложений русского языка, структура зависимостей проективная, что, несколько упрощая, означает, что зависимости в структуре не пересекаются. Большинство грамматик, порождающих деревья зависимостей, имеют дело только с проективными структурами. С другой стороны, в языках достаточно часто встречаются предложения, имеющие непроективиые структуры зависимостей.

лето» здесь играют дета

Рис. 1: Пример проективной структуры зависимостей

летом эдесь будут играть дети

Рис. 2: Пример непроективной структуры зависимостей в русском

Например, использование будущего времени в предложении "Летом здесь будут играть дети" приводит к появлению двух разрывных за-

„ . обст-вр обст-лок -,

висимостеи играть —> летом и играть —» здесь, показанных на рис. 2. Разрывные зависимости встречаются и в других языках. На рис. 3 изображена структура зависимостей французского предложения "Il n'en avait plus besoin" ("Он больше в этом не нуждался"), а на рис. 4 — английского предложения "The person to whom you must refer is Smith" ("Человек, к которому Вы должны обратиться, — Смит").

n' en avait plus besoin

Рис. 3: Пример неироективной структуры зависимостей во французском языке

Рис. 4: Пример неироективной структуры зависимостей в английском языке

Современная лингвистическая теория синтаксических зависимостей была разработана Мельчуком. Первые точные определения грамматик зависимостей появились в работах Хейса и Гайфмана. Они имели много общего с классическими категориальными грамматиками Бар-Хиллсла (которые восходят к работам Лесьнсвского и Айдукевича). Они полностью лексикализованы, используют синтаксические типы вместо правил вывода н естественно подходят для функциональных семантических структур. В 1960 году Бар-Хиллел, Гайфман и Шамир доказали, что формальный язык, но содержащий пустого слова, может быть задан классической категориальной грамматикой тогда и только тогда, когда

он является контекстно-свободным. В 1958 году Ламбек ввёл синтаксическое исчисление, расширяющее исчисление категориальных грамматик. В 198G году Бушковский доказал, что грамматики Ламбска в неассоцнатнвном варианте эквивалентны контскстно-свободным грамматикам (кс-грамматнкам), а в 1993 году Пснтус доказал эквивалентность кс-грамматик и исходных (ассоциативных) грамматик Ламбска. Однако сейчас признано, что кс-грамматики недостаточно выразительны для описания естественных языков. Например, кс-грамматнкн, как и классические категориальные грамматики, неспособны описывать в предложениях, подобных вышеприведённым, разрывные составляющие. В результате значительный интерес представляет разработка и изучение формальных грамматик, более выразительных, чем кс-грамматики. Например, ТАГ-грамматикн Джоши, один из классов часто используемых для практических приложений, более выразительны, чем кс-грамматики, и позволяют выражать некоторые контекстные зависимости. Как показали Виай-Шенкср н Уэир, ТАГ-грамматики эквивалентны некоторым грамматикам совершенно иной природы (линейным индексным грамматикам Ахо, комбинаторным категориальным грамматикам Стидмана н некоторым другим), разделяя с ними свойства, благодаря которым их называют слабо контекстными. Имеется несколько неэквивалентных понятий слабой контекстности класса грамматик. Одно из них состоит в том, что 1) грамматики этого класса порождают все кс-языкн; 2) для них существует алгоритм синтаксического анализа за полиномиальное время; 3) эти грамматики позволяют выразить по меньшей мере некоторые пересекающиеся зависимости; 4) порождаемые ими языки обладают свойством линейного роста, т.е. сслп все предложения языка упорядочить по длине, то длины соседних предложений могут отличаться не более чем на заранее фиксированную константу. Первые грамматики зависимостей, выражающие неограниченные непроективные зависимости, были определены Диковским в 2001 году1. Эти грамматики являются порождающими, а непросктивные зависимости между словами определяются в них через двойственные поляризованные валентности: одноимённые однонаправленные валентности с протнво-нымн знаками. Принцип спаривания двойственных валентностей (FA) аналогичен правильному спариванию скобок. В 2004 году Диковский

'Dikovsky Л. Polarized Xon-projective Dependency Grammars // Proc. of the Fourth Int. Conf. on Logical Aspects of Computational Linguistics (LACH. Springer. L.MAI v. 2099, 2001. P. 139-157.

определил категориальные грамматики зависимостей (КГЗ)2 . Подобно классическим категориальным грамматикам, КГЗ являются анализирующими, т.е. синтаксическая структура предложения — дерево зависимостей — извлекается в них из доказательства правильности приписывания типов словам. Непроективные зависимости, как и в порождающих грамматиках зависимостей, определяются через двойственные поляризованные валентности. В последующих совместных работах с Дехтярём определение КГЗ эволюционировало. Используемое ниже окончательное определение КГЗ содержится в работе Дехтяря и Диковского3. КГЗ хорошо зарекомендовали себя на практике. Например, с университете Нанта разработана и успешно используется для синтаксического анализа и для создания корпусов деревьев зависимостей весьма полная КГЗ французского языка. В 2007 году Диковский определил мультимодаль-ные категориальные грамматики зависимостей (ммКГЗ), обобщающие КГЗ. Их отличие от КГЗ состоит в том, что каждому типу валентностей соответствует своё правило спаривания.

Настоящая диссертационная работа посвящена формальной теории КГЗ.

Цели диссертационной работы. Исследование свойств классов категориальных грамматик зависимостей и соответствующих классов порождаемых ими языков. Изучаемые вопросы включают существование нормальных форм КГЗ, существование класса автоматов, распознающих КГЗ-языки, замкнутость классов КГЗ-языков относительно различных операций над языками, полулннейность КГЗ-языков, а также проблему принадлежности для КГЗ.

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

Научная новизна и основные положения, выносимые на защиту. Все

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

2Dikovsky Л. Dependencies as Categories In "Remit Advances in Dependency Grammars". COLING'O 1 Workshop, 2001. P. 90-97.

3Deklity ar M,, Dikovsky Л. Generalized Catcgorial Dependency Grammars // Trakhtenbrot Festschrift, Springer Verlag, LNCS v. 4800, 2008. P. 230-255

1. Определена нормальная форма для классов КГЗ и ммКГЗ, аналогичная нормальной форме Грейбах для кс-грамматик, и установлена возможность эффективного приведения всякой КГЗ и ммКГЗ к этой нормальной форме.

2. Доказаны свойства замкнутости для классов КГЗ- и ммКГЗ-языков относительно операций объединения, пересечения с регулярными языками, неукорачнвающего гомоморфизма, обращения гомоморфизма, конкатснацнн и усечённой итерации. Установлено, что класс ммКГЗ-языков образует абстрактное семейство языков.

3. Доказано, что любой КГЗ-язык можно представить как проекцию пересечения кс-языка и скобочного языка Ьск, состоящего из слов, проекции которых на каждый тип скобок являются правильными скобочными словами.

4. Построено расширение автоматов с магазинной памятью (МП-автоматов) — МП-автоматы с независимыми счетчиками. Эти автоматы дополняют обычные МП-автоматы конечным числом целочисленных счётчиков. Их отличие от машин Минского состоит в отсутствии проверки счётчиков на ноль. Доказано, что МП-автоматы с независимыми счётчиками распознают в точности КГЗ-языки.

5. Показано, что класс ммКГЗ-языков содержит неполулинейные языки, в отличие от класса кс-языков.

6. Доказано, что проблема принадлежности слова ммКГЗ-языку является КР-полной для конкретной ммКГЗ, в отличие от КГЗ, где для каждой грамматики существует полиномиальный алгоритм.

Теоретическая и практическая значимость. Работа НОСИТ теоретический характер. Материалы диссертации могут использоваться при чтении специальных курсов студентам и аспирантам, специализирующимся в области компьютерной лингвистики. Кроме того, результаты об автоматах, распознающих КГЗ-языки, и о сложности проблемы принадлежности могут использоваться при построении и анализе практических КГЗ для естественных языков.

Апробация работы Результаты диссертации докладывались автором на семинаре по теоретической информатике в Тверском государственном университете, на семинаре по математической логике в Петербургском отделении математического института РАН и на двенадцатой национальной конференции по искусственному интеллекту с международным участием "КИИ-2010". Некоторые результаты были представлены в совместном докладе на 15-й международной конференции по формальным грамматикам ("Formal Grammars 2010", Copenhagen, Denmark). Статья [1] была представлена в 2009 году на "Открытый конкурс па лучшую научную работу студентов по естественным, техническим и гуманитарным наукам в высших учебных заведениях Российской Федерации" и получила в этом конкурсе медаль "За лучшую научную студенческую работу". Работа поддерживалась грантами РФФИ 08-01-00241 и 10-01-00532а.

Публикации. Список публикаций по теме диссертации приведён в конце автореферата и включает 5 работ, 2 из которых опубликованы в издании, входящем в список рекомендованных ВАК ведущих рецензируемых изданий. Работы [4, 5] представляют доклады на международных конференциях и опубликованы в серии Lecture Notes in Computer Science.

Результаты совместной работы [4], вошедшие в диссертацию, принадлежат автору.

Структура и объём диссертации. Диссертация состоит из введения, трёх глав основной части, заключения и списка литературы. Общий объем работы — 103 стр. Синеок литературы содержит 40 наименований.

Краткое содержание работы

Содержание введения в основном совпадает с содержанием автореферата.

В главе 1 приводятся основные определения и обозначения, связанные с категориальными грамматиками зависимостей, которые используются в остальной части работы.

Для формализации лингвистического понятия синтаксического типа используется понятие категории. Пусть С — непустое множество имен зависимостей (по аналогии с категориальными грамматиками, мы бу-

дсм их называть элементарными категориями) (например, сказуемое, определение, дополнение и т. п.). Элементарные категории могут быть итерированы: для С 6 С пусть С* означает соответствующую итеративную категорию. Итерирование категории означает, что она может повторяться произвольное количество раз (возможно, ни одного). Например, в естественных языках у существительного может быть много определении, у глагола может быть много обстоятельств и т.п. Множество всех итеративных категорий будем обозначать С*.

Для описания непроектнвных зависимостей вводятся понятия полярности и поляризованной валентности. Полярностью V называется элемент множества V = { \, </, /* }. Поляризованная валентность ¡5 — это выражение вида уС, где V € V, С £ С. Элементарная категория С называется именем валентности. Пары двойственных валентностей и {у/С, \С) назовём правильными (они являются соответствующими "скобками"). Валентности вида /*С и </ С называются левыми, а валентности вида \С и \С — правыми (они являются левыми и правыми скобками соответственно). Последовательность поляризованных валентностей называется потенциалом. Множество всех возможных потенциалов обозначается РоЬ(С).

Потенциал называется сбалансированным, если его проекция на каждую пару двойственных поляризованных валентностей является правильным скобочным словом. Например, потенциал / Л /* В \ А \ В / Л \ А сбалансирован, а потенциал / Л \ В \ А не сбалансирован.

Определение 1.1. Множество локальных категорий ЬСсЛ{С) — это минимальное множество такое, что:

1) С и {е} С ЬСаЬ{С), где е — символ пустой категории;

2) если а 6 ЬСаЦС), Л £ С и С*, то [А\а], [а/А] € ЬСаЬ{С).

Из локальных категорий и потенциалов строятся категории.

Определение 1.2. Категорией 7 называется выражение вида а0, где а е ¿Саг(С), в 6 РоЬ(С). Множество всех категорий обозначим Са<(С).

Полагаем, что конструкторы \ и / ассоциативны, например, [Б\[Л/С]] = [[В\Д]/С] = [В\А/С]. Поэтому любая категория 7 может быть представлена в виде [¿Д ... \Li\CfRi/... /Ят]°. Теперь приведём основное определение категориальной грамматики зависимостей. Определение 1.3. Категориальной грамматикой зависимостей (КГЗ) называется система (3 = (ТГ, С, ¿к <5), где:

W — конечное множество символов, С — конечное множество элементарных категорий, S ~ выделенная в С главная категория,

S — словарь, функция на W такая, что ô(w) С Cat(С) и S(w) конечно для каждого символа w 6 W.

В КГЗ G после приписывания категорий символам слова происходит вывод главной категории S с помощью приведенных ниже правил сокращения. Эти правила имеют вид Г h Г', где Г — сокращаемая строка категорий, а Г' — строка категорий, получающаяся в результате сокращения. В приведённых ниже правилах Ti и Г2 — это произвольные строки категорий из Cat(С)*. Определение 1.4. Правила сокращения * Правила локальной зависимости: L1 : Г1[С]"1[С\а]('2Г2 h Г^а]"1"2^, 4 :ri[e]fl'[a]fcr2 НВД^Га Lr : r![a/Cf'[Cf2r2 h ВД^Гг, Ц:Гг[а}0^Г2 Ь где С 6 С.

Правила итеративной зависимости: I1 : iMCf'^Vf2^ Ь Г1[С*\а]в,ваГ2 /< : Г![С*\а]вГ2 h Г!ИвГ2 Г : ГЛа/СЧ^С^Гг h Т^а/С'}0^ Г0 : Г1[а/С*]«Г2 h ГМа]0Г2, где CG С.

Правило непроективной зависимости: D : Ь

где валентности (/3. /3) образуют правильную пару и 02 не содержит /3, /3.

Правила L1 и Lr — это аналоги классических правила сокращения. При сокращении аргумента С каждое из них создаёт проективную зависимость С и выполняет конкатенацию потенциалов. Правила LÍ и LI — это правила сокращения пустой категории е. Они не создают зависимостей. Правила и Г создают произвольное количество зависимостей С. Правила 110 и Ц служат для удаления итеративного подтипа С*. Правило D сокращает две двойственные поляризованные валентности ¡3 и ¡3 и создаёт непроективную зависимость С. Для пары /3 =/,С, ¡3 =\С эта зависимость идёт слева направо от слова, содержащего в своём потенциале валентность /*С, к слову, содержащему в потенциале \С. Если

(5 =>/С, в =\С, то зависимость С идёт в обратном направлении. Как обычно, через Ь* обозначим рефлексивное н транзитивное замыкание отношения h на множестве Cai(C)*.

Рассмотрим, например, предложение "Летом здесь будут играть дети". Пусть словарь содержит следующие категории: [е]|/0бст-вр ^ ¿(летом), [£]^обст-лок е ¿(здесь), [5/пред/вспом] € ¿(будут), [вспом]^оост-вР^обст-лок е ¿(играть), [пред] £ ¿(дети). Конкатенация этих категорий допускает сокращение до [S] по приведённым правилам. Результирующая структура зависимостей показана на рис. 2 (локальные зависимости показаны сплошными линиями, а нсироектнвные — пунктирными).

Определение 1.5. Слово s = wi... wn € W* принадлежит языку L(G) тогда и только тогда, когда существует строка категорий Г такая, что:

1) Г = 7i .. . 7„, где 7j £ 5(wi) для г = 1,..., п,

2) Г К [5].

Класс всех языков, порождаемых категориальными грамматиками зависимостей, обозначим через £(CDG). Через Ck(CDG) обозначим класс всех языков, порождаемых категориальными грамматиками зависимостей, содержащими не более к типов валентностей.

В приведённом выше правиле сокращения D все валентности вида / Л и \ Л образуют правильные пары в потенциале /*• Лв \ А, если 0 не содержит валентностей типа / Л и \ Л, т.е. \ А является первой доступной валентностью, соответствующей А. Это правило формирования пар называется "первый доступный" и обозначается FA (от англ. first available). Определение КГЗ можно расширить, разрешив дополнительные ограничения на возможность сокращения валентностей. Для этого на множестве всех элементарных категорий вводится функция запретов — отображение 7г: С —» 2е. Эта функция описывает ограничения на расположение правильных пар валентностей. Если У е тт(Х), то пара валентностей типа X не может создать зависимость, ссли между ними есть валентности типа У. Например, если щ{Х) = { У }, я"!(У) = { А' }, то в потенциале =/лХ /-Y \Х \У нет правильных пар. Действительно, / У не позволяет сформировать пару / Л' \Х, а\Х не позволяет сформировать пару /*У \Y. Если же 7г2(А) = {У}, 7Г2(У) = 0, то пара /~Y \У является правильной в в\. Если удалить её из то останется /X \1 — тоже правильная пара.

С учетом функции запретов понятие сбалансированности потенциала изменяется следующим образом. Потенциал называется сбалансированным, если его проекция на каждую пару двойственных поляризованных валентностей является правильным скобочным словом и существует такой порядок правильных пар, что их можно удатять из потенциала, не нарушая ограничений функции запретов. Например, потенциал /*А/*В\А\В/*А\А сбалансирован, если п (А) = {В},тт(В) = 0. Этот же потенциал не будет сбалансированным при тт(А) = {В},п(В) = {Л}. Потенциал /■ А \В \Л не сбалансирован независимо от функции запретов. Таким образом, определение сбалансированности потенциала без функции запретов является частным случаем более общего определения и получается из него при 7г(Х) = 0 для всех X.

Функция запретов используется в следующем определении более широкого класса КГЗ являющемся важным специальным случаем общего определения, содержащегося в работе Диковского4. Определение 1.6. Мультимодальной категориальной грамматикой зависимостей (ммКГЗ) называется система G = {W, С, S, 6, 7г), где: IV — конечное множество символов, С — конечное множество элементарных категорий, S — выделенная в С главная категория,

<5 — словарь, функция на W такая, что S(w) С Caí (С) и 6(w) конечно для каждого w € IV (мы будем задавать его в виде w М- S(w)), 7г: С —¥ 2е — функция запретов.

Как и в КГЗ, в ммКГЗ символам слова приписываются категории и происходит вывод главной категории с помощью правил сокращения. Правила сокращения локальных категорий для ммКГЗ точно такие же, что и для КГЗ. Изменяется лишь правило дальней зависимости. Определение 1.7. Правило дальней зависимости: D : Г^'^Гг Ь Тхав^Т2,

где валентности (/?, ¡3) образуют правильную пару и 02 не содержит /?, Р, а также /* В, \ В, В, \ В для всех В е ir (С), где С — имя валентности /3.

В простейшем случае ограничения означают, что зависимости некоторых типов не могут пересекаться. Например, в естественных языках

4Dikavsky A. Multimodal Categorial Dependency Grammars // Proc. of the 12th Conference on Formal Grammar. Dublin, Ireland, 2007. P. 1-12.

в предложениях с прямой речью зависимости не могут соединять слова, стоящие внутри кавычек, со словами, стоящими вне кавычек. Чтобы обеспечить это, можно соединить открывающие кавычки с закрывающими специальной зависимостью, которую не может пересечь ни одна другая зависимость.

Класс всех языков, порождаемых мультнмодальными категориальными грамматиками зависимостей, обозначим С{ттСОО), а класс всех языков порождаемых такими грамматиками, содержащими не более к типов валентностей, обозначим через Ск(ттСОС).

Из определения следует, что КГЗ-языкп содержат все языки, порождаемые классическими категориальными грамматиками, т.е. все кс-языки, не содержащие пустую строку е. На самом деле этот класс существенно шире класса кс-языков. Мы рассматриваем примеры известных языков, не являющихся контекстно-свободными: Ь\ = { а^а^ ... а^ \ к > О }, Ь2 = {ю е 1У+ | На, = • • • = На„ } и Ь = {ит)~1и) \ и> е {а, Ь}+}. Для языков Ь\ и ¿2 построены порождающие их КГЗ, а для языка — ммКГЗ.

Глава 2 посвящена свойствам категориальных грамматик зависимостей. В параграфе 2.1 рассматриваются нормальные формы для КГЗ.

Известно, что для кс-грамматик существуют различные специальные формы (нормальная форма Хомского, нормальная форма Грей-бах), упрощающие анализ порождаемых ими языков. Мы определяем нормальную форму для КГЗ, аналогичную нормальной форме Грей-бах.

Определенно 2.2. Будем называть КГЗ (3 = (И7, С, 3. 5) грамматикой в нормальной форме, если все её категории имеют один из следующих видов:

1) [X]"

2) [X/Г\°

3) [х/у/г]°,

где X, У, Ъ — элементарные категории, в — потенциал.

Основным результатом этого параграфа является следующая теорема.

Теорема 2.1. Для любой КГЗ (3 = С, Б, 6) существует КГЗ С' = (1У, С', 5, 6') в нормальной форме такая, что ¿((3) = ¿(С). Существует алгоритм, который по произвольной КГЗ С? строит КГЗ С, при этом размер С является полиномиальным относительно раз-

мера С.

Отметим, что эту теорему можно несколько усилить, построив для любой КГЗ (3 эквивалентную ей КГЗ С в нормальной форме такую, что её списки зависимостей не содержат главной категории.

В параграфе 2.2 исследуются свойства замкнутости класса КГЗ-язы-ков. Ранее Дехтярь, Днковский и Зайцев установили, что этот класс замкнут относительно операций объединения, конкатенации, неукора-чивающего гомоморфизма и пересечения с регулярными языками. При этом грамматика для результата выполнения операции содержала существенно больше типов валентностей, чем грамматики для аргументов операции. В следующих теоремах мы устанавливаем более точные результаты, содержащие оценку числа типов валентностей в грамматиках для языков-результатов этих операций.

Теорема 2.2. Если Ьх € Ск{СОв) и Ь2 6 Ск{СОО), то Ь = ЬгиЬ2 € Ск{СОС).

Теорема 2.3. Если Ьх € Ск(СОв), а Ьх € £,(67X7), то Ь = Ьх-Ь2е Сш(СОО).

Теорема 2.4. Если Ь € Ск(СОС) и Й — регулярный язык, то ЬПЯ € А(СЯС).

Теорема 2.5. Пусть IV и Е — два словаря. Пусть определена функция (иеукорачивающий гомоморфизм) т: \¥+ —» Е+. Тогда, если язык Ь е Ск{СБС), то т(Ь) = { т{и>{)т(и}2)...т{и!п) | еЬ}е

В этом же параграфе получен новый результат о замкнутости класса КГЗ-языков относительно обращения гомоморфизма. Теорема 2.6. Если Ь € Ск(СОС) и /г: IV* ->• Е* — произвольный гомоморфизм, то К~1{Ь) 6 Ск(СБС).

Таким образом, установлено, что для любого к класс Ск(СБС) замкнут относительно объединения, пересечения с регулярными языками, неукорачивающего гомоморфизма и обращения гомоморфизма.

В параграфе 2.3 мы получаем специальное представление КГЗ-язы-ков. Для кс-языков известен следующий результат (теорема Хомского-Шютценберже): для любого кс-языка Ь существуют регулярный язык Л, язык Дика Б и гомоморфизм ф такие, что Ь = ф(ПГ] П). КГЗ-языки обладают похожим свойством. Сначала определим понятие скобочного языка, который в нашем случае заменит язык Дика. Определение 2.6. Пусть Е = { а^ а\,..., ап, ап }. Определим для ал-

фавнта Е скобочный язык LCK, для которого его проекция на { o¿, a¿ } (г = 1,..., п) совпадает с языком правильной расстановки скобок { a¡, a¡ }

Аналогом теоремы Хомского-Шютценберже для КГЗ-языков является

Теорема 2.7. Для любого КГЗ-языка L существуют КС-язык L\, скобочный язык LCK и гомоморфизм ó такие, что L = ф(Ь\ П LCK).

В параграфе 2.4 решается задача определения класса автоматов, распознающих КГЗ-языкн. Это класс автоматов, которые дополняют обычные автоматы с магазинной памятью конечным множеством целочисленных счётчиков. При этом выбор действия автомата на каждом шаге не зависит от состояния счётчиков.

Определение 2.7. Автомат с магазинной памятью (МП-автомат) с

независимыми счётчиками — это семёрка М = (£, Q, Z, qa,z0, Р, п), где:

£ — конечный входной алфавит,

Q — конечное множество состояний,

Z — конечный алфавит магазина,

<7о G Q — начальное состояние,

zu € Z — начальный символ магазина,

Р — конечное множество правил,

п — число счётчиков.

Правила имеют вид (q,a,z) (q',a,v), где q, q' € Q, a G SU {е}, 2 6 Z, а € Z*, v = («i,..., v„) — целочисленный вектор.

Эти автоматы используют магазинную память, чтобы проверять сокращение локальных категорий, а счётчики позволяют проверять сбалансированность потенциалов.

Определение 2.8. Конфигурация МП-автомата с независимыми счётчиками М = (£,<2, Z,q0,z0,P,n) — это четверка (q,w,~f,u), где q 6 Q, и> е £*, 7 е Z*, й — (u¡,..., и„) — вектор неотрицательных целых чисел. Отношение перехода за один шаг на множестве конфигураций М: ((/. w."/. й) Иц (q',w', i',v!) означает, что существует правило (q,a,z) —> (q', а, V) € Р такое, что выполняются следующие три условия:

1) w = aw',

2) 7 = zi\ i = ai',

3) v! = й + v.

Отношения Ь^ и HJj определяются стандартным образом.

Фактически числа в счётчиках — это избытки левых валентностей, т.е. количество левых валентностей, для которых пока не найдена со-

ответствующая правая валентность. Положительные числа в правилах соответствуют левым валентностям, а отрицательные — правым. Автомат работает подобно обычному МП-автомату. Дополнительно он изменяет значения счётчиков на каждом шаге, но сам шаг не зависит от этих значений.

Язык, распознаваемый автоматом М определяется опустошением магазина и обнулением счётчиков.

Определение 2.9. Слово гп распознаётся МП-автоматом с независимыми счётчиками М тогда и только тогда, когда

(до, 2о, (0,..., 0)) \-*м (д, е, £, (0,..., 0)). Язык, распознаваемый автоматом М, — это множество всех слов, распознаваемых этим автоматом.

Мы будем рассматривать специальный подкласс автоматов без пустых циклов.

Определение 2.10. МП-автомат с независимыми счётчиками М называется автоматом без пустых циклов, если не существует состояний qu■■■qk (к > 1) таких, что (д;,£, г;) (дг+1,7;,^) € Р для 1 < г < к,

(дЬ76 Р-

Заметим, что без этого ограничения возможна ситуация, когда автомат выполняет ^-команды в цикле и изменяет счётчики. Тогда он сможет неограниченно увеличить счётчики, не читая новых символов. Но все потенциалы в КГЗ имеют конечную длину. Определение автомата без пустых циклов позволяет избежать этой ситуации.

Основными результатами параграфа являются следующие две теоремы.

Теорема 2.8. Любой КГЗ-язык распознаётся некоторым МП-автоматом с независимыми счётчиками и без пустых циклов. При это.м число счётчиков автомата равно числу типов валентностей в КГЗ. Теорема 2.9. Если язык Ь распознаётся МП-автоматом с независимыми счётчиками и без пустых циклов, то Ь\{ е } — КГЗ-язык. При этом число типов валентностей в КГЗ равно числу счётчиков автомата.

Из построений, описанных в теоремах, следует, что для любого МП-автомата с независимыми счётчиками и без пустых циклов существует эквивалентный автомат без е-команд.

В главе 3 изучаются мультимодальные категориальные грамматики зависимостей. В параграфе 3.1 показано, что результат о нормальной

форме для КГЗ непосредственно переносится на ммКГЗ.

В параграфе 3.2 исследуются свойства замкнутости класса ммКГЗ-языков. Устанавливается, что, как и класс КГЗ-языков, он замкнут относительно операций объединения, конкатенации, пересечения с регулярными множествами, неукорачивающего гомоморфизма и обращения гомоморфизма. Кроме того, мы доказываем, что класс ммКГЗ-языков замкнут относительно усечённой итерации.

Теорема 3.8. Если Ь 6 £к(ттСОС), то Ь+ 6 Ск+х{ттСОО).

Тогда справедлива следующая Теорема 3.9. Класс С(ттСБС) является абстрактным семейством языков.

Далее в параграфе 3.2 доказывается, что класс ммКГЗ-языков замкнут относительно пересечения, но не замкнут относительно проекции (теоремы 3.10 и 3.11).

В параграфе 3.3 рассматривается вопрос о полулннейностн ммКГЗ-языков. Известная теорема Парика утверждает, что все ке-языки являются полулинейными. Одним из известных свойств полулинейных языков является то, что длины входящих в них слов содержат бесконечные арифметические прогрессии. Мы доказываем, что язык Ь = { 101001... 102" | п = 3, 5, 7,... } является ммКГЗ-языком. Поскольку множество длин слов этого языка не содержит бесконечных арифметических прогрессии, он неполулннейный. Отсюда выводим Следствие 3.5. Класс ммКГЗ-языков содержит пеполулинейпые языки.

В параграфе 3.4 рассматривается сложность проблемы принадлежности для ммКГЗ-языков. Ранее в работе Дехтяря и Диковского (см. ссылку на стр. 6) было установлено, что проблема определения по КГЗ (3 и слову ъи, принадлежит ли ги языку ¿(6), является КР-полной. Для класса ммКГЗ-языков этот результат может быть усилен. Теорема 3.14. Существует ммКГЗ С с двумя типами валентностей такая, что проблема принадлежности для Ь{С) является ЛГР-полной.

Таким образом, если в ммКГЗ есть хотя бы два типа валентностей, которые не могут пересекаться, то проблема принадлежности оказывается сложной. Отметим, что для грамматик без запретов на пересечение дальних связей существует полиномиальный относительно размеров входного слова алгоритм.

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

ней результаты и сформулирован ряд открытых проблем.

Публикации в рецензируемых научных журналах

[1] Карлов Б.Н. Нормальные формы и автоматы для категориальных грамматик зависимостей // Вестник Тверского государственного университета, серия "Прикладная математика", №35 (95), 2008. С. 23-43.

[2] Карлов Б.Н. О свойствах языков, задаваемых мультнмодальными категориальными грамматиками зависимостей // Всстннк Тверского государственного университета, серия "Прикладная математика", №34, 2011. С. 91-110.

Другие публикации

[3] Карлов Б.Н. О свойствах обобщённых категориальных грамматик зависимостей // Двенадцатая национальная конференция по искусственному интеллекту с международным участием. Труды конференции. Т. 1. М.: Физматлит, 2010. С. 283-290.

[4] Dckhtyar М., Dikovsky A., Karlov В. Iterated dependencies and Kleene iteration // In Proc. of the 15th Conference on Formal Grammar (FG 2010), Copenhagen, Denmark, Lecture Notes in Computer Science №7395, Springer, 2012. P. 6G-81.

[5] Karlov B. Abstract Automata and a Normal Form for Catcgorial Dependency Grammars // Proc. of the 7th International Conference on Logical Aspects of Computational Linguistics (LACL 2012), Nantes, France, Lecture Notes in Computer Science №7351, Springer, 2012. P. 86-102.

Технический редактор A.B. Жильцов Подписано в печать 12.10.2012. Формат 60x84 Vie-Усл. печ. л. 1,12. Тираж 100 экз. Заказ .^507. Тверской государственный университет Редакцнонно-издательское управление Адрес: 170100, г. Тверь, ул. Желябова, 33. Тел. РИУ: (4822) 35-60-63

Введение

1 Основные определения

2 Категориальные грамматики зависимостей

2.1 Нормальные формы.

2.2 Свойства замкнутости.

2.3 Теорема о представлении

2.4 Автоматы для распознавания КГЗ-языков

3 Мультимодальные категориальные грамматики зависимостей

3.1 Нормальные формы.

3.2 Свойства замкнутости.

3.3 Неполулинейность.

3.4 Сложность распознавания ммКГЗ-языков.

Актуальность. Формальные способы описания синтаксической структуры предложения имеют первостепенную важность для большинства задач информатики, связанных с обработкой информации на естественном языке. После основополагающих работ Н. Хомского. определившего четыре базовых класса порождающих грамматик, был определен еще целый ряд типов грамматик, позволяющих вычислять синтаксическую структуру предложения в ходе его вывода или доказательства его правильности. В частности, грамматики зависимостей (специальный тип грамматик) присваивают структуры зависимостей (структуры подчинения) предложениям языка, который они определяют. Теории синтаксиса естественных языков, основанные на понятии зависимости, имеют давнюю традицию, восходящую к средним векам. Теньер впервые систематически описал структуру предложения в терминах именованных бинарных отношений между словами (зависимостей) [7]. Когда два слова ги 1 и связаны в предложении посредством зависимости д (обозначение и)\ -4 и^); является главным словом, а и)2 — зависимым словом. Содержательно, зависимость с1 задаёт ограничения на грамматические и лексические свойства и гиг, на их порядок, контекст и т.п., которые вместе означают, что "гг^ управляет ги2". Например, в структуре зависимостей предложения "Летом здесь играют дети", приведённой на рис. 1, отношение играют дети показывает предикатную зависимость между сказуемым играют и подлежащим дети, в котором главным словом является глагол.

В этом предложении, как и в большинстве обычных предложений русобст-tp пред летом здесь играют дети

Рис. 1: Пример проективной структуры зависимостей ского языка, структура зависимостей проективная, что, несколько упрощая, означает, что зависимости в структуре не пересекаются. Большинство грамматик, порождающих деревья зависимостей, имеют дело только с проективными структурами. С другой стороны, в языках достаточно часто встречаются предложения, имеющие непроективпые структуры зависимостей.

I- >1 летом здесь будут играть дети

Рис. 2: Пример непроективной структуры зависимостей в русском языке

Например, использование будущего времени в предложении "Летом здесь будут играть дети" приводит к появлению двух разрывных зависиобстп-вр обстп-лок -1 0 мостеи играть -—> летом и играть —У здесь, показанных на рис. ¿. Разрывные зависимости встречаются и в других языках. На рис. 3 изображена структура зависимостей французского предложения "Il n'en avait plus besoin" ("Он больше в этом не нуждался"), а на рис. 4 — английского предложения "The person to whom you must refer is Smith" ("Человек, к которому Вы должны обратиться, — Смит"). pred cpmpos-neg clit-p-obj p-obj p" ~ * f Ь li

1 n' en avait plus besoin

Рис. 3: Пример непроективной структуры зависимостей во французском языке

Современная лингвистическая теория синтаксических зависимостей была разработана Мельчуком [37]. Первые точные определения грамматик the person to whom you must refer is Smith

Рис. 4: Пример непроективной структуры зависимостей в английском языке зависимостей появились в работах Хейса [32] и Гайфмана [28]. Они имели много общего с классическими категориальными грамматиками Бар-Хиллела [14] (которые восходят к работам Лесьневского [36] и Айдукеви-ча [12]). Они полностью лексикализованы, используют синтаксические типы вместо правил вывода и естественно подходят для функциональных семантических структур. В 1960 году Бар-Хиллел, Гайфман и Шамир доказали. что формальный язык может быть задан классической категориальной грамматикой тогда и только тогда, когда он является контекстно-свободным [15]. В 1958 году Ламбек ввёл синтаксическое исчисление, расширяющее исчисление категориальных грамматик [35]. В 1986 году Буш-ковский доказал, что грамматики Ламбека в неассоциативном варианте эквивалентны контекстно-свободным грамматикам (кс-грамматикам) [17], а в 1993 году Пентус доказал эквивалентность кс-грамматик и исходных (ассоциативных) грамматик Ламбека [38]. Однако сейчас признано, что кс-грамматики недостаточно выразительны для описания естественных языков. Например, кс-грамматики, как и классические категориальные грамматики, неспособны описывать в предложениях, подобных вышеприведённым. разрывные составляющие. В результате значительный интерес представляет разработка и изучение формальных грамматик, более выразительных, чем кс-грамматики. Например. ТАГ-грамматики Джоши [33], один из классов часто используемых для практических приложений, более выразительны. чем кс-грамматики, и позволяют выражать некоторые контекстные зависимости. Как показали Виай-Шеикер и Уэйр [39], ТАГ-грамматики эквивалентны некоторым грамматикам совершенно иной природы (линейным индексным грамматикам Ахо [11. 29], комбинаторным категориальным грамматикам Стидмана [40] и некоторым другим), разделяя с ними свойства, благодаря которым их называют слабо контекстными. Имеется несколько неэквивалентных понятий слабой контскстности класса грамматик. Одно из них состоит в том, что 1) грамматики этого класса порождают все кс-языки; 2) для них существует алгоритм синтаксического анализа за полиномиальное время; 3) эти грамматики позволяют выразить по меньшей мере некоторые пересекающиеся зависимости; 4) порождаемые ими языки обладают свойством линейного роста, т.е. если все предложения языка упорядочить по длине, то длины соседних предложений могут отличаться не более чем на заранее фиксированную константу. Первые грамматики зависимостей, выражающие неограниченные непроективные зависимости, были определены Диковским в 2001 году [22, 23]. Эти грамматики являются порождающими, а непроективпые зависимости между словами определяются в них через двойственные поляризованные валентности: одноимённые однонаправленные валентности с противоположными знаками. Принцип спаривания двойственных валентностей (РА) аналогичен правильному спариванию скобок. В 2004 году Диковский определил категориальные грамматики зависимостей (КГЗ) [24]. Подобно классическим категориальным грамматикам, КГЗ являются анализирующими, т.е. синтаксическая структура предложения — дерево зависимостей — извлекается в них из доказательства правильности приписывания типов словам. Непроективпые зависимости, как и в порождающих грамматиках зависимостей, определяются через двойственные поляризованные валентности. В последующих совместных работах с Дехтярём определение КГЗ эволюционировало. Используемое ниже окончательное определение КГЗ содержится в [20]. КГЗ хорошо зарекомендовали себя на практике. Например, в университете Нанта разработана и успешно используется для синтаксического анализа и для создания корпусов деревьев зависимостей весьма полная КГЗ французского языка (см. [13. 27]). В статье [25] Диковский определил мультимодальные категориальные грамматики зависимостей (ммКГЗ), обобщающие КГЗ. Их отличие от КГЗ состоит в том. что каждому типу валентностей соответствует своё правило спаривания.

Настоящая диссертационная работа посвящена формальной теории КГЗ и ммКГЗ.

Цели диссертационной работы. Исследование свойств классов категориальных грамматик зависимостей и соответствующих классов порождаемых ими языков. Изучаемые вопросы включают существование нормальных форм КГЗ, существование класса автоматов, распознающих КГЗ-языки, замкнутость классов КГЗ-языков относительно различных операций над языками, полулинейность КГЗ-языков. а также проблему принадлежности для КГЗ.

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

Научная новизна и основные положения, выносимые на защиту. Все полученные в работе результаты являются новыми. На защиту выносятся следующие результаты.

1. Определена нормальная форма для классов КГЗ и ммКГЗ, аналогичная нормальной форме Грейбах для кс-грамматик, и установлена возможность эффективного приведения всякой КГЗ и ммКГЗ к этой нормальной форме.

2. Доказаны свойства замкнутости для классов КГЗ- и ммКГЗ-языков относительно операций объединения, пересечения с регулярными языками. неукорачивающего гомоморфизма, обращения гомоморфизма. конкатенации и усечённой итерации. Установлено, что класс ммКГЗ-языков образует абстрактное семейство языков.

3. Доказано, что любой КГЗ-язык можно представить как проекцию пересечения кс-языка и скобочног "■о языка ск, состоящего из слов, проекции которых на каждый тип скобок являются правильными скобочными словами.

4. Построено расширение автоматов с магазинной памятью (МП-автоматов) — МП-автоматы с независимыми счётчиками. Эти автоматы дополняют обычные МП-автоматы конечным числом целочисленных счётчиков. Их отличие от машин Минского состоит в отсутствии проверки счётчиков на ноль. Доказано, что МП-автоматы с независимыми счётчиками распознают в точности КГЗ-языки.

5. Показано, что класс ммКГЗ-языков содержит неполулинейные языки, в отличие от класса кс-языков.

6. Доказано, что проблема принадлежности слова ммКГЗ-языку является КР-полиой для конкретной ммКГЗ. в отличие от КГЗ, где для каждой грамматики существует полиномиальный алгоритм.

Теоретическая и практическая значимость. Работа носит теоретический характер. Материалы диссертации могут использоваться при чтении специальных курсов студентам и аспирантам, специализирующимся в области компьютерной лингвистики. Кроме того, результаты об автоматах, распознающих КГЗ-языки. и о сложности проблемы принадлежности могут использоваться при построении и анализе практических КГЗ для естественных языков.

Апробация работы Результаты диссертации докладывались автором на семинаре по теоретической информатике в Тверском государственном университете, на семинаре по математической логике в Петербургском отделении математического института РАН и на двенадцатой национальной конференции по искусственному интеллекту с международным участием "КИИ-2010". Некоторые результаты были представлены в совместном докладе на 15-й международной конференции по формальным грамматикам ("Formal Grammars 2010". Copenhagen. Denmark). Статья [4] была представлена в 2009 году на "Открытый конкурс на лучшую научную работу студентов по естественным, техническим и гуманитарным наукам в высших учебных заведениях Российской Федерации" и получила в этом конкурсе медаль "За лучшую научную студенческую работу". Работа поддерживалась грантами РФФИ 08-01-00241 и 10-01-00532а.

Публикации. Список публикаций по теме диссертации включает 5 работ: [4, 5, 6, 21, 34]. Работы [4, 6] опубликованы в издании, входящем в список рекомендованных ВАК ведущих рецензируемых изданий. Работы [21, 34] представляют доклады на международных конференциях и опубликованы в серии Lecture Notes in Computer Science.

Результаты совместной работы [21], вошедшие в диссертацию, принадлежат автору.

Структура и объём диссертации. Диссертация состоит из настоящего введения, трёх глав основной части, заключения и списка литературы. Общий объём работы — 103 стр. Список литературы содержит 40 наименований.

Обзор работы

В главе 1 мы приводим основные определения, связанные с КГЗ. В частности, в ней определено понятие поляризованных валентностей, описан класс возможных категорий слов, приведены правила вывода для сокращения в КГЗ и даны определения КГЗ и ммКГЗ. Также в этой главе приведены примеры КГЗ-языков, не являющихся контекстно-свободными.

Глава 2 посвящена исследованию свойств КГЗ. В параграфе 2.1 строится нормальная форма, аналогичная нормальной форме Грейбах для кс-языков и доказывается теорема 2.1 о том, что по любой КГЗ можно эффективно построить эквивалентную КГЗ в нормальной форме полиномиального размера по отношению к исходной КГЗ. В параграфе 2.2 исследуются свойства замкнутости. В теоремах 2.2-2.6 устанавливается замкнутость класса КГЗ-языков относительно операций объединения, конкатенации, пересечения с регулярными множествами, неукорачивающего гомоморфизма и обращения гомоморфизма. В параграфе 2.3 получен результат, аналогичный теорема Хомского-Шютцеибсрже для кс-языков. Доказана теорема 2.7 о том, что любой КГЗ-язык можно получить как гомоморфизм пересечения кс-языка с некоторым скобочным языком. В параграфе 2.4 определён класс автоматов с магазинной памятью с независимыми счётчиками. Содержательно, это обычные автоматы с магазинной памятью, дополнительно оснащённые конечным числом счётчиков, которые служат для обработки поляризованных валентностей. В теоремах 2.8 и 2.9 установлено, что класс языков, распознаваемых этими автоматами, совпадает с классом КГЗ-языков.

Глава 3 посвящена исследованию свойств ммКГЗ-языков. В параграфе 3.1 мы определяем нормальную форму ммКГЗ и доказываем теорему 3.2 о существовании нормальной формы. В параграфе 3.2 доказано, что класс ммКГЗ-языков замкнут относительно операций объединения, конкатенации, пересечения с регулярными множествами, неукорачивающего гомоморфизма, обращения гомоморфизма и усечённой итерации (теоремы 3.3-3.8). На основании этих результатов в теореме 3.9 делается вывод, что класс ммКГЗ-языков образует абстрактное семейство языков (см. [31]). Также показано, что класс ммКГЗ-языков замкнут относительно пересечения (теорема 3.10), но не замкнут относительно проекции (теорема 3.11).

Языки ряда других классов являются полулинейными, в частности, полулинейны все кс-языки. В параграфе 3.3 в теореме 3.12 мы приводим пример неполулинейного языка, порождаемого ммКГЗ. В параграфе 3.4 рассматривается проблема принадлежности для ммКГЗ: по грамматике О и слову т определить, принадлежит ли слово и) языку, порождаемому С. Для первоначального варианта КГЗ была доказана NP-IЮлнoтa этой проблемы в общем случае, когда переменными являются и грамматика, и слово (см. [19]). В теореме 3.14 мы показываем, что для ммКГЗ эта проблема является КР-полной для одной грамматики и порождаемого ей языка.

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

Заключение

В главе 1 мы привели основные определения, связанные с КГЗ. В частности, в ней было определено понятие поляризованных валентностей, описан класс возможных категорий слов и приведены правила вывода для сокращения в КГЗ. Также в этой главе были приведены примеры КГЗ-языков, пе являющихся контекстно-свободными.

Глава 2 была посвящена исследованию свойств КГЗ. В параграфе 2.1 была построена нормальная форма, аналогичная нормальной форме Грей-бах для кс-языков и доказана теорема 2.1 о том, что по любой КГЗ можно эффективно построить эквивалентную КГЗ в нормальной форме полиномиального размера по отношению к исходной КГЗ. В параграфе 2.2 были исследованы свойства замкнутости. В теоремах 2.2-2.С была уста-навлена замкнутость класса КГЗ-языков относительно операций объединения, конкатенации, пересечения с регулярными множествами, неукора-чивающего гомоморфизма и обращения гомоморфизма. В параграфе 2.3 был получен результат, аналогичный теорема Хомского-Шютценберже для кс-языков. Была доказана теорема 2.7 о том, что любой КГЗ-язык можно получить как гомоморфизм пересечения кс-языка с некоторым скобочным языком. В параграфе 2.4 был определён класс автоматов с магазинной памятью с независимыми счётчиками. В теоремах 2.8 и 2.9 было установлено, что класс языков, распознаваемых этими автоматами, совпадает с классом КГЗ-языков.

Глава 3 была посвящена исследованию свойств ммКГЗ-языков. В параграфе 3.1 мы определили нормальную форму ммКГЗ и доказали теорему 3.2 о существовании нормальной формы. В параграфе 3.2 доказано. что класс ммКГЗ-языков замкнут относительно операций объединения. конкатенации, пересечения с регулярными множествами, неукорачи-вающего гомоморфизма, обращения гомоморфизма и усечённой итерации (теорема 3.8). На основании этих результатов в теореме 3.9 сделан вывод, что класс КГЗ-языков образует абстрактное семейство языков. Также было показано, что класс ммКГЗ-языков замкнут относительно пересечения (теорема 3.10), но не замкнут относительно проекции (теорема 3.11). В параграфе 3.3 в теореме 3.12 мы привели пример неполулинейного языка. порождаемого ммКГЗ. В параграфе 3.4 рассмотрена проблема принадлежности для ммКГЗ. В теореме 3.14 мы показали, что для ммКГЗ эта проблема является МР-полной для одной грамматики и порождаемого ей языка.

Перечислим некоторые интересные вопросы о КГЗ и КГЗ-языках, которые остаются открытыми.

1. Справедлив ли для КГЗ-языков какой-либо вариант леммы о разрастании?

2. Является ли язык Ьсори — { ипи \ ш б Е* } КГЗ-языком? (В статье [19] авторы предположили, что он не является КГЗ-языком.)

3. Являются ли все КГЗ-языки полулинейными?

4. Замкнут ли класс КГЗ-языков относительно итерации и проекции?

5. Влияет ли количество типов валентностей на выразительную силу КГЗ? Мы предполагаем, что существует иерархия но числу типов валентностей.

6. Верно ли, что классы КГЗ- и ммКГЗ-языков не совпадают?

7. Каково соотношение классов КГЗ- и ммКГЗ-языков с другими классами, расширяющими кс-языки?

1. Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970. 326 с.

2. Гладкий A.B. Формальные грамматики и языки. М.: Наука, 1973. 368 с.

3. Гладкий A.B., Мельчук И.А. Элементы математической лингвистики. М.: Наука, 1969. 192 с.

4. Карлов Б.Н. Нормальные формы и автоматы для категориальных грамматик зависимостей // Вестник Тверского государственного университета, серия «Прикладная математика», №35 (95), 2008. С. 23-43.

5. Карлов Б.Н. О свойствах обобщённых категориальных грамматик зависимостей // Двенадцатая национальная конференция по искусственному интеллекту с международным участием. Труды конференции. Т. 1. М.: Физматлит, 2010. С. 283-290.

6. Карлов Б.Н. О свойствах языков, задаваемых мультимодальными категориальными грамматиками зависимостей // Вестник Тверского государственного университета, серия "Прикладная математика", №34, 2011. С. 91-110.

7. Теньер JI. Основы структурного синтаксиса. М.: Прогресс, 1988. 656 с.

8. Хомский Н. Три модели для описания языка // Кибернетический сборник, вып. 2, ИЛ, 1961. С. 237-266.

9. Хомский Н. Синтаксические структуры // Сб. "Новое в лингвистике", вып. 2, "Прогресс", 1962. С. 412-527.

10. Хомский Н. О некоторых формальных свойствах грамматик // Кибернетический сборник, вып. 5, ИЛ, 1962. С. 279-311.

11. Aho А. V. Indexed grammars — An extension to context-free grammars //J. ACM, 15, 1968. P. 647-671.

12. Ajdukiewicz K. Die syntaktische Konnexität // Studia Philosophica, №1, 1935. P.l-27.

13. Bar-Hillel Y. A quasi-arithmetical notation for syntactic description // Language, 29(1), 1953. P. 47-58.

14. Buszkowski W. Generative power of non-associative Lambek calculus // Bull. Polish Acad. Sei. Math., 34, 1986. P. 507-516.

15. Cook S.A. The complexity of theorem-proving procedures // Proc. 3-th Ann ACM Symp. on Theory of Computing, 1971. P.151-158.

16. Dekhtyar M., Dikovsky A. Categorial Dependency Grammars // Proc. of Int. Conf. on Categorial Grammars, Montpellier, 2004. P. 76-91.

17. Dekhtyar M., Dikovsky A. Generalized Categorial Dependency Grammars // Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, Lecture Notes in Computer Science, vol. 4800, 2008. P. 230-255.

18. Dekhtyar M., Dikovsky A., Karlov B. Iterated dependencies and Kleene iteration // Proc. of the 15th Conference on Formal Grammar (FG 2010), Copenhagen, Denmark, Lecture Notes in Computer Science vol. 7395, Springer, 2012. P. 66-81.

19. Dikovsky A. Grammars for Local and Long Dependencies // Proc. of the Intern. Conf. ACL'2001, Toulouse, France, 2001. P. 156-163.

20. Dikovsky A. Polarized Non-projective Dependency Grammars // Proc. of the Fourth International Conference on Logical Aspects of Computational Linguistics (LACL). LNAI, №2099, 2001. P. 139-157.

21. Dikovsky A. Dependencies as Categories // Recent Advances in Dependency Grammars, 2004. P. 90-97.

22. Dikovsky A. Multimodal Categorial Dependency Grammars // Proc. of the 12th Conference on Formal Grammar, 2007. P. 1-12.

23. Dikovsky A. Towards Wide Coverage Categorial Dependency Grammars // Proc. of the ESSLLI'2009 Workshop on Parsing with Categorial Grammars, Bordeaux, France, 2009.

24. Dikovsky A. Categorial Dependency Grammars: from Theory to Large Scale Grammars // Proc. of the 1st Intern. Conf. on Dependency Linguistics (Depling 2011). Barcelona, Spain, 2011. http://depling.org/proceedingsDepling2011/

25. Gaifman II. Dependency systems and phrase structure systems // Information and Control, 1965, vol. 8, №. P. 304-337.

26. Gazdar G. Applicability of indexed grammras to natural languages // Proc. of Natural Language Parsing and Linguistic Theories Conference, Dordrecht, Holland, 1988. P. 69-94.

27. Ginsburg S., Greibach S.A., Harrison M.A. One-way stack automata // Journal of The ACM, vol. 14, m, 1967. P. 389-418.

28. Ginsburg S., Greibach S. Abstract families of languages // Mem. Amer. Math. Soc., 87, 1969. P. 1-32.

29. Hays D. G. Grouping and dependency theories/'/ Proc. of the National Symp. on Machine Translation, Englewood Cliffs, NY, 1961. P. 258-266.

30. Joshi A.K., Levy L.S., Takahashi M. Tree adjunct grammars // Journ. of Comput. and Syst. Sci., 10(1), 1975. P. 136-163.

31. Lambek J. The mathematics of sentence structure // American Mathematical Monthly, 1958. P. 154-170.

32. Lesniewski S. Grundziige eines neuen Systems der Grundlagen der Mathematik // Fundam. Math., vol. 14, 1929. P. 1-81.

33. Mel'cuk I. Dependency Syntax. SUNY Press, Albany, NY, 1988. 428 p.

34. Comp. Sei., Montreal, 1993. P. 429-433.

35. Vijay-Shanker K., Weir D.J. The Equivalence of Four Extensions of Context-Free Grammars // Mathematical Study Theory, vol. 27, 1994. P. 511-545.

36. Steedman M. Combinators and grammars // In R. Oehrle, E. Bach, and D. Wheeler, editors, Categorial Grammars and Natural Language Structures. Foris, Dordrecht, 1986. P. 417-442.