Reescritura de grafos

Ejemplo de una regla de reescritura de grafos (optimización en la construcción de un compilador: multiplicación por 2 sustituida por suma)

En ciencias de la computación, transformación de grafos, o reescritura de grafos, Se refiere a la técnica de crear nuevos grafos a partir de un grafo origina de forma algorítmica. Tiene numerosas aplicaciones, desde ingeniería de software, (construcción de software y también Verificación de software) hasta diseño de algoritmos y generación de imágenes.

Las transformaciones de grafos pueden ser usadas como abstracción computacional. la idea básica es que el estado de un cálculo puede ser representado como un grafo, los siguientes pasos de ese cálculo pueden ser entonces representados como reglas de transformación en ese grafo. Dichas reglas consisten en un grafo original, que debe coincidir con un subgrafo en su estado completo, y un grafo de reemplazo que sustituirá a dicho grafo coincidente.

Formalmente, un sistema de reescritura de grafos suele consistir de un conjunto de reglas de reescritura de la forma ${\displaystyle L\rightarrow R}$, con ${\displaystyle L}$ siendo "grafos de patrón" (o lado izquierdo) y ${\displaystyle R}$ siendo "grafo de reemplazo" (o lado derecho de la regla). Una regla de reescritura se aplica al grafo anfitrión buscando una ocurrencia en el grafo de patrón (Búsqueda de patrones, así resolviendo el Problema de isomorfismo de subgrafos) y reemplazando la ocurrencia encontrada por una instancia del grafo de reemplazo. Reglas de reescritura pueden ser más reguladas en el caso de grafo etiquetados, como en una gramática de grafos regulada por cadenas.

A veces gramática de grafos se usa como sinónimo de sistema de reescritura de grafos, especialmente en el contexto de lenguajes formales; diferentes estilos de escritura se utilizan para enfatizar el objetivo buscado, como la enumeracion de todos los grafos desde un grafo inicial, es decir, la generación de un idioma de grafos, en lugar de simplemente transformar un estado dado (grafo anfitrión) a un nuevo estado.

Véase también

• Teoría de categorías
• Teoría de grafos
• Gramática geométrica
• Gramática formal

Notas

Referencias

• Rozenberg, Grzegorz (1997), Handbook of Graph Grammars and Computing by Graph Transformations, World Scientific Publishing, volumes 1–3, ISBN 9810228848, archivado desde el original el 4 de octubre de 2013, consultado el 2 de mayo de 2018 ..
• Perez, P.P. (2009), Matrix Graph Grammars: An Algebraic Approach to Graph Dynamics, VDM Verlag, ISBN 978-3-639-21255-6 ..
• Heckel, R. (2006). Graph transformation in a nutshell. Electronic Notes in Theoretical Computer Science 148 (1 SPEC. ISS.), pp. 187–198.
• König, Barbara (2004). Analysis and Verification of Systems with Dynamically Evolving Structure. Habilitation thesis, Universität Stuttgart, 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. ISSN 0304-3975. doi:10.1016/j.tcs.2011.07.004. 
• Esta obra contiene una traducción total derivada de «Graph rewriting» de Wikipedia en inglés, concretamente de esta versión del 23 de marzo de 2018, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.