Reescritura de grafos

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, ( 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 , con siendo "grafos de patrón" (o lado izquierdo) y 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 ; 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.