Reescrita de grafos

Na Teoria dos Grafos, reescrita de grafos denota um sistema de reescrita para grafos, isto é, um conjunto de regras de reescrita de grafos da forma ${\displaystyle \rho :L\longrightarrow R}$, sendo ${\displaystyle \,L}$ o grafo usado como padrão (no lado esquerdo) e ${\displaystyle \,R}$ o grafo de substituição (no lado direito da regra).

Uma regra de reescrita de grafos é aplicada ao grafo hospedeiro procurando por uma ocorrência do grafo padrão ${\displaystyle \,L}$ (resolvendo assim o problema do isomorfismo de subgrafos) e substituindo a ocorrência encontrada por uma instância do grafo de substituição.

Algumas vez gramática de grafos é usado como um sinônimo para sistema de reescrita de grafos, especialmente no contexto de linguagens formais; a expressão distinta é usada para enfatizar o objetivo de enumerar todos os grafos a partir de um grafo inicial, isto é, descrevendo uma linguagem de grafos (como em uma gramática de atributos), em vez de transformar um estado dado (um grafo hospedeiro) em um novo estado.

Abordagens à reescrita de grafos

Abordagem algébrica

Há muitas abordagens à reescrita de grafos, sendo uma delas é a abordagem algébrica, que é baseada na Teoria das Categorias. De fato a abordagem algébrica é dividida em algumas sub-abordagens, sendo a DPO (pushout duplo) e a SPO (pushout único) as mais importantes; há também outras, seguindo-se nesta linha, tais quais a sesqui-pushout e a abordagem pullback.

Pushout é o colimite de um diagrama, consistindo de dois morfismos ${\displaystyle f:Z\rightarrow X}$ e ${\displaystyle g:Z\rightarrow Y}$ com um domínio comum. Pullback é o dual do pushout.

Da perspectiva da abordagem DPO uma regra de reescrita de grafos é um par de morfismos na categoria dos grafos, com morfismos totais entre os grafos como flechas: ${\displaystyle r=(L\longleftarrow K\longrightarrow R)}$ (ou ${\displaystyle L\supseteq K\subseteq R}$), em que ${\displaystyle K\longrightarrow L}$ é injetiva. O grafo ${\displaystyle \,K}$ é chamado invariante ou algumas vezes grafo colante. Um passo de reescrita ou aplicação de uma regra ${\displaystyle \,r}$ para um grafo hospedeiro ${\displaystyle \,G}$ é definido por dois diagramas de pushout, ambos originando-se no mesmo morfismo ${\displaystyle k\colon K\longrightarrow G}$ (é daqui que o nome "pushout duplo" provém). Um morfismo de grafos ${\displaystyle m\colon L\longrightarrow G}$ que modela uma ocurrência de ${\displaystyle \,L}$ em ${\displaystyle \,G}$ é chamado de casamento. Na prática, ${\displaystyle \,L}$ é o subgrafo que é casado (ou unificado) com ${\displaystyle \,G}$ (ver problema do isomorfismo de subgrafos), e depois que um casamento é encontrado, ${\displaystyle \,L}$ é substituído por ${\displaystyle \,R}$ em um grafo hospedeiro ${\displaystyle \,G}$, onde ${\displaystyle \,K}$ funciona como uma espécie de interface.

