Грамматика регулярных деревьев

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

Определение

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

G = ( N , Σ, Z , P ),

куда

N - конечное множество нетерминалов,
Σ - это ранжированный алфавит (т. Е. Алфавит, символы которого имеют ассоциированную арность ), не пересекающийся с N ,
Z - начальный нетерминал, где Z ∈ N , и
P - конечное множество продукций вида A → t , где A ∈ N , и t ∈ T _Σ ( N ), где T _Σ ( N ) - ассоциированная термальная алгебра , т. Е. Множество всех деревьев, составленных из символов в Σ ∪ N согласно их арности, где нетерминалы считаются нулевыми.

Вывод деревьев

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

Дерево t ₁ ∈ T _Σ ( N ) может быть преобразовано за один шаг в дерево t ₂ ∈ T _Σ ( N ) (короче: t ₁ ⇒ _G t ₂ ), если существует контекст S и продукция ( A → t ) ∈ P такая, что:

t ₁ = S [ A ], и
t ₂ = S [ t ].

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

Язык деревьев, порожденный G, - это язык L ( G ) = { t ∈ T _Σ | Z ⇒ _{G *} t }.

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

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

Примеры

Пример дерева вывода из G ₁ в линейной (верхняя левая таблица) и графическом (основное изображение) обозначении

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

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

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

BList ⇒ cons ( Bool , BList ) ⇒ cons ( false , cons ( Bool , BList )) ⇒ cons ( false , cons ( true , nil )).

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

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

 тип данных  Bool  =  false  |  истинный  тип данных  BList  =  nil  |  минусы  от  Bool  *  Blist

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

В качестве другого примера, пусть G ₂ = ( N ₁ , Σ ₁ , BList1 , P ₁ ∪ P ₂ ), используя нетерминальный набор и алфавит сверху, но расширяя производственный набор с помощью P ₂ , состоящий из следующих продуктов:

BList1 → cons ( истина , BList )
BList1 → cons ( ложь , BList1 )

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

BList1 ⇒ cons ( false , BList1 ) ⇒ cons ( false , cons ( true , BList )) ⇒ cons ( false , cons ( true , nil )).

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

Если L ₁ , L ₂ и регулярные языки дерева, то множества деревьев L ₁ ∩ L ₂ , L ₁ ∪ L ₂ и L ₁ \ L ₂ также регулярные языки дерева, и она разрешима ли L ₁ ⊆ L ₂ , и является ли L ₁ = L ₂ .

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

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

Приложения

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

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

Смотрите также

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

использованная литература

^ "Регулярные древовидные грамматики как формализм для недостаточной спецификации области". CiteSeerX 10.1.1.164.5484 . Цитировать журнал требует |journal=( помощь )
^ Комон, Хьюберт; Дауше, Макс; Гиллерон, Реми; Лёдинг, Кристоф; Жакемар, Флоран; Лужие, Денис; Тисон, Софи; Томмази, Марк (12 октября 2007 г.). «Методы и приложения древовидных автоматов» . Проверено 25 января +2016 .
^ Alur, R .; Мадхусудан, П. (2004). «Языки с явным раскрытием» (PDF) . Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '04 . С. 202–211. DOI : 10.1145 / 1007352.1007390 . ISBN 978-1581138528. Раздел 4, теорема 5,
^ Alur, R .; Мадхусудан, П. (2009). «Добавление структуры вложенности к словам» (PDF) . Журнал ACM . 56 (3): 1–43. CiteSeerX 10.1.1.145.9971 . DOI : 10.1145 / 1516512.1516518 . Раздел 7
^ Emmelmann, Helmut (1991). «Выбор кода путем регулярно контролируемого переписывания терминов». Генерация кода - концепции, инструменты, методы . Семинары по вычислительной технике. Springer. С. 3–29.
Перейти ↑ Comon, Hubert (1990). "Формулы уравнений в упорядоченных алгебрах". Proc. ИКАЛП .
^ Gilleron, R .; Tison, S .; Томмази, М. (1993). «Решение систем заданных ограничений с использованием древовидных автоматов». 10-й ежегодный симпозиум по теоретическим аспектам информатики . LNCS. 665 . Springer. С. 505–514.
^ Бургхардт, Йохен (2002). «Аксиоматизация конечных алгебр». Достижения в области искусственного интеллекта . LNAI. 2479 . Springer. С. 222–234. arXiv : 1403,7347 . Bibcode : 2014arXiv1403.7347B . ISBN 3-540-44185-9.
^ Зив-Ukelson, Смолы (2016). Алгоритмы поиска в сети регулярной древовидной грамматики и их применение для выявления паттернов вирусных инфекций человека . J. of Comp. Bio. [1]

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

Регулярные древовидные грамматики были описаны еще в 1968 году:
- Брейнерд, WS (1968). «Минимизация древовидных автоматов» . Информация и контроль . 13 (5): 484–491. DOI : 10.1016 / s0019-9958 (68) 90917-0 .
- Тэтчер, JW; Райт, JB (1968). «Обобщенная теория конечных автоматов с приложением к решающей задаче логики второго порядка». Математическая теория систем . 2 (1): 57–81. DOI : 10.1007 / BF01691346 .
Книга, посвященная грамматике деревьев: Ниват, Морис; Подельски, Андреас (1992). Древовидные автоматы и языки . Исследования в области компьютерных наук и искусственного интеллекта. 10 . Северная Голландия.
Алгоритмы на регулярных древовидных грамматиках обсуждаются с точки зрения эффективности в: Aiken, A .; Мерфи, Б. (1991). «Реализация регулярных древовидных выражений». Конференция ACM по языкам функционального программирования и компьютерной архитектуре . С. 427–447. CiteSeerX 10.1.1.39.3766 .
Учитывая отображение деревьев в веса, обобщение Дональда Кнута алгоритма кратчайшего пути Дейкстры может быть применено к грамматике регулярных деревьев для вычисления для каждого нетерминала минимального веса выводимого дерева. Основываясь на этой информации, легко перечислить его язык в порядке возрастания веса. В частности, любой нетерминал с бесконечным минимальным весом порождает пустой язык. См .: Knuth, DE (1977). «Обобщение алгоритма Дейкстры». Письма об обработке информации . 6 (1): 1–5. DOI : 10.1016 / 0020-0190 (77) 90002-3 .
Обычные древовидные автоматы были обобщены, чтобы допускать проверки на равенство между родственными узлами в деревьях. См .: Bogaert, B .; Тисон, Софи (1992). «Ограничения равенства и неравенства для прямых подпунктов в древовидных автоматах». Proc. 9-й СТАНДАРТ . LNCS. 577 . Springer. С. 161–172.
Разрешение проверки равенства между более глубокими узлами приводит к неразрешимости. См .: Tommasi, M. (1991). Automates d'Arbres avec Tests d'Egalités entre Cousins Germains . LIFL-IT.

[1] "Регулярные древовидные грамматики как формализм для недостаточной спецификации области". CiteSeerX 10.1.1.164.5484 . Цитировать журнал требует |journal=( помощь )

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

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

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

[5] Emmelmann, Helmut (1991). «Выбор кода путем регулярно контролируемого переписывания терминов». Генерация кода - концепции, инструменты, методы . Семинары по вычислительной технике. Springer. С. 3–29.

[6] Перейти ↑ Comon, Hubert (1990). "Формулы уравнений в упорядоченных алгебрах". Proc. ИКАЛП .

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

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

[9] Зив-Ukelson, Смолы (2016). Алгоритмы поиска в сети регулярной древовидной грамматики и их применение для выявления паттернов вирусных инфекций человека . J. of Comp. Bio. [1]

[1]