Reescritura de grafos de doble empuje

En informática , la reescritura de grafos de doble empuje (o reescritura de grafos DPO) se refiere a un marco matemático para la reescritura de grafos . Fue introducida como uno de los primeros enfoques algebraicos para la reescritura de grafos en el artículo "Graph-grammars: An algebraic approach" (1973). ^{[ 1 ]} Desde entonces, se ha generalizado para permitir la reescritura de estructuras que no son grafos y para manejar condiciones de aplicación negativas, ^{[ 2 ]} entre otras extensiones.

Un sistema de transformación de grafos DPO (o gramática de grafos ) consta de un grafo finito , que es el estado inicial, y un conjunto finito o numerable de extensiones etiquetadas en la categoría de grafos finitos y homomorfismos de grafos , que sirven como reglas de derivación. Generalmente se considera que las extensiones de las reglas están compuestas de monomorfismos , pero los detalles pueden variar. ^{[ 3 ]}

La reescritura se realiza en dos pasos: eliminación y adición.

Después de un partido desde el lado izquierdo a${\displaystyle G}$Una vez corregido, se eliminan los nodos y aristas que no se encuentran en el lado derecho. A continuación, se añade el lado derecho.

De hecho, pegar grafos es una construcción de empuje dentro de la categoría de grafos, y la eliminación es lo mismo que encontrar un complemento de empuje, de ahí su nombre.

La reescritura de grafos de doble empuje permite especificar transformaciones de grafos al especificar un patrón de tamaño y composición fijos que se debe encontrar y reemplazar, donde parte del patrón se puede conservar. La aplicación de una regla es potencialmente no determinista: pueden ser posibles varias coincidencias distintas. Estas pueden no superponerse o compartir solo elementos conservados, mostrando así un tipo de concurrencia conocida como independencia paralela, ^{[ 4 ]} o pueden ser incompatibles, en cuyo caso las aplicaciones a veces se pueden ejecutar secuencialmente, o incluso una puede excluir a la otra.

Puede utilizarse como lenguaje para el diseño y la programación de software (normalmente se elige una variante que trabaja con estructuras más complejas que los grafos). La terminación para la reescritura de grafos DPO es indecidible porque el problema de correspondencia de Post se puede reducir a ella. ^{[ 5 ]}

La reescritura de grafos DPO puede considerarse una generalización de las redes de Petri . ^{[ 4 ]}

Se han buscado axiomas para describir categorías en las que la reescritura DPO funcionará. Una posibilidad es la noción de una categoría adhesiva , que también goza de muchas propiedades de cierre. Nociones relacionadas son los sistemas HLR, las categorías cuasi adhesivas y${\displaystyle {\mathcal {M}}}$-categorías de adhesivos, categorías HLR de adhesivos. ^{[ 6 ]}

Los conceptos de categoría de adhesivo y sistema HLR están relacionados (una categoría de adhesivo con coproductos es un sistema HLR ^{[ 7 ]} ).

Los hipergrafos , los grafos tipados y la reescritura de grafos con atributos , ^{[ 8 ]} por ejemplo, se pueden manejar porque se pueden representar como sistemas HLR adhesivos.

• Reescritura de grafos de empuje único