Переписывание графика двойного выталкивания - Double pushout graph rewriting

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

Определение

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

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

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

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

Использует

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

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

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

Обобщение

Аксиомы пытались описать категории, в которых будет работать перезапись DPO. Одна из возможностей - это понятие категория клея, который также обладает многими закрывающими свойствами. Связанные понятия: системы HLR, квазиадгезивные категории и -клеевые категории, клейкие HLR-категории.[6]

Концепции категория клея и система HLR связаны (категория клея с побочные продукты это система HLR[7]).

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

Примечания

  1. ^ «Граф-грамматики: алгебраический подход», Эриг, Хартмут и Пфендер, Михаэль и Шнайдер, Ханс-Юрген, теория переключений и автоматов, 1973. SWAT'08. Отчет конференции IEEE о 14-м ежегодном симпозиуме, стр. 167-180, 1973, IEEE
  2. ^ "Ограничения и условия применения: от графов к структурам высокого уровня", Эриг, Эриг, Хабель и Пеннеманн, Преобразования графов, стр. 287-303, Springer
  3. ^ «Повторение преобразования графа с двойным выталкиванием», Хабель, Аннегрет и Мюллер, Юрген и Пламп, Детлеф, Математические структуры в компьютерных науках, вып. 11, вып. 05. С. 637--688, 2001, Cambridge University Press.
  4. ^ а б «Параллельные вычисления: от сетей Петри до грамматик графов», Коррадини, Андреа, ENTCS, т. 2. С. 56--70, 1995, Elsevier.
  5. ^ , «Прекращение перезаписи графа неразрешимо», Детлеф Пламп, Fundamenta Informaticae, т. 33, нет. 2. С. 201--209, 1998, IOS Press.
  6. ^ Хартмут Эриг и Аннегрет Хабель, Джулия Падберг и Ульрике Прейндж, "Адгезивные категории и системы замены высокого уровня", 2004, Springer
  7. ^ «Клейкие категории», Стивен Лак и Павел Собочиньски, в Основы программной науки и вычислительные структурыС. 273--288, Springer 2004.
  8. ^ «Основы преобразования алгебраических графов», Хартмут Эриг, Карстен Эриг, Ульрике Прейндж и Габриэле Тэнцер