Регулярная древовидная грамматика

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

Определение

Регулярная древовидная грамматика G определяется набором

г знак равно ( N , Σ, Z , п ),

где

N — конечное множество нетерминалов,
Σ — ранговый алфавит (т. е. алфавит, символы которого имеют соответствующую арность ), не пересекающийся с N ,
Z — начальный нетерминал, при этом $Z \in N$ и
P — конечное множество продукций формы A → t , где $A \in N$ и $t \in T Σ (N)$ , где T _Σ ( N ) — ассоциированная алгебра терминов , т.е. набор всех деревьев, составленных из символов в $Σ \cup N$ в соответствии с их арностью, где нетерминалы считаются нулевыми.

Происхождение деревьев

Грамматика G неявно определяет набор деревьев: любое дерево, которое может быть получено из Z с использованием набора правил P называется описываемым G , . набор деревьев известен язык G. Этот как Более формально отношение ⇒ _G на множестве T _Σ ( N ) определяется следующим образом:

Дерево $t 1 \in T Σ (N)$ можно за один шаг превратить в дерево $t 2 \in T Σ (N)$ (короче: t ₁ ⇒ _G t ₂ ), если существует контекст S и продукция $(A \to t) \in P$ такие, что:

t ₁ = S [ A ], и
т ₂ знак равно S [ т ].

Здесь контекст означает дерево, в котором ровно одно отверстие; если S контекстом, S [ t ] обозначает результат заполнения дерева t в дырку S. является таким

Древовидным языком, порожденным G , является язык $L (G) = {t \in T Σ | Z \Rightarrow Г * т}$ .

Здесь T _Σ обозначает множество всех деревьев, составленных из символов Σ, а ⇒ _{G *} обозначает последовательные применения ⇒ _G .

Язык, порожденный некоторой регулярной древовидной грамматикой, называется регулярным древовидным языком .

Примеры

Пусть G ₁ = ( N ₁ , Σ ₁ , Z ₁ , P ₁ ), где

N ₁ = { Bool , BList } — наш набор нетерминалов,
Σ ₁ = { true , false , nil , cons (.,.) } — наш ранжированный алфавит, арность указана фиктивными аргументами (т. е. символ cons имеет арность 2),
Z ₁ = BList — наш стартовый нетерминал, а
набор П ₁ состоит из следующих продукций:
- Логическое значение → ложь
- Бул → правда
- BList → ноль
- BList → минусы ( Bool , BList )

Пример вывода из грамматики G ₁ :

BList ⇒ минусы ( Bool , BList ) ⇒ минусы ( ложь , минусы ( Bool , BList )) ⇒ минусы ( ложь , минусы ( истина , ноль )).

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

Язык дерева, порожденный G _{1 ,} представляет собой набор всех конечных списков логических значений, то есть L ( G ₁ ) оказывается равным T _Σ1 . Грамматика G ₁ соответствует объявлениям алгебраических типов данных (на языке программирования Standard ML ):

  datatype Bool
    = false
    | true
  datatype BList
    = nil
    | cons of Bool * BList

Каждый член L ( G ₁ ) соответствует значению Standard-ML типа BList.

В качестве другого примера, пусть $G 2 = (N 1, Σ 1, BList 1, P 1 \cup P 2)$ , используя нетерминальный набор и алфавит сверху, но расширяя производственный набор с помощью P ₂ , состоящий из следующих продукций:

BList ₁ → минусы ( истина , BList )
BList ₁ → минусы ( ложь , BList ₁ )

Язык L ( G2 _хотя ) — это набор всех конечных списков логических значений, которые содержат true бы один раз . Набор L ( G ₂ ) не имеет аналога типа данных ни в стандартном ML, ни в каком-либо другом функциональном языке. Это собственное подмножество L ( G ₁ ). Термин, приведенный выше в качестве примера, также находится в L ( G ₂ ), как показывает следующий вывод:

Список ₁ ⇒ минусы ( ложь , BList ₁ ) ⇒ минусы ( ложь , минусы ( правда , BList )) ⇒ минусы ( ложь , минусы ( истина , ноль )).

Свойства языка

