b"\n_START_ARTICLE_\nReescriptura de grafs\n_START_PARAGRAPH_\nUna transformaci\xc3\xb3 de grafs, o reescriptura de grafs, \xc3\xa9s una t\xc3\xa8cnica per crear algor\xc3\xadstmicament un nou graf a partir d'un altre graf donat. T\xc3\xa9 nombroses aplicacions, des de l'enginyeria de programari fins a algorismes i generaci\xc3\xb3 d'imatges._NEWLINE_La reescriptura de grafs es pot utilitzar com a abstracci\xc3\xb3 de computacions. La idea b\xc3\xa0sica \xc3\xa9s que l'estat d'una computaci\xc3\xb3 es pot representar en forma de graf, i els passos seg\xc3\xbcents en aquesta computaci\xc3\xb3 es poden representar mitjan\xc3\xa7ant regles de transformaci\xc3\xb3 sobre el graf. Aquestes regles consisteixen d'un graf de partida, que s'encaixa amb un subgraf per a l'edtat complet, i un graf de substituci\xc3\xb3, que reempla\xc3\xa7ar\xc3\xa0 el subgraf encaixat.\n_START_SECTION_\nDefinici\xc3\xb3\n_START_PARAGRAPH_\nFormalment, un sistema de reescriptura de grafs consisteix d'un conjunt de regles de reescriptura de grafs de la forma , on  \xc3\xa9s el graf patr\xc3\xb3 (o membre esquerre de la regla), i  \xc3\xa9s el graf de substituci\xc3\xb3 (o membre dret). La manera d'aplicar una regla de reescriptura al graf original consisteix a cercar l'aparici\xc3\xb3 del graf patr\xc3\xb3 (comprovaci\xc3\xb3 de patrons o pattern matching, resolent aix\xc3\xad el problema d'isomorfisme de subgrafs) i substituint l'aparici\xc3\xb3 trobada per una inst\xc3\xa0ncia del graf de substituci\xc3\xb3. Les regles de reescriptura es poden refinar en el cas de grafs etiquetats._NEWLINE_De vegades s'utilitza el terme gram\xc3\xa0tica de grafs com a sin\xc3\xb2nim de sistema de reescriptura de grafs, especialment en el context dels llenguatges formals; aquesta altra terminologia s'utilitza per emfasitzar l'objectiu de les construccions, com l'enumeraci\xc3\xb3 de tots els grafs a partir d'un cert graf de partida, \xc3\xa9s a dir, la generaci\xc3\xb3 d'un llenguatge de grafs, en comptes de simplement transformar un estat inicial (simbolitzat pel graf original) en un nou estat.\n_START_SECTION_\nAproximaci\xc3\xb3 algebraica\n_START_PARAGRAPH_\nL'aproximaci\xc3\xb3 algebraica a la reescriptura de grafs es basa en la teoria de categories. Aquesta aproximaci\xc3\xb3 algebraica es pot subdividir en altres aproximacions, on les m\xc3\xa9s comunes s\xc3\xb3n la transformaci\xc3\xb3 de pushout doble de grafs ((angl\xc3\xa8s) Double-pushout graph rewriting, DPO) i la transformaci\xc3\xb3 de pushout simple de grafs ((angl\xc3\xa8s) Single-pushout graph rewriting, SPO). Altres aproximacions inclouen el sesqui-pushout i el pullback._NEWLINE_Des de la perspectiva de l'aproximaci\xc3\xb3 DPO, una regla de reescriptura de grafs \xc3\xa9s un parell de morfismes de la categoria de grafs i homomorfismes de grafs entre ells:  (o ) on  \xc3\xa9s injectiu. Es diu que el graf K \xc3\xa9s l'invariant o el graf aglutinador. Un pas de reescriptura o aplicaci\xc3\xb3 d'una regla r a un graf de partida G es defineix per dos diagrames pushout que originen el mateix morfisme , on D \xc3\xa9s un graf context (d'aqu\xc3\xad el nom de pushout doble). Un altre morfisme de grafs  modela l'aparici\xc3\xb3 de L dins G, i s'anomena comprovaci\xc3\xb3 de patrons. Una manera d'entendre aquest plantejament \xc3\xa9s veure que  \xc3\xa9s un subgraf patr\xc3\xb3 identificat dins , i un cop que es troba una coincid\xc3\xa8ncia, se substitueix  amb  en el graf de partida , on  actua com una interf\xc3\xadcie, que cont\xc3\xa9 els nodes i les arestes que es conserven per aplicaci\xc3\xb3 de la regla. \xc3\x89s necessari que el graf  s'acobli al patr\xc3\xb3 dins el seu context: si \xc3\xa9s buit, la coincid\xc3\xa8ncia nom\xc3\xa9s pot designar la totalitat d'una component connexa del graf ._NEWLINE_En contrast amb aix\xc3\xb2, una regla de reescriptura amb l'aproximaci\xc3\xb3 SPO \xc3\xa9s un sol morfisme de la categoria dels multigrafs etiquetats i aplicacions parcials que preserven l'estructura de multigraf: . Aix\xc3\xad, un pas de reescriptura es defineix per un sol diagrama de pushout. La interpretaci\xc3\xb3 \xc3\xa9s similar al cas de l'aproximaci\xc3\xb3 DPO; la difer\xc3\xa8ncia \xc3\xa9s que no hi ha cap interf\xc3\xadcie entre el graf de partida G i el graf G' que resulta d'aplicar el pas de reescriptura._NEWLINE_Tamb\xc3\xa9 existeix una altra aproximaci\xc3\xb3 algebraica per a la reescriptura de grafs, principalment basada en \xc3\xa0lgebra booleana i \xc3\xa0lgebra de matrius, anomenada gram\xc3\xa0tiques matricials de grafs.\n_START_SECTION_\nReescriptura de grafs determinada\n_START_PARAGRAPH_\nUna altra aproximaci\xc3\xb3 a la reescriptura de grafs, coneguda com a reescriptura de grafs determinada, va sorgir a partir de la l\xc3\xb2gica i la teoria de bases de dades. En aquesta aproximaci\xc3\xb3, els grafs es tracten com si fossin inst\xc3\xa0ncies de bases de dades, i les operacions de reescriptura com un mecanisme per a definir consultes i vistes; per tant, tota reescriptura ha de proporcionar uns resultats \xc3\xbanics (llevat d'isomorfismes), i hom aconsegueix aix\xc3\xb2 aplicant qualsevol regla de reescriptura de forma concurrent a trav\xc3\xa9s del graf, all\xc3\xa0 on tingui sentit, de manera que el resultat estigui, efectivament, definit de manera un\xc3\xadvoca.\n_START_SECTION_\nReescriptura de grafs de termes\n_START_PARAGRAPH_\nUna altra aproximaci\xc3\xb3 a la reescriptura de grafs \xc3\xa9s la reescriptura de grafs de termes, que consisteix en el proc\xc3\xa9s de transformaci\xc3\xb3 de grafs de termes (tamb\xc3\xa9 coneguts com a grafs sem\xc3\xa0ntics abstractes) mitjan\xc3\xa7ant un conjunt de regles sem\xc3\xa0ntiques de reescriptura._NEWLINE_Els grafs de termes s\xc3\xb3n una \xc3\xa0rea d'estudi actual en la investigaci\xc3\xb3 dels llenguatges de programaci\xc3\xb3, ja que les regles de reescriptura de grafs de termes s\xc3\xb3n capaces d'expressar formalment la sem\xc3\xa0ntica operacional d'un compilador. Els grafs de termes tamb\xc3\xa9 s'utilitzen com a m\xc3\xa0quines abstractes capaces de modelitzar c\xc3\xa0lculs qu\xc3\xadmics i biol\xc3\xb2gics, aix\xc3\xad com c\xc3\xa0lculs gr\xc3\xa0fics com els models de concurr\xc3\xa8ncia. Els grafs de termes poden realitzar verificacions autom\xc3\xa0tiques i programaci\xc3\xb3 l\xc3\xb2gica, ja que estan orientats a representar enunciats quantificats en l\xc3\xb2gica de primer ordre. Les eines de programaci\xc3\xb3 simb\xc3\xb2lica \xc3\xa9s una altra aplicaci\xc3\xb3 dels grafs de termes, que s\xc3\xb3n capa\xc3\xa7os de representar i realitzar c\xc3\xa0lculs amb estructures algebraiques abstractes, com grups, cossos i anells._NEWLINE_La confer\xc3\xa8ncia TERMGRAPH se centra exclusivament en la recerca sobre la reescriptura de grafs de termes i les seves aplicacions."