Грамматика, примыкающая к дереву - Tree-adjoining grammar

Грамматика, примыкающая к дереву (ТЕГ) это грамматический формализм определяется Аравинд Джоши. Грамматики, примыкающие к дереву, чем-то похожи на контекстно-свободные грамматики, но элементарной единицей перезаписи является дерево, а не символ. В то время как контекстно-свободные грамматики имеют правила для перезаписи символов как строк других символов, в грамматиках, примыкающих к дереву, есть правила для перезаписи узлов деревьев как других деревьев (см. дерево (теория графов) и дерево (структура данных) ).

История

TAG возникла в результате исследований Джоши и его учеников семейства дополнительных грамматик (AG),^[1] "строковая грамматика" Зеллиг Харрис.^[2] Ручка AG экзоцентрический свойства языка естественным и эффективным способом, но не имеют хорошей характеристики эндоцентрический конструкции; обратное верно для переписывать грамматики, или же грамматика фразеологической структуры (ПСЖ). В 1969 году Джоши представил семейство грамматик, которое использует эту взаимодополняемость, смешивая два типа правил. Для генерации словаря строк для правил присоединения достаточно нескольких очень простых правил перезаписи. Это семейство отличается от Иерархия Хомского-Шютценбергера но пересекает его интересным и лингвистически значимым образом.^[3] Центральные и вспомогательные струны также могут быть сгенерированы грамматика зависимостей, полностью избегая ограничений систем перезаписи.^[4]^[5]

Описание

Правила в теге - это деревья со специальным листовым узлом, известным как ножной узел, привязанный к слову. В TAG есть два типа основных деревьев: исходный деревья (часто обозначаемые как ' ${ displaystyle alpha}$ ') и вспомогательный деревья (' ${ displaystyle beta}$ '). Исходные деревья представляют собой основные отношения валентности, а вспомогательные деревья допускают рекурсию.^[6]Вспомогательные деревья имеют корневой (верхний) узел и нижний узел, помеченные одним и тем же символом. Деривация начинается с исходного дерева, комбинируемого через замена или же примыкание. Подстановка заменяет пограничный узел другим деревом, верхний узел которого имеет ту же метку. Метка корня / основания вспомогательного дерева должна совпадать с меткой узла, к которому оно примыкает. Таким образом, присоединение может иметь эффект вставки вспомогательного дерева в центр другого дерева.^[4]

Другие варианты TAG позволяют многокомпонентные деревья, деревья с несколькими опорными узлами и другие расширения.

Сложность и применение

Грамматики, примыкающие к дереву, более эффективны (с точки зрения слабая генеративная способность ) чем контекстно-свободные грамматики, но менее мощный, чем линейные системы перезаписи без контекста,^[7] индексированный^{[примечание 1]} или же контекстно-зависимый грамматики.

Тег может описывать язык квадратов (на котором повторяется произвольная строка), а язык ${ displaystyle {a ^ {n} b ^ {n} c ^ {n} d ^ {n} | 1 Leq n }}$ . Этот тип обработки может быть представлен встроенный автомат выталкивания.Языки с кубиками (т. Е. Тройными строками) или с более чем четырьмя различными символьными строками одинаковой длины не могут быть сгенерированы смежными с деревом грамматиками.

По этим причинам грамматики, примыкающие к дереву, часто описываются как слегка контекстно-зависимый Предполагается, что эти классы грамматики достаточно мощны, чтобы моделировать естественные языки оставаясь при этом эффективно разборчивый в общем случае.^[8]

Эквивалентности

Виджай-Шанкер и Вейр (1994)^[9] продемонстрировать, что линейные индексированные грамматики, комбинаторно-категориальная грамматика, грамматики, примыкающие к дереву, и основные грамматики находятся слабо эквивалентный формализмов, поскольку все они определяют одни и те же строковые языки.

Лексикализованный

Лексикализованные грамматики, примыкающие к дереву (LTAG) - это вариант TAG, в котором каждое элементарное дерево (начальное или вспомогательное) связано с лексическим элементом. Лексикализованная грамматика для английского языка была разработана исследовательской группой XTAG при Институте когнитивных исследований Университета Пенсильвании.^[5]

