Reescriptura de grafs

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.

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

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ó

modifica

Formalment, un sistema de reescriptura de grafs consisteix d'un conjunt de regles de reescriptura de grafs de la forma  , on   és el graf patró (o membre esquerre de la regla), i   é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

modifica

Aproximació algebraica

modifica

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:   (o  ) on   é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  , on D és un graf context (d'aquí el nom de pushout doble). Un altre morfisme de grafs   modela l'aparició de L dins G, i s'anomena comprovació de patrons. Una manera d'entendre aquest plantejament és veure que   és un subgraf patró identificat dins  , i un cop que es troba una coincidència, se substitueix   amb   en el graf de partida  , on   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   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  .

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:  . 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.[1][2]

Reescriptura de grafs determinada

modifica

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

modifica

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[3] se centra exclusivament en la recerca sobre la reescriptura de grafs de termes i les seves aplicacions.

Implementacions i aplicacions

modifica

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).

Referències

modifica
  1. Perez 2009 tracta en detall aquesta aproximació.
  2. Per a més detalls sobre aquest aspecte, consulteu mat2gra.info.
  3. «TERMGRAPH».

Bibliografia

modifica

Vegeu també

modifica