GPaR main goal is to rewrite a graph denoted g into a graph g' by using, simultaneously, rewriting rules.
GPaR deals with overlapping matches and thus can be used for a large variety of rewriting problems including cellular automata or L-systems.
To tackle this problem of overlapping matches, an extended definition of graph is used. Usually, a graph is defined by an order pair (V,E) where V is the set of vertices and E a set of edges. Here, two types of vertices are identified: V=N ∪ P where N is a set of attributed nodes and P the set of attributed ports. Ports have a central role in ensuring the effective connection between the remaining parts of g in g' and the new parts. The methods used in GPaR are based on the theoretical results of "Parallel graph rewriting with overlapping rules" of Rachid Echahed and Aude Maignan ( CoRR, abs/1701.06790, 2017).
Formally, we define a general structure called pregraph :
A pregraph H is a tuple H= (NH, PH, PNH, PPH, AttH, attH) such that:
- NH is a finite set of nodes and PH is a finite set of ports,
- PNH is a relation PNH ⊆ PH × NH,
- PPH is a symmetric binary relation on ports, PPH ⊆PH × PH,
- AttH is a structure of attributes,
- attH is a function attH: PH ⊎ NH → 2AttH such that ∀ x ∈ NH ⊎ PH, card(attH(x)) is finite.
- PN is a relation ⊆ P × N which associates at most one node to every port.
- PP is a symmetric binary relation which associates at most one port to another port.
- full parallel rewrite relation: g is rewritten in g' using all the possible matches (including eventual permutations of the same set of nodes and ports).
- parallel rewrite relation up to automorphisms: If a set of matches is obtained from one rewrite rule on a same set of nodes and ports then only one match of this set is used during the rewriting process. Confluence results can be found in the paper cited above.
- It selects all the subgraphs of g whose elements match one of the pattern li,
- If the parallel rewrite relation "is up to automorphism" then it reduces the set of matches to the set of matches up to automorphism;
- It replaces all the matches of all the li by a variant of ri. The states of nodes and port are computed according to the rules. A pregraph has been created.
- It merges ports and edges accordingly to the rewriting modulo approach.