Примечания

^ поскольку для каждой грамматики, примыкающей к дереву, можно найти линейную индексированную грамматику, дающую один и тот же язык, см. ниже, а для последнего можно найти слабо эквивалентную (правильную) индексированную грамматику, в свою очередь, см. Индексированная грамматика # Вычислительная мощность

внешняя ссылка

Проект XTAG, который использует TAG для обработки естественного языка.
Учебник по TAG
Документация СемКонст Краткий обзор проблем синтаксиса и семантического интерфейса в рамках TAG.
Проект TuLiPa Архитектура лингвистического анализа Тюбингена (TuLiPA) - это мультиформализмная синтаксическая (и семантическая) среда синтаксического анализа, разработанная в основном для многокомпонентное дерево смежных грамматик с кортежи деревьев
Набор инструментов Metagrammar который предоставляет несколько инструментов для редактирования и компиляции МетаГрамматики в теги. Он также включает в себя широкий охват французских метаграмм.
LLP2 А лексикализованное дерево, примыкающее к грамматике парсер, обеспечивающий простую в использовании графическую среду (страница на французском языке)

[8] поскольку для каждой грамматики, примыкающей к дереву, можно найти линейную индексированную грамматику, дающую один и тот же язык, см. ниже, а для последнего можно найти слабо эквивалентную (правильную) индексированную грамматику, в свою очередь, см. Индексированная грамматика # Вычислительная мощность

[JoshiKosarajuYamada1969-1] Джоши, Аравинд; С. Р. Косараджу; Х. Ямада (1969). «Струнные дополнительные грамматики». Труды десятого ежегодного симпозиума по теории автоматов, Ватерлоо, Канада. Цитировать журнал требует | журнал = (помощь)Джоши, Аравинд К .; Косараджу, С. Рао; Ямада, Х. М. (1972), "Струнные дополнительные грамматики: I. Локальное и распределенное присоединение", Информация и контроль, 21 (2): 93–116, Дои:10.1016 / S0019-9958 (72) 90051-4Джоши, Аравинд К .; Косараджу, С. Рао; Ямада, Х. М. (1972), "Строковые дополнительные грамматики: II. Эквивалентное представление, нулевые символы и лингвистическая релевантность", Информация и контроль, 21 (3): 235–260, Дои:10.1016 / S0019-9958 (72) 80005-6

[2] Харрис, Зеллиг С. (1962). Строковый анализ структуры предложения. Статьи по формальной лингвистике. 1. Гаага: Mouton & Co.

[Joshi1969-3] Джоши, Аравинд (1969). «Свойства формальных грамматик со смешанными типами правил и их лингвистическая значимость». Труды Третьего международного симпозиума по компьютерной лингвистике, Стокгольм, Швеция. Цитировать журнал требует | журнал = (помощь)

[joshi-rambow2003-4] а ^б Джоши, Аравинд; Оуэн Рамбоу (2003). «Формализм для грамматики зависимостей, основанный на грамматике, примыкающей к дереву» (PDF). Материалы конференции по теории смыслового текста..

[xtagenglish-5] а ^б "Лексикализованное дерево, примыкающее к грамматике английского языка".

[jurafsky-martin2000-6] Юрафски, Даниэль; Джеймс Х. Мартин (2000). Обработка речи и языка. Река Аппер Сэдл, Нью-Джерси: Prentice Hall. п. 354.

[7] Каллмейер, Лаура (2010). Анализ вне контекстно-свободных грамматик. Springer. Здесь: с.215-216

[joshi1985-9] Джоши, Аравинд (1985). «Насколько необходима контекстная чувствительность для характеристики структурных описаний». В Д. Даути; Л. Карттунен; А. Цвикки (ред.). Обработка естественного языка: теоретические, вычислительные и психологические аспекты. Нью-Йорк, Нью-Йорк: Издательство Кембриджского университета. стр.206 –250.

[vijayshankarAndWeir1995-10] Виджай-Шанкер К. и Вейр Дэвид Дж. 1994. Эквивалентность четырех расширений контекстно-свободных грамматик. Математическая теория систем 27 (6): 511–546.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[примечание 1]

[8]

[9]