En informática , la transformación o reescritura de gráficos se refiere a la técnica de crear un nuevo gráfico a partir de un gráfico original de forma algorítmica. 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 una 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 adicionales en 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 subgráfico en el estado completo, y un gráfico de reemplazo, que reemplazará al subgráfico emparejado.
Formalmente, un sistema de reescritura de gráficos generalmente consiste en un conjunto de reglas de reescritura de gráficos de la forma, con siendo llamado gráfico de patrón (o lado izquierdo) y siendo llamado gráfico de reemplazo (o el 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 patrón , resolviendo así el problema de isomorfismo del subgráfico ) 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 de gráficos se utiliza como sinónimo de sistema de reescritura de gráficos , especialmente en el contexto de los lenguajes formales ; la redacción diferente se usa para enfatizar el objetivo de las construcciones, como la enumeración de todos los gráficos 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 de host) en un nuevo estado.
Enfoques de reescritura de gráficos
Enfoque algebraico
El enfoque algebraico para la reescritura de gráficos se basa en la teoría de categorías . El enfoque algebraico se divide 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 sesqui-pushout y el enfoque de retroceso .
Desde la perspectiva del enfoque de 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 , dónde es inyectable . 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 que se originan en el mismo morfismo , donde D es un gráfico de contexto (aquí es de donde proviene el nombre doble -pushout). Otro morfismo gráficomodela una ocurrencia de L en G y se llama coincidencia . La comprensión práctica de esto es que es un subgrafo que coincide con (ver problema de isomorfismo en el subgrafo ), y después de encontrar una coincidencia, es reemplazado por en el gráfico de host dónde sirve como interfaz, que contiene los nodos y bordes que se conservan al aplicar la regla. La gráfica es necesario para adjuntar el patrón que se coincide con su contexto: si está vacío, la coincidencia solo puede designar un componente completo 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 multigraph:. Por lo tanto, un paso de reescritura se define mediante un solo diagrama de expulsión . La comprensión práctica de esto es similar al enfoque de DPO. La diferencia es que no existe una interfaz entre el gráfico de host 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 tratan la eliminación de nodos con bordes adyacentes, en particular, cómo evitan que tales eliminaciones puedan dejar "bordes colgantes". El enfoque DPO solo elimina un nodo cuando la regla también especifica la eliminación de todos los bordes adyacentes (esta condición colgante 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 similar al algebraico para la reescritura de gráficos, basado principalmente en el álgebra de Boole y un álgebra de matrices, llamadas gramáticas de gráficos matriciales . [1]
Reescritura de gráficos determinados
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 base de datos y las operaciones de reescritura como un mecanismo para definir consultas y vistas; por lo tanto, se requiere toda reescritura para producir resultados únicos ( hasta isomorfismo ), y esto se logra aplicando cualquier regla de reescritura al mismo tiempo en todo el gráfico, donde sea que se aplique, de tal manera que el resultado se defina de manera única.
Reescritura de gráfico de términos
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 completamente en la investigación sobre la reescritura de gráficos de términos y sus aplicaciones.
Clases de gramática de gráficos y sistema de reescritura de gráficos
Los sistemas de reescritura de gráficos se agrupan naturalmente en clases de acuerdo con el tipo de representación de los 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 usa con mayor frecuencia en las clasificaciones. Algunos tipos comunes son:
- Gramáticas de gráficos atribuidas , generalmente formalizadas utilizando el enfoque de expulsión simple o el enfoque de expulsión doble para caracterizar reemplazos, mencionado en la sección anterior sobre el enfoque algebraico para la reescritura de gráficos.
- Gramáticas hipergráficas, incluidas, como subclases más restrictivas , gramáticas de gráficos de puertos , gramáticas de gráficos lineales y redes de interacción .
Implementaciones y aplicaciones
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 los bordes se suelen escribir y atribuir. Los cálculos se describen en este modelo por cambios en las relaciones entre las entidades o por 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 por sistemas de reescritura de gráficos / herramientas de transformación de gráficos.
- Herramientas que son neutrales al dominio de la aplicación:
- AGG , el sistema gramatical de grafos atribuidos ( Java )
- GP (Graph Programs) es un lenguaje de programación para calcular en gráficos mediante la aplicación dirigida de reglas de transformación de gráficos.
- GMTE , el motor de transformación y comparación de gráficos para la transformación y comparación de gráficos . Es una implementación de una extensión del algoritmo de Messmer usando C ++ .
- GrGen.NET , el generador de reescritura de gráficos, una herramienta de transformación de gráficos que emite ensamblajes de código C # o .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 estado de las gramáticas de gráficos y verificar modelos de esos espacios de estado; también se puede utilizar como motor de transformación de gráficos.
- Verigraph , un sistema de verificación y especificación de software basado en la reescritura de gráficos ( Haskell ).
- Herramientas que resuelven tareas de ingeniería de software (principalmente MDA ) con reescritura de gráficos:
- eMoflon , una herramienta de transformación de modelos compatible con EMF compatible con el modelado basado en historias y las gramáticas de triple gráfico
- EMorF un sistema de reescritura de gráficos 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 gráficos basado en PROGRES
- Las bases de datos de gráficos a menudo admiten la reescritura dinámica de gráficos
- Estupendo
- Gremlin , un lenguaje de programación basado en gráficos (ver Reescritura de gráficos )
- Henshin , un sistema de reescritura de gráficos 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 lenguaje de muy alto nivel para sistemas de reescritura de gráficos programados
- VIATRA
- Herramientas de ingenieria mecanica
- GraphSynth es un intérprete y un entorno de interfaz de usuario para crear gramáticas gráficas sin restricciones, así como para probar y buscar la variante de idioma resultante. Guarda gráficos y reglas gramaticales de gráficos como archivos XML y está escrito en C # .
- Soley Studio , es un entorno de desarrollo integrado para sistemas de transformación de gráficos. Su principal enfoque de aplicación es el análisis de datos en el campo de la ingeniería.
- Aplicaciones de biología
- Modelado funcional-estructural de plantas con un lenguaje basado en gramática gráfica
- Modelado de desarrollo multicelular con gramáticas gráficas reguladas por cadenas
- Inteligencia artificial / procesamiento del lenguaje natural
- OpenCog proporciona un comparador de patrón básico (en hypergraphs ) que se utiliza para poner en práctica varios algoritmos de IA.
- RelEx es un analizador en inglés que emplea la reescritura de gráficos para convertir un análisis de enlace en un análisis de dependencia .
Ver también
- Teoría de categorías
- Teoría de grafos
- Forma gramatica
- Gramática formal
- Gráfico de término
Referencias
Citas
- ^ Pérez 2009 cubre este enfoque en detalle.
- ^ "Un modelo de objetos orientado a gráficos para interfaces de usuario final de base de datos" (PDF) .
- ^ "TERMGRAPH" .
Fuentes
- Rozenberg, Grzegorz (1997), Handbook of Graph Grammars and Computing by Graph Transformations , Volúmenes 1-3, World Scientific Publishing, ISBN 9810228848
|volume=
tiene texto extra ( ayuda ). - Pérez, PP (2009), Gramáticas gráficas matriciales: un enfoque algebraico de la dinámica gráfica , VDM Verlag , ISBN 978-3-639-21255-6.
- Heckel, R. (2006). Transformación gráfica en pocas palabras . Notas electrónicas en informática teórica 148 (1 SPEC. ISS.), Págs. 187–198.
- König, Barbara (2004). Análisis y verificación de sistemas con estructura en evolución dinámica . Tesis de habilitación, Universität Stuttgart , págs. 65–180.
- Lobo, Daniel; Vico, Francisco J .; Dassow, Jürgen (1 de octubre de 2011). "Graficar gramáticas con reescritura regulada por cadenas" . Informática Teórica . 412 (43): 6101–6111. doi : 10.1016 / j.tcs.2011.07.004 . ISSN 0304-3975 .
- Grzegorz Rozenberg , ed. (Febrero de 1997). Fundaciones . Manual de Gramáticas de Gráficos y Computación por Transformación de Gráficos. 1 . World Scientific. doi : 10.1142 / 3303 . ISBN 978-981-02-2884-2.
- Hartmut Ehrig ; Gregor Engels; Hans-Jörg Kreowski ; Grzegorz Rozenberg, eds. (Octubre de 1999). Aplicaciones, Idiomas y Herramientas . Manual de Gramáticas de Gráficos y Computación por Transformación de Gráficos. 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). Simultaneidad, paralelismo y distribución . Manual de Gramáticas de Gráficos y Computación por Transformación de Gráficos. 3 . World Scientific. doi : 10.1142 / 4181 . ISBN 978-981-02-4021-9.