Переписывание графа - Graph rewriting

В информатике , преобразования графа , или графа переписывания , относится метод создания нового графа из оригинального графика алгоритмически. Он имеет множество приложений, от разработки программного обеспечения ( создание программного обеспечения, а также его проверка ) до алгоритмов компоновки и создания изображений.

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

Формально система перезаписи графа обычно состоит из набора правил перезаписи графа формы , которые называются графом шаблонов (или левой частью) и называются графом замены (или правой частью правила). Правило перезаписи графа применяется к главному графу путем поиска вхождения графа шаблона ( сопоставление с образцом , таким образом решая проблему изоморфизма подграфа ) и путем замены найденного вхождения экземпляром графа замены. Правила перезаписи можно дополнительно регулировать в случае помеченных графов , например, в грамматиках графов с строковым регулированием. ${\ Displaystyle L \ rightarrow R}$${\ displaystyle L}$${\ displaystyle R}$

Иногда грамматика графов используется как синоним системы переписывания графов , особенно в контексте формальных языков ; другая формулировка используется, чтобы подчеркнуть цель построения, такую ​​как перечисление всех графов из некоторого начального графа, то есть создание языка графов - вместо простого преобразования данного состояния (основного графа) в новое состояние.

Подходы к переписыванию графов

Вверху: Пример правила перезаписи графа ( оптимизация на основе конструкции компилятора: умножение на 2 заменено сложением). Внизу: применение правила для оптимизации «y = x * 2» в «y = x + x».

Алгебраический подход

Алгебраический подход к переписыванию графов основан на теории категорий . Алгебраический подход делится на суб-подходы, наиболее распространенным из которых являются дважды Кодекартов Квадрат (ДПО) подход и одношаговый подход Кодекартов Квадрат (СПО) . Другие суб-подходы включают сескви--Кодекартов Квадрат и откат подхода .

С точки зрения подхода ДПО график переписывания правило пара морфизмов в категории графов и гомоморфизмов графов между ними: также написано , где это инъективны . Граф K называется инвариантным или иногда графом склейки . Перезаписи шаг или приложения из правила г на хост граф G определяется два Кодекартовых Квадрат диаграмм и возникающих в том же морфизме , где D представляет собой контекст , график (это где имя двойной -pushout происходит от). Другой морфизм графа моделирует вхождение L в G и называется совпадением . Практическое понимание этого состоит в том, что это подграф, который сопоставляется (см. Проблему изоморфизма подграфа ), и после того, как совпадение найдено, заменяется на в графе хоста, где служит интерфейсом, содержащим узлы и ребра, которые сохраняются при применении правило. Граф необходим для присоединения сопоставляемого шаблона к его контексту: если он пуст, сопоставление может обозначать только весь связанный компонент графа . ${\ Displaystyle г = (L \ leftarrow K \ rightarrow R)}$${\ Displaystyle L \ supseteq K \ substeq R}$${\ displaystyle K \ rightarrow L}$ ${\ Displaystyle к \ двоеточие K \ rightarrow D}$${\ Displaystyle м \ двоеточие L \ rightarrow G}$${\ displaystyle L}$${\ displaystyle G}$${\ displaystyle L}$${\ displaystyle R}$${\ displaystyle G}$${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle G}$

В противоположность этому график правило перезаписи от SPO подхода является один морфизм в категории меченых мультиграфов и частичных отображений , сохраняющих структуру мультиграф: . Таким образом, шаг перезаписи определяется одной диаграммой выталкивания . Практическое понимание этого аналогично подходу DPO. Разница в том, что между графом хоста G и графом G ', являющимся результатом этапа перезаписи, нет интерфейса. ${\ displaystyle r \ двоеточие L \ rightarrow R}$

С практической точки зрения, ключевое различие между DPO и SPO заключается в том, как они справляются с удалением узлов со смежными ребрами, в частности, как они избегают того, что такие удаления могут оставлять "болтающиеся края". Подход DPO удаляет узел только тогда, когда правило также определяет удаление всех смежных ребер (это состояние зависания можно проверить для данного совпадения), тогда как подход SPO просто удаляет смежные ребра, не требуя явной спецификации.

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

Детерминированная перезапись графа

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

Переписывание срочного графа

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

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

Конференция TERMGRAPH полностью посвящена исследованиям переписывания графов терминов и его приложений.

Классы грамматики графов и системы переписывания графов

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

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

Реализации и приложения

Графы - это выразительный, наглядный и математически точный формализм для моделирования объектов (сущностей), связанных отношениями; объекты представлены узлами, а отношения между ними - ребрами. Узлы и ребра обычно типизируются и приписываются. Вычисления в этой модели описываются изменениями отношений между объектами или изменениями атрибутов элементов графа. Они закодированы в правилах перезаписи графов / преобразования графов и выполняются системами перезаписи графов / инструментами преобразования графов.

• Инструменты, не зависящие от предметной области приложения:
  • AGG , система грамматики графов с атрибутами ( Java )
  • GP (Graph Programs) - это язык программирования для вычислений на графах путем направленного применения правил преобразования графов.
  • GMTE , механизм сопоставления и преобразования графов для сопоставления и преобразования графов . Это реализация расширения алгоритма Мессмера с использованием C ++ .
  • GrGen.NET , генератор перезаписи графов, инструмент преобразования графов, генерирующий C # -код или .NET-сборки
  • GROOVE , набор инструментов на основе Java для редактирования графов и правил преобразования графов, изучения пространств состояний грамматик графов и проверки моделей этих пространств состояний; также может использоваться как механизм преобразования графов.
  • Verigraph , система спецификации и проверки программного обеспечения, основанная на переписывании графов ( Haskell ).
• Инструменты, решающие задачи программной инженерии (в основном MDA ) с перезаписью графов:
  • eMoflon , EMF-совместимый инструмент преобразования моделей с поддержкой сюжетного моделирования и грамматик Triple Graph.
  • EMorF - система перезаписи графов на основе EMF , поддерживающая преобразование на месте и преобразование модели в модель.
  • Fujaba использует моделирование на основе историй, язык перезаписи графов, основанный на PROGRES.
  • Базы данных графиков часто поддерживают динамическую перезапись графиков.
  • Большой
  • Gremlin , язык программирования на основе графов (см. Переписывание графов )
  • Henshin , система перезаписи графов на основе EMF , поддерживающая преобразование на месте и преобразование модели в модель , анализ критических пар и проверку моделей
  • PROGRES , интегрированная среда и язык очень высокого уровня для систем программирования программируемых графов
  • ВИАТРА
• Инструменты машиностроения
  • GraphSynth - это интерпретатор и среда пользовательского интерфейса для создания неограниченных грамматик графов, а также для тестирования и поиска результирующего языкового варианта. Он сохраняет графики и правила грамматики графиков в виде файлов XML и написан на C # .
  • Soley Studio - это интегрированная среда разработки для систем преобразования графов. Его основная сфера применения - аналитика данных в области инженерии.
• Приложения в биологии
  • Функционально-структурное моделирование объектов с помощью языка, основанного на грамматике графов
  • Моделирование многоклеточной разработки с помощью грамматик графов, регулируемых строками
• Искусственный интеллект / обработка естественного языка
  • OpenCog предоставляет базовый сопоставитель шаблонов (на гиперграфах ), который используется для реализации различных алгоритмов искусственного интеллекта.
  • РЕЛЭКС является английским языком анализатором , который использует график переписывание преобразовать ссылку разобрана в разбор зависимостей .

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

• Теория категорий
• Теория графов
• Грамматика формы
• Формальная грамматика
• График сроков

Рекомендации

Цитаты

Источники