Reescritura de gráfico de doble expulsión
En informática , la reescritura de gráficos de doble extracción (o reescritura de gráficos DPO) se refiere a un marco matemático para la reescritura de gráficos . Se introdujo como uno de los primeros enfoques algebraicos para la reescritura de gráficos 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 gráficos y para manejar condiciones de aplicación negativas, [2] entre otras extensiones.
Un sistema de transformación de gráficos DPO (o gramática de gráficos ) consta de un gráfico finito , que es el estado inicial, y un conjunto finito o contable de tramos etiquetados en la categoría de gráficos finitos y homomorfismos de gráficos, que sirven como reglas de derivación. Generalmente se considera que los intervalos de reglas están compuestos de monomorfismos , pero los detalles pueden variar. [3]
Después de corregir una coincidencia del lado izquierdo a , los nodos y los bordes que no están en el lado derecho se eliminan. Luego se pega el lado derecho.
Pegar gráficos es, de hecho, una construcción de extracción en la categoría de gráficos, y la eliminación es lo mismo que encontrar un complemento de extracción, de ahí el nombre.
La reescritura de gráficos de extracción doble permite la especificación de transformaciones de gráficos al especificar un patrón de tamaño y composición fijos para 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. Estos pueden no superponerse o compartir solo elementos preservados, 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 se puede excluir el otro.
Se puede usar como lenguaje para el diseño y la programación de software (generalmente se elige una variante que funcione en estructuras más ricas que los gráficos). La terminación para la reescritura del gráfico DPO es indecidible porque el problema de la correspondencia posterior se puede reducir a ella. [5]