En informática , la transformación de gráficos o reescritura de gráficos se refiere a la técnica de crear algorítmicamente un nuevo gráfico a partir de un gráfico original. Tiene numerosas aplicaciones, que van desde la ingeniería de software ( construcción de software y también verificación de software ) hasta algoritmos de diseño y generación de imágenes.
Las transformaciones de gráficos se pueden utilizar como abstracción de cálculo. La idea básica es que si el estado de un cálculo se puede representar como un gráfico, los pasos posteriores de ese cálculo se pueden representar como reglas de transformación en ese gráfico. Dichas reglas consisten en un gráfico original, que debe coincidir con un subgrafo en el estado completo, y un gráfico de reemplazo, que reemplazará al subgrafo coincidente.
Formalmente, un sistema de reescritura de gráficos generalmente consta de un conjunto de reglas de reescritura de gráficos de la forma , que se denomina gráfico de patrón (o lado izquierdo) y gráfico de reemplazo (o lado derecho de la regla). Se aplica una regla de reescritura de gráfico al gráfico anfitrión buscando una ocurrencia del gráfico de patrón ( coincidencia de patrones , resolviendo así el problema de isomorfismo del subgrafo ) y reemplazando la ocurrencia encontrada por una instancia del gráfico de reemplazo. Las reglas de reescritura se pueden regular aún más en el caso de gráficos etiquetados , como en las gramáticas de gráficos reguladas por cadenas.
A veces, la gramática gráfica se utiliza como sinónimo de sistema de reescritura de gráficos , especialmente en el contexto de lenguajes formales ; la redacción diferente se utiliza para enfatizar el objetivo de las construcciones, como la enumeración de todos los gráficos a partir de algún gráfico inicial, es decir, la generación de un lenguaje de gráficos, en lugar de simplemente transformar un estado dado (gráfico anfitrión) en un nuevo estado.
El enfoque algebraico para la reescritura de gráficos se basa en la teoría de categorías . El enfoque algebraico se divide a su vez en subenfoques, los más comunes de los cuales son el enfoque de doble expulsión (DPO) y el enfoque de expulsión única (SPO) . Otros subenfoques incluyen el enfoque sesqui-pushout y el de retroceso .
Desde la perspectiva del enfoque DPO, una regla de reescritura de gráficos es un par de morfismos en la categoría de gráficos y homomorfismos de gráficos entre ellos: , también escrito , donde es inyectivo . El gráfico K se llama invariante o, a veces, gráfico de pegado . Un paso de reescritura o aplicación de una regla r a un gráfico anfitrión G se define mediante dos diagramas de expulsión , ambos originados en el mismo morfismo , donde D es un gráfico de contexto (de aquí proviene el nombre de doble expulsión). Otro morfismo gráfico modela una aparición de L en G y se llama coincidencia . La comprensión práctica de esto es que es un subgrafo que coincide (consulte el problema de isomorfismo del subgrafo ) y, después de encontrar una coincidencia, se reemplaza por el grafo anfitrión , donde sirve como interfaz, que contiene los nodos y bordes que se conservan al aplicar el regla. El gráfico es necesario para vincular el patrón que se está comparando con su contexto: si está vacío, la coincidencia solo puede designar un componente completo y conectado del gráfico .
En contraste, una regla de reescritura de gráficos del enfoque SPO es un morfismo único en la categoría de multigrafos etiquetados y mapeos parciales que preservan la estructura del multigrafo: . Por lo tanto, un paso de reescritura se define mediante un único diagrama de extracción . La comprensión práctica de esto es similar al enfoque DPO. La diferencia es que no existe una interfaz entre el gráfico anfitrión G y el gráfico G' que es el resultado del paso de reescritura.
Desde la perspectiva práctica, la distinción clave entre DPO y SPO es cómo abordan la eliminación de nodos con bordes adyacentes, en particular, cómo evitan que dichas eliminaciones dejen "bordes colgantes". El enfoque DPO solo elimina un nodo cuando la regla especifica la eliminación también de todos los bordes adyacentes (esta condición pendiente se puede verificar para una coincidencia determinada), mientras que el enfoque SPO simplemente elimina los bordes adyacentes, sin requerir una especificación explícita.
También existe otro enfoque de tipo algebraico para la reescritura de gráficos, basado principalmente en el álgebra booleana y un álgebra de matrices, llamado gramáticas de gráficos matriciales . [1]
Otro enfoque más para la reescritura de gráficos, conocido como reescritura de gráficos determinados , surgió de la lógica y la teoría de las bases de datos . [2] En este enfoque, los gráficos se tratan como instancias de bases de datos y las operaciones de reescritura como un mecanismo para definir consultas y vistas; por lo tanto, se requiere que toda reescritura produzca resultados únicos ( hasta el isomorfismo ), y esto se logra aplicando cualquier regla de reescritura simultáneamente en todo el gráfico, dondequiera que se aplique, de tal manera que el resultado esté efectivamente definido de manera única.
Otro enfoque para la reescritura de gráficos es la reescritura de gráficos de términos , que implica el procesamiento o transformación de gráficos de términos (también conocidos como gráficos semánticos abstractos ) mediante un conjunto de reglas de reescritura sintáctica.
Los gráficos de términos son un tema destacado en la investigación de lenguajes de programación, ya que las reglas de reescritura de gráficos de términos son capaces de expresar formalmente la semántica operativa de un compilador . Los gráficos de términos también se utilizan como máquinas abstractas capaces de modelar cálculos químicos y biológicos, así como cálculos gráficos como modelos de concurrencia. Los gráficos de términos pueden realizar verificación automatizada y programación lógica, ya que son adecuados para representar declaraciones cuantificadas en lógica de primer orden. El software de programación simbólica es otra aplicación para gráficos de términos, que son capaces de representar y realizar cálculos con estructuras algebraicas abstractas como grupos, campos y anillos.
La conferencia TERMGRAPH [3] se centra exclusivamente en la investigación sobre la reescritura de gráficos de términos y sus aplicaciones.
Los sistemas de reescritura de gráficos se agrupan naturalmente en clases según el tipo de representación de gráficos que se utilizan y cómo se expresan las reescrituras. El término gramática de gráficos, equivalente a sistema de reescritura de gráficos o sistema de reemplazo de gráficos, se utiliza con mayor frecuencia en las clasificaciones. Algunos tipos comunes son:
Los gráficos son un formalismo expresivo, visual y matemáticamente preciso para modelar objetos (entidades) vinculados por relaciones; los objetos están representados por nodos y las relaciones entre ellos por aristas. Los nodos y aristas se tipifican y atribuyen comúnmente. Los cálculos se describen en este modelo mediante cambios en las relaciones entre las entidades o mediante cambios de atributos de los elementos del gráfico. Están codificados en reglas de reescritura de gráficos/transformación de gráficos y ejecutados mediante sistemas de reescritura de gráficos/herramientas de transformación de gráficos.
