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

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

Определение

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

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

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

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

Использует

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

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

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

Обобщение

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

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

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

Примечания

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