Если L ₁ , L ₂ оба являются регулярными древесными языками, то множества деревьев $L 1 \cap L 2, L 1 \cup L 2$ и L ₁ \ L ₂ также являются регулярными древесными языками, и можно решить, является ли $L 1 \subseteq L 2$ , и является ли L ₁ = L ₂ .

Альтернативные характеристики и связь с другими формальными языками

Регулярные древовидные грамматики являются обобщением грамматик обычных слов .
Регулярные древовидные языки также являются языками, распознаваемыми древесными автоматами «снизу вверх» и недетерминированными древесными автоматами «сверху вниз». ^{[ 2 ]}
Раджив Алур и Партасарати Мадхусудан связали подкласс обычных языков двоичного дерева с вложенными словами и языками с видимым расположением вниз . ^{[ 3 ]}^{[ 4 ]}

Приложения

Приложения регулярных древовидных грамматик включают:

Выбор инструкций при генерации кода компилятора ^{[ 5 ]}
Процедура принятия решения для первого порядка логической теории формул над равенством (=) и набором членства (ε) в качестве единственных предикатов ^{[ 6 ]}
Решение ограничений на математические множества ^{[ 7 ]}
Набор всех истин, выразимых в логике первого порядка о конечной алгебре (которая всегда является регулярным древовидным языком) ^{[ 8 ]}
Граф-поиск ^{[ 9 ]}

См. также

Установить ограничение - обобщение регулярных древовидных грамматик.
Грамматика, примыкающая к дереву

Ссылки

^ «Регулярные древовидные грамматики как формализм для занижения области видимости». CiteSeerX 10.1.1.164.5484 .
^ Комон, Хьюберт; Доше, Макс; Гиллерон, Реми; Лёдинг, Кристоф; Жакмар, Флоран; Лужье, Денис; Тисон, Софи; Томмаси, Марк (12 октября 2007 г.). «Техника и применение древовидных автоматов» . Проверено 25 января 2016 г.
^ Алур, Р.; Мадхусудан, П. (2004). «Языки с видимым нажатием вниз» (PDF) . Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '04 . стр. 202–211. дои : 10.1145/1007352.1007390 . ISBN 978-1581138528 . S2CID 7473479 . Раздел 4, Теорема 5,
^ Алур, Р.; Мадхусудан, П. (2009). «Добавление вложенности к словам» (PDF) . Журнал АКМ . 56 (3): 1–43. CiteSeerX 10.1.1.145.9971 . дои : 10.1145/1516512.1516518 . S2CID 768006 . Раздел 7
^ Эммельманн, Хельмут (1991). «Выбор кода путем регулярно контролируемого переписывания терминов». Генерация кода — концепции, инструменты, методы . Семинары по информатике. Спрингер. стр. 3–29.
^ Комон, Хьюберт (1990). «Уравнения в алгебрах с порядковой сортировкой». Учеб. ИКАЛП .
^ Гиллерон, Р.; Тайсон, С.; Томмаси, М. (1993). «Решение систем множественных ограничений с использованием древовидных автоматов». 10-й ежегодный симпозиум по теоретическим аспектам информатики . ЛНКС. Том. 665. Спрингер. стр. 505–514.
^ Бургхардт, Йохен (2002). «Аксиоматизация конечных алгебр». Достижения в области искусственного интеллекта . ЛНАИ. Том. 2479. Спрингер. стр. 222–234. arXiv : 1403.7347 . Бибкод : 2014arXiv1403.7347B . ISBN 3-540-44185-9 .
^ Зив-Укельсон, Смолы (2016). Алгоритмы поиска в сети по регулярной древовидной грамматике и их применение для анализа закономерностей вирусных инфекций человека . Дж. Комп. Био. [1]

Дальнейшее чтение

