Reescritura de grafos

En informática , la transformación o reescritura de grafos se refiere a la técnica de crear un nuevo grafo a partir de uno original mediante un algoritmo. Tiene numerosas aplicaciones, que van desde la ingeniería de software ( construcción y verificación de software ) hasta algoritmos de diseño y generación de imágenes.

Las transformaciones de grafos pueden utilizarse como una abstracción computacional. La idea básica es que, si el estado de un cálculo puede representarse como un grafo, los pasos posteriores de dicho cálculo pueden representarse como reglas de transformación sobre ese grafo. Estas reglas constan de un grafo original, que se corresponde con un subgrafo en el estado completo, y un grafo de reemplazo, que sustituirá al subgrafo correspondiente.

Formalmente, un sistema de reescritura de grafos generalmente consiste en un conjunto de reglas de reescritura de grafos de la forma $L\rightarrow R$ , con $L$ ser llamado gráfico de patrones (o lado izquierdo) y $R$ Se denomina grafo de reemplazo (o lado derecho de la regla). Una regla de reescritura de grafos se aplica al grafo anfitrión buscando una ocurrencia del grafo patrón ( coincidencia de patrones , resolviendo así el problema del isomorfismo de subgrafos ) y reemplazando la ocurrencia encontrada por una instancia del grafo de reemplazo. Las reglas de reescritura pueden regularse aún más en el caso de grafos etiquetados , como en las gramáticas de grafos reguladas por cadenas.

A veces, la gramática de grafos se usa como sinónimo de sistema de reescritura de grafos , especialmente en el contexto de los lenguajes formales ; la diferente terminología se usa para enfatizar el objetivo de las construcciones, como la enumeración de todos los grafos a partir de un grafo inicial, es decir, la generación de un lenguaje de grafos, en lugar de simplemente transformar un estado dado (grafo anfitrión) en un nuevo estado.

Enfoques de reescritura de grafos

Enfoque algebraico

El enfoque algebraico para la reescritura de grafos se basa en la teoría de categorías . Este enfoque se divide a su vez en subenfoques, siendo los más comunes el enfoque de doble empuje (DPO) y el enfoque de empuje simple (SPO) . Otros subenfoques incluyen el enfoque de sesquiempuje y el enfoque de retroceso .

Desde la perspectiva del enfoque DPO, una regla de reescritura de grafos es un par de morfismos en la categoría de grafos y homomorfismos de grafos entre ellos: $r=(L\leftarrow K\rightarrow R)$ , también escrito $L\supseteq K\subseteq R$ , dónde $K\rightarrow L$ es inyectivo . El grafo K se llama invariante o, a veces, grafo de pegado . Un paso de reescritura o aplicación de una regla r a un grafo anfitrión G se define mediante dos diagramas de empuje que se originan en el mismo morfismo. $k\colon K\rightarrow D$ , donde D es un grafo de contexto (de aquí proviene el nombre de doble empuje). Otro morfismo de grafos $m\colon L\rightarrow G$ modela una ocurrencia de L en G y se llama coincidencia . La comprensión práctica de esto es que $L$ es un subgrafo que coincide con $G$ (véase el problema del isomorfismo de subgrafos ), y después de que se encuentre una coincidencia, $L$ es reemplazado por $R$ en el gráfico del anfitrión $G$ dónde $K$ Sirve como interfaz, conteniendo los nodos y aristas que se conservan al aplicar la regla. El grafo $K$ Es necesario para adjuntar el patrón que se está comparando a su contexto: si está vacío, la coincidencia solo puede designar un componente conectado completo del grafo. $G$ .

En contraste, una regla de reescritura de grafos del enfoque SPO es un único morfismo en la categoría de multigrafos etiquetados y mapeos parciales que preservan la estructura del multigrafo: $r\colon L\rightarrow R$ Por lo tanto, un paso de reescritura se define mediante un único diagrama de empuje . Su comprensión práctica es similar al enfoque DPO. La diferencia radica en que no existe una interfaz entre el grafo anfitrión G y el grafo G' resultante del paso de reescritura.

Desde una perspectiva práctica, la principal diferencia entre DPO y SPO radica en cómo gestionan la eliminación de nodos con aristas adyacentes, en particular, cómo evitan que dichas eliminaciones dejen "aristas colgantes". El enfoque DPO solo elimina un nodo cuando la regla especifica también la eliminación de todas las aristas adyacentes (esta condición de aristas colgantes se puede verificar para una coincidencia determinada), mientras que el enfoque SPO simplemente elimina las aristas adyacentes, sin requerir una especificación explícita.

