Переписывание графика двойного выталкивания

В информатике ( переписывание графа с двойным выталкиванием или переписывание графа DPO) относится к математической основе для переписывания графа . Он был представлен как один из первых алгебраических подходов к переписыванию графов в статье «Граф-грамматики: алгебраический подход» (1973). ^[1] С тех пор он был обобщен, чтобы позволить перезаписывать структуры, которые не являются графами, и обрабатывать негативные условия применения. ^[2] среди других расширений.

Определение

Система преобразования графов DPO (или грамматика графов ) состоит из конечного графа , который является начальным состоянием, и конечного или счетного набора помеченных промежутков в категории конечных графов и гомоморфизмов графов, которые служат правилами вывода. Обычно считается, что диапазоны правил состоят из мономорфизмов , но детали могут различаться. ^[3]

Перезапись выполняется в два этапа: удаление и добавление.

После матча с левого фланга на $G$ фиксировано, узлы и ребра, находящиеся не в правой части, удаляются. Затем приклеивается правая сторона.

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

Использование

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

Его можно использовать в качестве языка для проектирования и программирования программного обеспечения (обычно выбирается вариант, работающий с более богатыми структурами, чем графы). Завершение перезаписи графа DPO неразрешимо , поскольку задача соответствия Поста . к нему сводится ^[5]

Переписывание графа DPO можно рассматривать как обобщение сетей Петри . ^[4]

Обобщение

Были найдены аксиомы для описания категорий, в которых будет работать переписывание DPO. Одной из возможностей является понятие категории клея , которая также обладает многими закрывающими свойствами. Связанными понятиями являются системы HLR, категории квазиадгезивов и ${\mathcal {M}}$ -категории клея, категории клея HLR. ^[6]

Понятия категории клея и системы HLR связаны (категория клея с сопутствующими продуктами представляет собой систему HLR). ^[7]).

Гиперграф , типизированный граф и переписывание атрибутивного графа , ^[8] например, с ними можно обращаться, поскольку их можно отливать в виде клейких систем HLR.

Примечания

^ Хартмут Эриг; Майкл Пфендер; Ханс-Юрген Шнайдер (октябрь 1973 г.). «Граф-грамматики: алгебраический подход» . Протокол конференции IEEE 14-го ежегодного симпозиума по теории коммутации и автоматов (SWAT'08) . IEEE. стр. 167–180. дои : 10.1109/SWAT.1973.11 .
^ Хартмут Эриг; Карстен Эриг; Аннегрет Хабель; Карл-Хайнц Пеннеманн (2004). «Ограничения и условия применения: от графов к структурам высокого уровня» . В Эриге Х.; Энгельс Г.; Паризи-Пресичче Ф.; Розенберг Г. (ред.). Преобразования графа . Конспекты лекций по информатике. Том. 3256. Спрингер. стр. 287–303. дои : 10.1007/978-3-540-30203-2_21 . ISBN 978-3-540-23207-0 .
^ «Возвращение к преобразованию графа с двойным выталкиванием», Хабель, Аннегрет и Мюллер, Юрген и Пламп, Детлеф, Математические структуры в информатике, том. 11, нет. 05., стр. 637–688, 2001, издательство Кембриджского университета.
^ Перейти обратно: ^а ^б «Параллельные вычисления: от сетей Петри к графовым грамматикам», Коррадини, Андреа, ENTCS, том. 2, стр. 56–70, 1995, Elsevier.
^ , «Прекращение перезаписи графа неразрешимо», Детлеф Пламп, Fundamenta Informaticae, vol. 33, нет. 2, стр. 201–209, 1998, IOS Press.
^ Хартмут Эриг и Аннегрет Хабель, Джулия Падберг и Ульрике Пранге, «Категории и системы замены клея высокого уровня», 2004, Springer
^ «Адгезивные категории», Стивен Лак и Павел Собоциньский, в «Основах науки о программном обеспечении и вычислительных структурах» , стр. 273–288, Springer 2004.
^ «Основы преобразования алгебраических графов», Хартмут Эриг, Карстен Эриг, Ульрике Пранге и Габриэле Тенцер

[ehrig73-1] Хартмут Эриг; Майкл Пфендер; Ханс-Юрген Шнайдер (октябрь 1973 г.). «Граф-грамматики: алгебраический подход» . Протокол конференции IEEE 14-го ежегодного симпозиума по теории коммутации и автоматов (SWAT'08) . IEEE. стр. 167–180. дои : 10.1109/SWAT.1973.11 .

[ehrig2-2] Хартмут Эриг; Карстен Эриг; Аннегрет Хабель; Карл-Хайнц Пеннеманн (2004). «Ограничения и условия применения: от графов к структурам высокого уровня» . В Эриге Х.; Энгельс Г.; Паризи-Пресичче Ф.; Розенберг Г. (ред.). Преобразования графа . Конспекты лекций по информатике. Том. 3256. Спрингер. стр. 287–303. дои : 10.1007/978-3-540-30203-2_21 . ISBN 978-3-540-23207-0 .

[habel01-3] «Возвращение к преобразованию графа с двойным выталкиванием», Хабель, Аннегрет и Мюллер, Юрген и Пламп, Детлеф, Математические структуры в информатике, том. 11, нет. 05., стр. 637–688, 2001, издательство Кембриджского университета.

[corradini-4] Перейти обратно: ^а ^б «Параллельные вычисления: от сетей Петри к графовым грамматикам», Коррадини, Андреа, ENTCS, том. 2, стр. 56–70, 1995, Elsevier.

[plump1998termination-5] , «Прекращение перезаписи графа неразрешимо», Детлеф Пламп, Fundamenta Informaticae, vol. 33, нет. 2, стр. 201–209, 1998, IOS Press.

[ahlr-6] Хартмут Эриг и Аннегрет Хабель, Джулия Падберг и Ульрике Пранге, «Категории и системы замены клея высокого уровня», 2004, Springer

[Lack-7] «Адгезивные категории», Стивен Лак и Павел Собоциньский, в «Основах науки о программном обеспечении и вычислительных структурах» , стр. 273–288, Springer 2004.

[8] «Основы преобразования алгебраических графов», Хартмут Эриг, Карстен Эриг, Ульрике Пранге и Габриэле Тенцер

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]