Reescritura de gráficos de doble expulsión
En informática , la reescritura de gráficos de doble expulsió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 "Graficas-gramáticas: un enfoque algebraico" (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 ) consiste en un gráfico finito , que es el estado inicial, y un conjunto finito o contable de intervalos etiquetados en la categoría de gráficos finitos y homomorfismos de gráficos, que sirven como reglas de derivación. Por lo general, se considera que los intervalos de reglas están compuestos por monomorfismos , pero los detalles pueden variar. [3]
Después de arreglar una coincidencia del lado izquierdo con , se eliminan los nodos y los bordes que no están en el lado derecho. Luego se pega el lado derecho.
Pegar gráficos es, de hecho, una construcción de expulsión en la categoría de gráficos, y la eliminación es lo mismo que encontrar un complemento de expulsión, de ahí el nombre.
La reescritura de gráficos de doble expulsión permite la especificación de transformaciones de gráficos al especificar un patrón de tamaño y composición fijos que se encuentra y se reemplaza, donde se puede conservar parte del patrón. La aplicación de una regla es potencialmente no determinista: pueden ser posibles varias coincidencias distintas. Estos pueden ser no superpuestos, o compartir solo elementos preservados, mostrando así un tipo de simultaneidad 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 utilizar como lenguaje para el diseño y la programación de software (normalmente se elige una variante que trabaje en estructuras más ricas que los gráficos). La terminación para la reescritura de gráficos DPO es indecidible porque el problema de correspondencia posterior se puede reducir a eso. [5]