También existe otro enfoque de tipo algebraico para la reescritura de grafos, basado principalmente en el álgebra booleana y un álgebra de matrices, llamado gramáticas de grafos matriciales . ^{[ 1 ]}

Reescritura de grafos determinista

Otro enfoque para la reescritura de grafos, conocido como reescritura de grafos determinista , surgió de la lógica y la teoría de bases de datos . ^{[ 2 ]} En este enfoque, los grafos 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 ( salvo isomorfismo ), y esto se logra aplicando cualquier regla de reescritura concurrentemente en todo el grafo, dondequiera que se aplique, de tal manera que el resultado esté definido de manera única.

Reescritura de grafos de términos

Otro enfoque para la reescritura de grafos es la reescritura de grafos de términos , que implica el procesamiento o la transformación de grafos de términos (también conocidos como grafos semánticos abstractos ) mediante un conjunto de reglas de reescritura sintáctica.

Los grafos de términos son un tema destacado en la investigación de lenguajes de programación, ya que las reglas de reescritura de grafos de términos permiten expresar formalmente la semántica operacional de un compilador . 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 los modelos de concurrencia. Los grafos de términos pueden realizar verificación automatizada y programación lógica, dado que son idóneos para representar enunciados cuantificados en lógica de primer orden. El software de programación simbólica es otra aplicación de los grafos de términos, que permite representar y realizar cálculos con estructuras algebraicas abstractas como grupos, cuerpos y anillos.

La conferencia TERMGRAPH ^{[ 3 ]} se centra por completo en la investigación sobre la reescritura de grafos de términos y sus aplicaciones.

Clases de gramática de grafos y sistema de reescritura de grafos

Los sistemas de reescritura de grafos se agrupan naturalmente en clases según el tipo de representación de grafos que se utiliza y cómo se expresan las reescrituras. El término gramática de grafos, también equivalente a sistema de reescritura de grafos o sistema de reemplazo de grafos, es el que se usa con mayor frecuencia en las clasificaciones. Algunos tipos comunes son:

Las gramáticas de grafos con atributos , que normalmente se formalizan utilizando el enfoque de empuje simple o el enfoque de empuje doble para caracterizar las sustituciones, se mencionan en la sección anterior sobre el enfoque algebraico para la reescritura de grafos.
Las gramáticas de hipergrafos, incluidas como subclases más restrictivas, portan gramáticas de grafos , gramáticas de grafos lineales y redes de interacción .

Implementaciones y aplicaciones

Los grafos constituyen un formalismo expresivo, visual y matemáticamente preciso para modelar objetos (entidades) vinculados por relaciones. Los objetos se representan mediante nodos y las relaciones entre ellos mediante aristas. Los nodos y las aristas suelen tener tipos y atributos definidos. En este modelo, los cálculos se describen mediante cambios en las relaciones entre las entidades o mediante cambios en los atributos de los elementos del grafo. Estos cálculos se codifican en reglas de reescritura/transformación de grafos y se ejecutan mediante sistemas de reescritura/herramientas de transformación de grafos.