Já na abordagem SPO uma regra de reescrita de grafos é um único morfismo na categoria dos multigrafos rotulados, com morfismos parciais entre os grafos como flechas: ${\displaystyle r\colon L\longrightarrow R}$. Assim, um passo de reescrita é definido por um único diagrama de pushout. Na prática, o processo é similar ao da abordagem DPO; a diferença é que não há interface entre o grafo hospedeiro ${\displaystyle \,G}$ e grafo ${\displaystyle \,G'}$, que é o resultado do passo de reescrita.

Abordagem por sistemas de reescrita de termos

No caso de reescrita de grafos como termos, os grafos têm que ser necessariamente dirigidos, etiquetados e com ordenação nas arestas, e as operações são caracterizadas sobre uma especificação de grafo, definida como:

${\displaystyle \,G=\langle \alpha \,|\,\{\alpha _{1}=t_{1},...,\alpha _{n}=t_{n}\}\rangle }$

em que ${\displaystyle \,\alpha _{i}}$ é um par disjunto de nós (com variáveis) e ${\displaystyle \,t_{i}}$ um termo. O nó ${\displaystyle \,\alpha }$ indica a raiz do grafo.

As seguintes propriedades devem ser respeitadas em ${\displaystyle p:L\longrightarrow R}$:

• ${\displaystyle \,L}$ não é um nó com uma única variável (então L não é da forma ${\displaystyle (x|\emptyset )}$ ou ${\displaystyle (\alpha |\alpha =x))}$
• ${\displaystyle VL(R)\subseteq VL(L)}$

(sendo ${\displaystyle \,VL(x)}$ o conjunto de variáveis livres em ${\displaystyle \,x}$)

Um sistema de reescrita grafos como termos consiste de uma assinatura e um conjunto de regras de reescrita sobre essa assinatura. A assinatura geralmente é deixada implícita.

Um casamento de ${\displaystyle \,L}$ para ${\displaystyle \,G}$ é um homomorfismo de ${\displaystyle \,L}$ em ${\displaystyle \,G}$, isto é, uma renomeação de variáveis ${\displaystyle \sigma }$ tal que ${\displaystyle L\sigma \subseteq G}$

Um redex (instância de uma regra de reescrita) em ${\displaystyle \,G}$ é determinado pelo par ${\displaystyle \,(\rho ,\sigma )}$, em que ${\displaystyle \rho :L\longrightarrow R}$ é uma regra de reescrita com ${\displaystyle L\sigma \subseteq G}$. A raiz desse redex é o nó ${\displaystyle \,\sigma (\alpha )}$, em que ${\displaystyle \,\alpha }$ é a raiz de ${\displaystyle \,L}$.

A parte do casamento de ${\displaystyle \,G}$ com relação ao redex ${\displaystyle \,(\rho ,\sigma )}$ é a coleção de especificações de nós ${\displaystyle \,\sigma (\alpha )}$ em que ${\displaystyle \,\alpha }$ é um nó em ${\displaystyle \,L}$. A especificação da raiz desse redex é a especificação do nó dessa raiz.

E finalmente, um passo de reescrita correpondente ao redex ${\displaystyle \,(\rho ,\sigma )}$ em ${\displaystyle \,G}$, denotado por ${\displaystyle \rho :L\longrightarrow R}$, consiste em substituir a especificação da raiz do redex pelo ${\displaystyle \,R\sigma }$, com uma boa escolha de variáveis ligadas (para evitar colisões com variáveis em ${\displaystyle \,G}$). Normalmente se dá destaque à parte relevante do grafo por uma denotação conveniente do "contexto": ${\displaystyle G[\sigma (\alpha )=t]\longrightarrow G[R\sigma ]}$.

Outras abordagens

Outra abordagem à reescrita de grafos, conhecida como reescrita determinante de grafos, vem da lógica da Teoria dos bancos de dados. Nessa abordagem, grafos são tratados como instâncias de bancos de dados, e operações de reescrita como um mecanismo para definição de consultas e visões; portanto, todas as reescritas devem possuir resultados únicos (salvo isomorfismo), e isto é conseguido aplicando-se qualquer regra de reescrita concorrentemente ao longo todo o grafo, onde quer que ela se aplique, de modo que o resultado é de fato unicamente definido.

Implementações e Aplicações

Exemplo para uma regra de reescrita de grafos (otimização de uma construção de compilador: multiplicação por 2 substituído pela adição)

Grafos são um formalismo expressivo, visual e matemática preciso para modelagem de objetos (entidades) ligados por relações binárias; objetos são representados por nós e relações entre eles por arestas. Nós e arestas são normalmente etiquetados. Computações são descritas neste modelo por mudanças nas relações entre as entidades ou por mudanças nas etiquetas dos elementos do grafo. Elas são codificadas nas regras de reescrita/transformação de grafos e executadas por ferramentas de reescrita/transformação de grafos.

• Ferramentas que são aplicáveis a domínios neutros:
  • GrGen.NET, o gerador de reescrita de grafos, ferramenta de gera sistemas de reescrita para grafos em C# ou .NET-assembly.

Bibliografia

• Handbook of Graph Grammars and Computing by Graph Transformations. Volume 1-3. World Scientific Publishing
• Term Rewriting Systems, Terese, Cambridge Tracts in Theoretical Computer Science, 2003.

Veja também

• Teoria dos grafos
• Teoria das categorias

Referências