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

Алгебраический подход к переписыванию графов основан на теории категории. Алгебраический подход подразделяется на субподходы, наиболее распространенными из которых являются подход double-pushout (DPO) и подход single-pushout (SPO). Другие подходы включают sesqui-pushout и pullback.

С точки зрения подхода DPO правило переписывания графа это пара морфизмов в категории графов и гомоморфизмы графа между ними: ${\displaystyle r=(L\leftarrow K\rightarrow R)}$ (или ${\displaystyle L\supseteq K\subseteq R}$), где ${\displaystyle K\rightarrow L}$ инъективно. Граф ${\displaystyle K}$ называется инвариантным или иногда склеивающим графом. Шаг переписывания или применение правила ${\displaystyle r}$ к исходному графу ${\displaystyle G}$ определяется двумя диаграммами кодекартова квадрата, обе ведущими в один и тот же морфизм ${\displaystyle k\colon K\rightarrow D}$, где ${\displaystyle D}$ это контекстный граф (откуда и происходит название double-pushout). Другой морфизм графа ${\displaystyle m\colon L\rightarrow G}$ моделирует вхождение ${\displaystyle L}$ в ${\displaystyle G}$ и называется сопоставлением. Практическим пониманием этого является то, что ${\displaystyle L}$ является подграфом, который сопоставляется из ${\displaystyle G}$ (смотри задачу поиска изоморфного подграфа), и после того, как совпадение найдено, ${\displaystyle L}$ заменяется на ${\displaystyle R}$ в исходном графе ${\displaystyle G}$, где ${\displaystyle K}$ служит интерфейсом, содержащим узлы и рёбра, которые при применении правила были сохранены. Граф ${\displaystyle K}$ необходим для того, чтобы присоединить образец, сопоставляющийся его контексту: если он пуст, совпадение может обозначать только весь связанный компонент графа ${\displaystyle G}$.

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

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

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

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

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

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

Конференция TERMGRAPH[3] полностью фокусируется на исследованиях в области АСГ и их приложениях.