## Graph Transformation Theory and Applications

The calendar of events (iCal format).

In order to add the event calendar to your favorite agenda, subscribe to the calendar by using this link.

#### Contact(s)

The GReTA – Graph TRansformation Theory and Applications virtual seminar series aims to serve as a platform for the international graph rewriting community, to promote recent developments and trends in the field, and to permit a regular networking and interaction between members of this community. Seminars are held twice a month in the form of Zoom sessions (some of which will be live-streamed to YouTube).

Please refer to GReTA homepage for further information on how to participate in this seminar via Zoom or via YouTube live streams.

### Next talks

Graph Transformation Theory and Applications

Friday March 12, 2021, 3PM, (online)

**Jean-Pierre Jouannaud** (Laboratoire d'Informatique (LIX), École Polytechnique) *Composition-based Graph Rewriting*

Graph Transformation Theory and Applications

Friday March 26, 2021, 3PM, online

**Hans-Jörg Kreowski & Aaron Frederick Lye** (University of Bremen, Germany) *Formal Graph Language Theory & Fusion Grammars*

A fusion grammar is a hypergraph grammar which provides a start hypergraph of small connected components. To derive hypergraphs, connected components can be copied multiple times and can be fused by the application of fusion rules (where such an application removes two complementary hyperedges and merges their attachment vertices). The generated hypergraph language contains all terminal connected components of derived hypergraphs. The main results for various kinds of fusion grammars concern their generative power.

Graph Transformation Theory and Applications

Friday April 9, 2021, 3PM, online

**Jonathan Gorard** (University of Cambridge and Wolfram Research, UK) *Hypergraph Rewriting and the Wolfram Model*

Graph Transformation Theory and Applications

Friday April 23, 2021, 3PM, online

**Paweł Sobociński** (Department of Computer Science, Tallinn University of Technology, Estonia) *Rewriting Modulo Symmetric Monoidal Structure*

If we are to take string diagrams out of research papers and into practical applications, we need understand how to implement diagrammatic reasoning. This is the focus of my talk.

There is a tight correspondence between symmetric monoidal categories where every object has a coherent special Frobenius algebra structure and categories of cospans of hypergraphs. This correspondence, therefore, takes us from a topological understanding of string diagrams to a combinatorial data-structure-like description. Moreover, diagrammatic reasoning translates via this correspondence exactly to DPO rewriting with interfaces.

The obvious follow-up question is: how much of this correspondence survives if we drop the assumption about Frobenius structure? Can we use this correspondence to implement diagrammatic reasoning on vanilla symmetric monoidal categories? The answer is yes, but we need to restrict the kinds of cospans we consider: the underlying hypergraph has to be acyclic and satisfy an additional condition called monogamy. Moreover, we must restrict the DPO rewriting mechanism to a variant that we call convex DPO rewriting. The good news is that none of these modifications come with a significant algorithmic cost.

The material in this talk is joint work with Filippo Bonchi, Fabio Gadducci, Aleks Kissinger and Fabio Zanasi, and has been published in a series of papers:

- “Rewriting modulo symmetric monoidal structure”, Proceedings of LiCS 2016

- “Confluence of Graph Rewriting with Interfaces”, Proceedings of ESOP 2017

- “Rewriting with Frobenius”, Proceedings of LiCS 2018

### Previous talks

#### Year 2021

Graph Transformation Theory and Applications

Friday February 26, 2021, 3PM, (online)

**Detlef Plump & Graham Campbell** (University of York, UK & Newcastle University, UK) *Fast Graph Programs*

Graph Transformation Theory and Applications

Friday February 12, 2021, 3PM, (online)

**Alexandru Burdusel & Steffen Zschaler** (Department of Informatics, King's College London, UK) *MDEOptimiser: Searching for optimal models with EMF and Henshin*

Graph Transformation Theory and Applications

Friday January 29, 2021, 3PM, (online)

**Leen Lambers & Fernando Orejas** (Hasso-Plattner-Institut Potsdam, Germany & Technical University of Catalonia (UPC), Spain) *Confluence of Graph Transformation*

Traditionally, the set of critical pairs has been shown to constitute such a set. It is representative in the sense that for each conflict a critical pair exists, representing the conflict in a minimal context, such that it can be extended injectively to this conflict (M-completeness). Recently, it has been shown that initial conflicts constitute a considerably reduced subset of critical pairs, being still representative in a slightly different way. In particular, for each conflict there exists a unique initial conflict that can be extended (possibly non-injectively) to the given conflict (completeness). Compared to the set of critical pairs, the smaller set of initial conflicts allows for more efficient conflict as well as confluence analysis.

We continue by demonstrating that initial conflicts (critical pairs) are minimally complete (resp. minimally M-complete), and thus are both optimally reduced w.r.t. representing conflicts in a minimal context via general (resp. injective) extension morphisms. We proceed with showing that it is impossible to generalize this result to the case of rules with application conditions (equivalent to FOL on graphs). We therefore revert to a symbolic setting, where finiteness and minimal (M-)completeness can again be guaranteed. Finally, we describe important special cases (e.g. rules with negative application conditions), where we are able to obtain minimally complete (resp. M-complete) sets of conflicts in the concrete setting again.

Graph Transformation Theory and Applications

Friday January 15, 2021, 3PM, (online)

**Christoph Bockisch & Gabriele Taentzer** (Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Germany) *Java Bytecode Verification and Manipulation based on Model Driven Engineering*

#### Year 2020

Graph Transformation Theory and Applications

Friday December 18, 2020, 3PM, (online)

**Maribel Fernandez & Bruno Pinaud** (King's College London, UK & Université de Bordeaux, France) *Hierarchical port graphs & PORGY - port graph rewriting as a modelling tool*

This is joint work with members of the PORGY team at Bordeaux and King’s College London.

Graph Transformation Theory and Applications

Friday December 4, 2020, 3PM, (online)

**Daniel Merkle & Jakob Lykke Andersen** (Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark) *Chemical Graph Transformation and Applications*

In this talk, we present our on-going work on creating a practical modelling framework for chemistry based on Double Pushout graph transformation, and how it can be applied to analyse chemical systems. We will address important technical design decisions as well as the importance of methods inspired from Algorithm Engineering in order to reach the required efficiency of our implementation. We will present chemically relevant features that our framework provides (e.g. automatic atom tracing) as well as a set of chemical systems we investigated are currently investigating. If time allows we will discuss variations of graph transformation rule compositions and their chemical validity.

Graph Transformation Theory and Applications

Friday November 20, 2020, 3PM, (online)

**Barbara König** (Fakultät für Ingenieurwissenschaften, Universität Duisburg-Essen, Germany) *Graph Transformation Meets Logic*

In the graph transformation community the formalism of nested graph conditions has emerged, that is, conditions which are equivalent to first-order logic, but directly integrate graphs and graph morphisms, in order to express constraints more succinctly.

In this talk we also explain how the notion of nested conditions can be lifted from graph transformation systems to the setting of reactive systems as defined by Leifer and Milner. It turns out that some constructions for graph transformation systems (such as computing weakest preconditions and strongest postconditions and showing local confluence by means of critical pair analysis) can be done quite elegantly in the more general setting.