Dominique Duval

Algebraic graph rewriting


Graphs are used to describe a wide range of situations. When system states are represented by graphs, it is natural to use rules that transform graphs to describe the system evolution. The algebraic approaches to graph transformation are based on the fact that the categorical notions of pushout and pullback provide a good description of the simplest transformations. Then the challenge is to generalize them in a proper way for expressing a diversity of transformations on a diversity of graphs. The algebraic approaches to graph transformation include the double-pushout (DPO), the single-pushout (SPO), the sesqui-pushout (SqPO), which subsumes the DPO and SPO in most situations, as well as the double-pullback (DPB).

In 2014 we extended the SqPO approach to attributed graphs, which play an important role in model-driven design and programming. In 2015 we proposed the AGREE approach (for Algebraic Graph Rewriting with controllEd Embedding), which can simulate the SqPO rewriting and which allows non-local transformations. In 2016 we went one step further in understanding how pushout-based and pullback-based algebraic approaches may collaborate. In 2018 we introduced a new categorical condition of parallel independence and we proved its equivalence with two other conditions proposed in the literature.

See my Publications with Andrea Corradini, Michael Löwe, Rachid Echahed, Frédéric Prost and Leila Ribeiro and the references in these papers.