Регулярные древовидные грамматики были описаны еще в 1968 году:
- Брейнерд, WS (1968). «Минимализация древовидных автоматов» . Информация и контроль . 13 (5): 484–491. дои : 10.1016/s0019-9958(68)90917-0 . hdl : 10945/40204 .
- Тэтчер, Дж.В.; Райт, Дж. Б. (1968). «Обобщенная теория конечных автоматов с применением к задаче решения логики второго порядка». Теория математических систем . 2 (1): 57–81. дои : 10.1007/BF01691346 . S2CID 31513761 .
Книга, посвященная древовидным грамматикам: Ниват, Морис; Подельски, Андреас (1992). Древовидные автоматы и языки . Исследования в области компьютерных наук и искусственного интеллекта. Том. 10. Северная Голландия.
Алгоритмы на основе регулярных древовидных грамматик обсуждаются с точки зрения эффективности в: Эйкен, А.; Мерфи, Б. (1991). «Реализация регулярных древовидных выражений». Конференция ACM по функциональным языкам программирования и компьютерной архитектуре . стр. 427–447. CiteSeerX 10.1.1.39.3766 .
Учитывая отображение деревьев в веса, Дональда Кнута обобщение алгоритма кратчайшего пути Дейкстры может быть применено к грамматике обычного дерева для вычисления для каждого нетерминала минимального веса выводимого дерева. Основываясь на этой информации, легко перечислить его язык в порядке возрастания веса. В частности, любой нетерминал с бесконечным минимальным весом порождает пустой язык. Видеть: Кнут, DE (1977). «Обобщение алгоритма Дейкстры». Письма об обработке информации . 6 (1): 1–5. дои : 10.1016/0020-0190(77)90002-3 .
Обычные древесные автоматы были обобщены, чтобы допускать проверки равенства между одноуровневыми узлами в деревьях. Видеть: Богерт, Б.; Тайсон, Софи (1992). «Ограничения равенства и неравенства на прямых подчленах в древовидных автоматах». Учеб. 9-й СТАКС . ЛНКС. Том. 577. Спрингер. стр. 161–172.
Разрешение проверок равенства между более глубокими узлами приводит к неразрешимости. Видеть: Томмаси, М. (1991). Древовидные автоматы с проверками связи между двоюродными братьями . ЛИВЛ-ИТ.

[1] «Регулярные древовидные грамматики как формализм для занижения области видимости». CiteSeerX 10.1.1.164.5484 .

[Comon-2] Комон, Хьюберт; Доше, Макс; Гиллерон, Реми; Лёдинг, Кристоф; Жакмар, Флоран; Лужье, Денис; Тисон, Софи; Томмаси, Марк (12 октября 2007 г.). «Техника и применение древовидных автоматов» . Проверено 25 января 2016 г.

[Alur2004-3] Алур, Р.; Мадхусудан, П. (2004). «Языки с видимым нажатием вниз» (PDF) . Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '04 . стр. 202–211. дои : 10.1145/1007352.1007390 . ISBN 978-1581138528 . S2CID 7473479 . Раздел 4, Теорема 5,

[Alur2009-4] Алур, Р.; Мадхусудан, П. (2009). «Добавление вложенности к словам» (PDF) . Журнал АКМ . 56 (3): 1–43. CiteSeerX 10.1.1.145.9971 . дои : 10.1145/1516512.1516518 . S2CID 768006 . Раздел 7

[5] Эммельманн, Хельмут (1991). «Выбор кода путем регулярно контролируемого переписывания терминов». Генерация кода — концепции, инструменты, методы . Семинары по информатике. Спрингер. стр. 3–29.

[6] Комон, Хьюберт (1990). «Уравнения в алгебрах с порядковой сортировкой». Учеб. ИКАЛП .

[7] Гиллерон, Р.; Тайсон, С.; Томмаси, М. (1993). «Решение систем множественных ограничений с использованием древовидных автоматов». 10-й ежегодный симпозиум по теоретическим аспектам информатики . ЛНКС. Том. 665. Спрингер. стр. 505–514.

[8] Бургхардт, Йохен (2002). «Аксиоматизация конечных алгебр». Достижения в области искусственного интеллекта . ЛНАИ. Том. 2479. Спрингер. стр. 222–234. arXiv : 1403.7347 . Бибкод : 2014arXiv1403.7347B . ISBN 3-540-44185-9 .

[9] Зив-Укельсон, Смолы (2016). Алгоритмы поиска в сети по регулярной древовидной грамматике и их применение для анализа закономерностей вирусных инфекций человека . Дж. Комп. Био. [1]

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]