Herramientas que son independientes del dominio de aplicación:
- AGG , el sistema de gramática de grafos con atributos ( Java ).
- GP 2 es un lenguaje de programación gráfica visual basado en reglas, diseñado para facilitar el razonamiento formal sobre programas gráficos.
- GMTE se archivó el 13 de marzo de 2018 en Wayback Machine . Se trata del Motor de Transformación y Emparejamiento de Grafos . Es una implementación de una extensión del algoritmo de Messmer utilizando C++ .
- GrGen.NET , el generador de reescritura de grafos, es una herramienta de transformación de grafos que genera código C# o ensamblados .NET.
- GROOVE , un conjunto de herramientas basado en Java para editar gráficos y reglas de transformación de gráficos, explorar los espacios de estados de las gramáticas de gráficos y verificar modelos de esos espacios de estados, también puede utilizarse como motor de transformación de gráficos.
- Verigraph , un sistema de especificación y verificación de software basado en la reescritura de grafos ( Haskell ).
Herramientas que resuelven tareas de ingeniería de software (principalmente MDA ) con reescritura de grafos:
- eMoflon , una herramienta de transformación de modelos compatible con EMF que admite el modelado basado en historias y las gramáticas de grafos triples.
- EMorF es un sistema de reescritura de grafos basado en EMF , que admite la transformación in situ y de modelo a modelo .
- Fujaba utiliza el modelado basado en historias, un lenguaje de reescritura de grafos basado en PROGRES.
- Las bases de datos de grafos suelen admitir la reescritura dinámica de grafos.
- Excelente .
- Gremlin , un lenguaje de programación basado en grafos (véase Reescritura de grafos ).
- Henshin , un sistema de reescritura de grafos basado en EMF , que admite la transformación in situ y de modelo a modelo , el análisis de pares críticos y la verificación de modelos .
- PROGRES , un entorno integrado y un lenguaje de muy alto nivel para sistemas de reescritura de grafos programados.
- VIATRA .
Herramientas de ingeniería mecánica
- GraphSynth es un intérprete y un entorno de interfaz de usuario para crear gramáticas de grafos sin restricciones, así como para probar y buscar la variante de lenguaje resultante. Guarda los grafos y las reglas de la gramática de grafos como archivos XML y está escrito en C# .
- Soley Studio es un entorno de desarrollo integrado para sistemas de transformación de grafos. Su principal aplicación se centra en el análisis de datos en el campo de la ingeniería.
Aplicaciones de la biología
- Modelado funcional-estructural de plantas con un lenguaje basado en gramática de grafos.
- Modelado del desarrollo multicelular con gramáticas de grafos reguladas por cadenas
- Kappa es un lenguaje basado en reglas para modelar sistemas de agentes que interactúan entre sí, motivado principalmente por la biología de sistemas moleculares.
Inteligencia Artificial/Procesamiento del Lenguaje Natural
- OpenCog proporciona un comparador de patrones básico (en hipergrafos ) que se utiliza para implementar diversos algoritmos de IA.
- RelEx es un analizador sintáctico en inglés que emplea la reescritura de grafos para convertir un análisis de enlaces en un análisis de dependencias .
Lenguaje de programación informática
- El lenguaje de programación Clean se implementa mediante la reescritura de grafos.

Véase también

teoría de grafos
gramática de formas
Gramática formal
Reescritura abstracta : una generalización de la reescritura de grafos.

Referencias

Citas

↑ Pérez Velasco 2009 cubre este enfoque en detalle.
↑ "Un modelo de objetos orientado a grafos para interfaces de usuario final de bases de datos" (PDF) .
↑ "TERMGRAPH" .

Fuentes

Rozenberg, Grzegorz, ed. (1997), Handbook of Graph Grammars and Computing by Graph Transformations , vol. 1–3 , World Scientific Publishing, ISBN 9810228848Archivado del original el 4 de octubre de 2013 , consultado el 11 de julio de 2012..
Rozenberg, Grzegorz , ed. (febrero de 1997). Fundamentos . Manual de gramáticas de grafos y computación mediante transformación de grafos. Vol. 1. World Scientific. doi : 10.1142/3303 . ISBN 978-981-02-2884-2.
Pérez Velasco, Pedro Pablo (2009), Gramáticas de gráficos matriciales: un enfoque algebraico para la dinámica de gráficos , VDM Verlag , arXiv : 0801.1245 , ISBN 978-3-639-21255-6.
Heckel, R. (2006). Transformación de grafos en pocas palabras . Electronic Notes in Theoretical Computer Science 148 (1 SPEC. ISS.), pp. 187–198.
König, Barbara (2004). Análisis y verificación de sistemas con estructura dinámicamente evolutiva . Tesis de habilitación, Universidad de Stuttgart. Archivada el 25 de junio de 2007 en Wayback Machine , pp. 65–180.
Lobo, Daniel; Vico, Francisco J.; Dassow, Jürgen (1 de octubre de 2011). "Graph grammars with string-regulated rewriting" . Theoretical Computer Science . 412 (43): 6101– 6111. doi : 10.1016/j.tcs.2011.07.004 . hdl : 10630/6716 . ISSN 0304-3975 .
Hartmut Ehrig ; Gregor Engels; Hans-Jörg Kreowski ; Grzegorz Rozenberg, eds. (octubre de 1999). Aplicaciones, lenguajes y herramientas . Manual de gramáticas de grafos y computación mediante transformación de grafos. Vol. 2. World Scientific. doi : 10.1142/4180 . ISBN 978-981-02-4020-2.
Hartmut Ehrig; Hans-Jörg Kreowski; Ugo Montanari; Grzegorz Rozenberg, eds. (agosto de 1999). Concurrencia, paralelismo y distribución . Manual de gramáticas de grafos y computación mediante transformación de grafos. Vol. 3. World Scientific. doi : 10.1142/4181 . ISBN 978-981-02-4021-9.

[1] Pérez Velasco 2009 cubre este enfoque en detalle.

[2] "Un modelo de objetos orientado a grafos para interfaces de usuario final de bases de datos" (PDF) .

[3] "TERMGRAPH" .

[ 1 ]

[ 2 ]

[ 3 ]