## Graph Transformation Theory and Applications

#### Jour, heure et lieu

Le vendredi à 15h, online

Le calendrier des séances (format iCal).

Pour ajouter le calendrier des séances à votre agenda favori, souscrire au calendrier en indiquant ce lien.

#### 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.

### Prochaines séances

Graph Transformation Theory and Applications

Vendredi 22 octobre 2021, 15 heures, online

**Frank Drewes, Berthold Hoffmann & Mark Minas** (Department of Computing Science, Umeå University, Sweden; Department of Mathematics and Informatics, University of Bremen, Germany; Institute for Software Technology, Computer Science Department, Universität der Bundeswehr München , Germany) *Contextual Hyperedge Replacement Grammars: Languages – Parsing – Grappa*

We start from the well-established theory of context-free grammars based on hyperedge replacement (HR) and introduces a modest extension, contextual hyperedge replacement (CHR), in order to extend their generative power. We discuss the generative power and other properties of CHR, and relate them to HR.

Then we consider parsing for CHR grammars. As for HR, parsing is NP-complete in general, so that efficient parsing algorithms can only be achieved for subclasses. We have devised two algorithms, called predictive top-down (PTD) and predictive shift-reduce (PSR), which are inspired by the well-known LL(k) and LR(k) parsing for strings, and are usually linear, at most quadratic. We illustrate the ideas of these algorithms by graph transformation rules.

Finally we demonstrate Mark Minas' graph parser generator Grappa, which implements not only PTD and PSR parsing, including the needed analysis tools, but also generalized PSR, where parallel parsing allows to cope with ambiguous grammars. Measurements of generated parsers validate our theoretical findings regarding complexity.

Graph Transformation Theory and Applications

Vendredi 19 novembre 2021, 15 heures, online

**Jens H. Weber** (Department of Computer Science, University of Victoria, Canada) *GRAPEpress - A Computational Notebook for Graph Transformations*

### Séances passées

#### Année 2021

Graph Transformation Theory and Applications

Vendredi 8 octobre 2021, 15 heures, online

**Stefan Höppner & Raffaela Groner** (Institute of Software Engineering and Programming Languages, University of Ulm, Germany) *Model Transformation Languages and Performance Engineering*

Graph Transformation Theory and Applications

Vendredi 24 septembre 2021, 15 heures, online

**Romain Pascual** (MICS laboratory, CentraleSupélec, University Paris-Saclay, France) *Combinatorial maps: transformations and application to geometric modeling*

Graph Transformation Theory and Applications

Vendredi 10 septembre 2021, 15 heures, online

**Mario Alvarez-Picallo** (Department of Computer Science, University of Oxford, UK) *Soundness for Automatic Differentiation via String Diagrams*

Graph Transformation Theory and Applications

Vendredi 16 juillet 2021, 15 heures, online

**Aleks Kissinger** (Department of Computer Science, University of Oxford, UK) *Picturing Quantum Software*

Graph Transformation Theory and Applications

Vendredi 2 juillet 2021, 15 heures, online

**Filippo Bonchi** (Dipartimento di Informatica, Università degli Studi di Pisa, Italy) *The Logic of Hypergraphs*

Graph Transformation Theory and Applications

Vendredi 4 juin 2021, 15 heures, online

**Vincent Danos** (CNRS & Ecole Normale Supérieure, Paris, France) *Global Order Routing on Exchange Networks*

Graph Transformation Theory and Applications

Vendredi 21 mai 2021, 15 heures, online

**Andrea Corradini** (Computer Science Department, University of Pisa, Italy) *From Petri Nets to Graph Rewriting Systems: aspects of truly concurrent semantics*

Graph Transformation Theory and Applications

Vendredi 7 mai 2021, 15 heures, online

**James Fairbanks** (Department of Computer & Information Science & Engineering, University of Florida, USA) *Computational Categorical Algebra with Catlab*

Graph Transformation Theory and Applications

Mercredi 28 avril 2021, 18 heures, online

**Stephen Wolfram** (Wolfram Research, Champaign, USA) *GReTA Special Event: Graph Rewriting as a Foundation for Science and Technology (and the Universe)*

Stephen Wolfram is the creator of Mathematica, Wolfram|Alpha and the Wolfram Language; the author of “A New Kind of Science”; the originator of the Wolfram Physics Project; and the founder and CEO of Wolfram Research. Over the course of more than four decades, he has been a pioneer in the development and application of computational thinking—and has been responsible for many discoveries, inventions and innovations in science, technology and business.

Graph Transformation Theory and Applications

Vendredi 23 avril 2021, 15 heures, 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

Graph Transformation Theory and Applications

Vendredi 9 avril 2021, 15 heures, online

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

Graph Transformation Theory and Applications

Vendredi 26 mars 2021, 15 heures, 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

Vendredi 12 mars 2021, 15 heures, (online)

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

Graph Transformation Theory and Applications

Vendredi 26 février 2021, 15 heures, (online)

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

Graph Transformation Theory and Applications

Vendredi 12 février 2021, 15 heures, (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

Vendredi 29 janvier 2021, 15 heures, (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

Vendredi 15 janvier 2021, 15 heures, (online)

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

#### Année 2020

Graph Transformation Theory and Applications

Vendredi 18 décembre 2020, 15 heures, (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

Vendredi 4 décembre 2020, 15 heures, (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

Vendredi 20 novembre 2020, 15 heures, (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.