Reescriptura de grafs

Exemple d'una regla de reescriptura de grafs (optimització dins la construcció d'un compilador: multiplicació per 2 substituïda per suma)

Una transformació de grafs, o reescriptura de grafs, és una tècnica per crear algorístmicament un nou graf a partir d'un altre graf donat. Té nombroses aplicacions, des de l'enginyeria de programari fins a algorismes i generació d'imatges.

La reescriptura de grafs es pot utilitzar com a abstracció de computacions. La idea bàsica és que l'estat d'una computació es pot representar en forma de graf, i els passos següents en aquesta computació es poden representar mitjançant regles de transformació 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ó, que reemplaçarà el subgraf encaixat.

Definició

Formalment, un sistema de reescriptura de grafs consisteix d'un conjunt de regles de reescriptura de grafs de la forma $L\rightarrow R$, on $L$ és el graf patró (o membre esquerre de la regla), i $R$ és el graf de substitució (o membre dret). La manera d'aplicar una regla de reescriptura al graf original consisteix a cercar l'aparició del graf patró (comprovació de patrons o pattern matching, resolent així el problema d'isomorfisme de subgrafs) i substituint l'aparició trobada per una instància del graf de substitució. Les regles de reescriptura es poden refinar en el cas de grafs etiquetats.

De vegades s'utilitza el terme gramàtica de grafs com a sinònim 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ó de tots els grafs a partir d'un cert graf de partida, és a dir, la generació d'un llenguatge de grafs, en comptes de simplement transformar un estat inicial (simbolitzat pel graf original) en un nou estat.

Aproximacions a la reescriptura de grafs

Aproximació algebraica

L'aproximació algebraica a la reescriptura de grafs es basa en la teoria de categories. Aquesta aproximació algebraica es pot subdividir en altres aproximacions, on les més comunes són la transformació de pushout doble de grafs ((anglès) Double-pushout graph rewriting, DPO) i la transformació de pushout simple de grafs ((anglès) Single-pushout graph rewriting, SPO). Altres aproximacions inclouen el sesqui-pushout i el pullback.

Des de la perspectiva de l'aproximació DPO, una regla de reescriptura de grafs és un parell de morfismes de la categoria de grafs i homomorfismes de grafs entre ells: $r=(L\leftarrow K\rightarrow R)$ (o $L\supseteq K\subseteq R$) on $K\rightarrow L$ és injectiu. Es diu que el graf K és l'invariant o el graf aglutinador. Un pas de reescriptura o aplicació d'una regla r a un graf de partida G es defineix per dos diagrames pushout que originen el mateix morfisme $k\colon K\rightarrow D$, on D és un graf context (d'aquí el nom de pushout doble). Un altre morfisme de grafs $m\colon L\rightarrow G$ modela l'aparició de L dins G, i s'anomena comprovació de patrons. Una manera d'entendre aquest plantejament és veure que $L$ és un subgraf patró identificat dins $G$, i un cop que es troba una coincidència, se substitueix $L$ amb $R$ en el graf de partida $G$, on $K$ actua com una interfície, que conté els nodes i les arestes que es conserven per aplicació de la regla. És necessari que el graf $K$ s'acobli al patró dins el seu context: si és buit, la coincidència només pot designar la totalitat d'una component connexa del graf $G$.

En contrast amb això, una regla de reescriptura amb l'aproximació SPO és un sol morfisme de la categoria dels multigrafs etiquetats i aplicacions parcials que preserven l'estructura de multigraf: $r\colon L\rightarrow R$. Així, un pas de reescriptura es defineix per un sol diagrama de pushout. La interpretació és similar al cas de l'aproximació DPO; la diferència és que no hi ha cap interfície entre el graf de partida G i el graf G' que resulta d'aplicar el pas de reescriptura.

També existeix una altra aproximació algebraica per a la reescriptura de grafs, principalment basada en àlgebra booleana i àlgebra de matrius, anomenada gramàtiques matricials de grafs.

Reescriptura de grafs determinada

