Sandro Stucki

Reversible Sesqui-Pushout Rewriting

Vincent Danos, Tobias Heindel, Ricardo Honorato-Zimmer, and Sandro Stucki. In Graph Transformation -- 7th International Conference (ICGT '14), in LNCS, volume 8571, pp. 161–176, Springer, 2014.


The paper proposes a variant of sesqui-pushout rewriting (SqPO) that allows one to develop the theory of nested application conditions (NACs) for arbitrary rule spans; this is a considerable generalisation compared with existing results for NACs, which only hold for linear rules (w.r.t. a suitable class of monos). Besides this main contribution, namely an adapted shifting construction for NACs, the paper presents a uniform commutativity result for a revised notion of independence that applies to arbitrary rules; these theorems hold in any category with (enough) stable pushouts and a class of monos rendering it weak adhesive HLR. To illustrate results and concepts, we use simple graphs, i.e. the category of binary endorelations and relation preserving functions, as it is a paradigmatic example of a category with stable pushouts; moreover, using regular monos to give semantics to NACs, we can shift NACs over arbitrary rule spans.