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 more general transformations. 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. A rewrite step for AGREE is made of a pullback followed by a pushout.

In 2016 we went one step further in understanding how pushout-based and pullback-based algebraic approaches may collaborate.

See my Publications with Andrea Corradini, Rachid Echahed, Frédéric Prost and Leila Ribeiro and their bibliography.