Una altra aproximació a la reescriptura de grafs, coneguda com a reescriptura de grafs determinada, va sorgir a partir de la lògica i la teoria de bases de dades. En aquesta aproximació, els grafs es tracten com si fossin instàncies 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 únics (llevat d'isomorfismes), i hom aconsegueix això aplicant qualsevol regla de reescriptura de forma concurrent a través del graf, allà on tingui sentit, de manera que el resultat estigui, efectivament, definit de manera unívoca.

Reescriptura de grafs de termes

Una altra aproximació a la reescriptura de grafs és la reescriptura de grafs de termes, que consisteix en el procés de transformació de grafs de termes (també coneguts com a grafs semàntics abstractes) mitjançant un conjunt de regles semàntiques de reescriptura.

Els grafs de termes són una àrea d'estudi actual en la investigació dels llenguatges de programació, ja que les regles de reescriptura de grafs de termes són capaces d'expressar formalment la semàntica operacional d'un compilador. Els grafs de termes també s'utilitzen com a màquines abstractes capaces de modelitzar càlculs químics i biològics, així com càlculs gràfics com els models de concurrència. Els grafs de termes poden realitzar verificacions automàtiques i programació lògica, ja que estan orientats a representar enunciats quantificats en lògica de primer ordre. Les eines de programació simbòlica és una altra aplicació dels grafs de termes, que són capaços de representar i realitzar càlculs amb estructures algebraiques abstractes, com grups, cossos i anells.

La conferència TERMGRAPH se centra exclusivament en la recerca sobre la reescriptura de grafs de termes i les seves aplicacions.

Implementacions i aplicacions

Els grafs són un formalisme expressiu, visual i matemàticament precís per modelitzar objectes (entitats) vinculades mitjançant relacions; els nodes representen els objectes i les arestes representen les relacions. És habitual que tant els nodes com les arestes siguin d'un tipus precís. En aquest model, els càlculs venen descrits com a canvis en les relaciins entre entitats, o com a alteracions dels atributs dels elements del graf. Aquests càlculs es codifiquen en regles de reescriptura (o de transformació) de grafs, i els executen els sistemes de reescriptura de grafs (o les eines de transformació de grafs).

• Eines vàlides en qualsevol àrea:
  • GrGen.NET, el generador de reescriptura de grafs, una eina de transformació de grafs que proporciona codi C# o ensamblats .NET.
  • AGG Arxivat 2011-02-17 a Wayback Machine., el sistema de gramàtica de grafs amb atributs (Java)
  • GP (Graph Programs) Arxivat 2016-03-25 a Wayback Machine. és un llenguatge de programació per a computació sobre grafs, mitjançant l'aplicació directa de regles de transformació de grafs.
  • GMTE Arxivat 2018-03-13 a Wayback Machine., el Motor de Coincidències i Transformacions de Grafs (Graph Matching and Transformation Engine). És una implementació d'una extensió de l'algorisme de Messmer que utilitza C++
  • GROOVE, una eina basada en Java per a editar grafs i regles de transformació de grafs, que explora els espais d'estat de les gramàtiques de grafs, i que comprova els models d'aquests espais d'estats; també es pot utilitzar com un motor de transformació de grafs.
• Eines que resolen tasques d'enginyeria de programari (principalment Arquitectura dirigida per models) mitjançant la reescriptura de grafs:
  • eMoflon, eina de transformació de models basada en un entorn de treball per Eclipse.
  • GReAT
  • VIATRA
  • Les bases de dades orientades a grafs acostumen a donar suport a la reescriptura dinàmica de grafs
  • Gremlin Arxivat 2013-01-16 a Wayback Machine., un llenguatge de programació basat en grafs (vegeu Graph Rewriting a GitHub)
  • PROGRES, un entorn integrat i a alt nivell per a sistemes de reescriptura programada de grafs ((anglès) PROgrammed Graph REwriting Systems)
  • Fujaba, un llenguatge de reescriptura de grafs basat en PROGRES
  • EMorF Arxivat 2016-04-22 a Wayback Machine. i Henshin, sistemes de reescriptura de grafs basats en un entorn de treball per Eclipse.
• Eines d'enginyeria mecànica
  • GraphSynth és un intèrpret i entorn d'interfície d'usuari per a crear gramàtiques il·limitades de grafs, així com per a comprovar i cercar la variant del llenguatge resultant. Emmagatzema grafs i regles de la gramàtica de grafs en format XML, i està escrit en C#.
  • Soley Studio Arxivat 2015-03-17 at Archive.is és un entorn integrat de desenvolupament per a sistemes de transformació de grafs. El seu principal camp d'aplicació és l'anàlisi de dades en l'àrea de l'enginyeria.
• Aplicacions a la biologia
  • Model de plantes funcional-estructural mitjançant un llenguatge basat en una gramàtica de grafs
  • Modelat de desenvolupament multicel·lular mitjançant gramàtiques de grafs regulades per cadenes
• Intel·ligència artificial (IA)/Processament de llenguatge natural
  • OpenCog proporciona un comprovador de patrons bàsic (sobre hipergrafs), utilitzat per a implementar diversos algorismes d'IA.
  • RelEx és un analitzador sintàctic que utilitza reescriptura de grafs.

Bibliografia

• Rozenberg, Grzegorz. Handbook of Graph Grammars and Computing by Graph Transformations. World Scientific Publishing, volumes 1–3, 1997. ISBN 9810228848.  Arxivat 2013-10-04 a Wayback Machine..
• Perez, P.P.. Matrix Graph Grammars: An Algebraic Approach to Graph Dynamics. VDM Verlag, 2009. ISBN 978-3-639-21255-6. .
• Heckel, Reiko «Electronic Notes in Theoretical Computer Science Graph transformation in a nutshell». Electronic Notes in Theoretical Computer Science. Elsevier, 148, 1, 01-02-2006, pàg. 187–198. DOI: 10.1016/j.entcs.2005.12.018.
• König, Barbara «Analysis and Verification of Systems with Dynamically Evolving Structure». Habilitation thesis, Universität Stuttgart, 2004, pàg. 65–180. Arxivat de l'original el 2007-06-25 [Consulta: 2 abril 2016].
• Lobo, D. [et al]. «Graph grammars with string-regulated rewriting». Theoretical Computer Science, 412, 43, 2011, pàg. 6101-6111. DOI: 10.1016/j.tcs.2011.07.004.

Vegeu també

• Teoria de categories
• Teoria de grafs
• Gramàtica formal