## Graph Transformation Theory and Applications

#### Day, hour and place

Friday at 3pm, online

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 April 21, 2023, 3PM, online

**Uwe Egbert Wolter** (Department of Informatics, University of Bergen, Norway) *Generalized Sketches, Sketch Implications and Sketch Conditions*

Graph Transformation Theory and Applications

Friday May 5, 2023, 3PM, online

**Ricardo Honorato-Zimmer** (Centro Interdisciplinario de Neurociencias de Valparaíso (CINV), Universidad de Valparaíso, Chile) *Energy-based modelling*

### Previous talks

#### Year 2023

Graph Transformation Theory and Applications

Friday January 27, 2023, 3PM, online

**Steffen Zschaler** (Department of Informatics, King's College London, UK) *Composing Executable Domain-Specific Modelling Languages – A Graph-Transformation Based Approach*

Graph Transformation Theory and Applications

Friday January 13, 2023, 3PM, online

**Manfred Nagl** (RWTH Aachen University, Germany) *What have the Design in Informatics and of Gothic Cathedrals in common?*

#### Year 2022

Graph Transformation Theory and Applications

Friday December 16, 2022, 3PM, online

**Steffen Zschaler** (Department of Informatics, King's College London, UK) *Activation diagrams as a tool for generating consistency-preserving graph transformation rules: the case of product-line configuration with Acapulco*

Graph Transformation Theory and Applications

Friday November 18, 2022, 3PM, online

**Reiko Heckel** (Department of Informatics, University of Leicester, UK) *Visual Smart Contracts for DAML: A Case Study in Groove*

Graph Transformation Theory and Applications

Friday November 4, 2022, 3PM, online

**Luciano Baresi** (DEIB Politecnico di Milano, Italy) *Efficient Dynamic Updates of Distributed Components Through Version Consistency*

Graph Transformation Theory and Applications

Wednesday June 29, 2022, 7PM, online

**John Baez** (Department of Mathematics, University of California, Riverside, USA) *★★★ GReTA Special Event ★★★ Compositional Modeling with Decorated Cospans*

Graph Transformation Theory and Applications

Friday June 17, 2022, 3PM, online

**Davide Castelnovo** (Department of Computer Science, Mathematics and Physics, University of Udine, Italy) *A new criterion for M,N-adhesivity, with an application to hierarchical graphs*

Graph Transformation Theory and Applications

Friday June 3, 2022, 3PM, 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

Friday May 20, 2022, 3PM, online

**Roy Overbeek** (Department of Computer Science, Vrije Universiteit, Amsterdam, Netherlands) *PBPO+: A Unifiying Theory for Quasitoposes*

Graph Transformation Theory and Applications

Friday April 22, 2022, 3PM, online

**Jens Kosiol, Lars Fritsche** (Arbeitsgruppe Softwaretechnik, Philipps-Universität Marburg, Germany, Fachgebiet Echtzeitsysteme, Technische Universität Darmstadt, Germany) *Recent Developments in TGG-based Model Synchronisation*

Graph Transformation Theory and Applications

Friday March 25, 2022, 3PM, online

**Reiko Heckel** (Department of Informatics, University of Leicester, UK) *Tutorial on Graph Transformation Concepts and Applications - Part 3: Modelling, Matching and Reverse Engineering of Services with Visual Contracts*

Graph Transformation Theory and Applications

Friday March 18, 2022, 3PM, online

**Ambroise Lafont** (Department of Computer Science and Technology, University of Cambridge, UK) *A categorical diagram editor to help formalising commutation proofs*

Graph Transformation Theory and Applications

Friday March 11, 2022, 3PM, online

**Gabriele Taentzer** (Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Germany) *Tutorial on Graph Transformation Concepts and Applications - Part 2*

Graph Transformation Theory and Applications

Friday February 25, 2022, 3PM, online

**Artur Boronat** (Department of Informatics, University of Leicester, UK) *Software Reuse in Modeling Language Engineering using Structural and Behavioural Model Subtyping with OCL Constraints*

In model-driven engineering, such DSLs are engineered using abstract graphs, possibly enriched with constraints, that denote model types, and model transformation to represent their behavioural semantics, either operational or translational. In this talk, I will present the use of model subtyping with OCL constraints for facilitating verifiable software reuse when engineering DSLs, and I will illustrate the technique with different use cases.

Graph Transformation Theory and Applications

Friday February 11, 2022, 3PM, online

**Pablo Arrighi** (Université Paris-Saclay, France) *Quantum Causal Graph Dynamics*

Graph Transformation Theory and Applications

Friday January 28, 2022, 3PM, online

**William Waites** (University of Strathclyde, Scotland, UK) *Rule-based Models of Epidemics*

Graph Transformation Theory and Applications

Friday January 14, 2022, 3PM, online

**Reiko Heckel** (Department of Informatics, University of Leicester, UK) *Tutorial on Graph Transformation Concepts and Applications*

#### Year 2021

Graph Transformation Theory and Applications

Friday December 17, 2021, 3PM, online

**Paolo Bottoni** (Department of Computer Science, Sapienza University of Rome, Italy) *Request-Guarantee Agents and their Check-Transform-Enforce Processes*

Graph Transformation Theory and Applications

Friday December 3, 2021, 3PM, online

**Daniel Strüber** (Department of Computer Science and Engineering, Chalmers University of Technology, University of Gothenburg, Sweden) *Supporting Software Variability with Graph Transformations*

Graph Transformation Theory and Applications

Friday November 26, 2021, 3PM, online

**Cyril Cohen** (Inria Sophia-Antipolis Méditerranée, Sophia-Antipolis, France) *Hierarchy Builder*

HB gives the library designer a language to describe the building blocks of algebraic structures and to assemble them into a hierarchy. Similarly it provides the final user linguistic constructs to build instances (examples) of structures and to teach the elaborator of Coq how to take advantage of this knowledge during type inference. Finally HB lets the library designer improve the usability of his library by providing alternative interfaces to the primitive ones, a feature that can also be used to accommodate changes to the hierarchy without breaking user code.

This is a joint work with Kazuhiko Sakaguchi and Enrico Tassi.

Graph Transformation Theory and Applications

Friday November 19, 2021, 3PM, online

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

Graph Transformation Theory and Applications

Friday November 12, 2021, 10AM, online

**Chantal Keller** (Université Paris-Saclay, CNRS, ÉNS Paris-Saclay, Laboratoire Méthodes Formelles, Gif-sur-Yvette, France) *SMTCoq: the power of SMT solving in Coq*

* checking SMT answers, both in Coq and externally using the Coq extraction mechanism

* importing SMT problems as Coq theorems

* calling SMT solvers to ease Coq proof building, in a ongoing project called Sniper.

An API to build first-order SMTCoq terms and formulas is also under progress, in order to have an easy access to SMTCoq internal functionalities.

Graph Transformation Theory and Applications

Friday November 5, 2021, 3PM, online

**Nicolas Behr** (IRIF) *GReTA-ExACT: towards Executable Applied Category Theory*

In the first part of this talk, I will provide an illustrated tour of broad scope of mathematical concepts in modern categorical rewriting theories, ranging over the definitions of Double-Pushout (DPO) and Sesqui-Pushout (SqPO) semantics to the notions of concurrency and associativity theorems, their proofs (illustrating a particular type of diagrammatic reasoning on commutative diagrams), the theory of tracelets, their Hopf algebras and decomposition spaces, certain concepts of opfibrations and finally double-categorical structures that are currently under active investigation (joint work with Paul-André Melliès and Noam Zeilberger). In the second part of the talk, I will outline a proposal for the new GReTA-ExACT online working group format.

References:

[1] R. Heckel, L. Lambers, M.G. Saadat, “Analysis of Graph Transformation Systems: Native vs Translation-based Techniques”, EPTCS 309, 2019, pp. 1-22. http://dx.doi.org/10.4204/EPTCS.309.1

[2] N. Behr, R. Heckel, M.G. Saadat, “Efficient Computation of Graph Overlaps for Rule Composition: Theory and Z3 Prototyping”, EPTCS 330, 2020, pp. 126–144. http://dx.doi.org/10.4204/EPTCS.330.8

Graph Transformation Theory and Applications

Friday October 8, 2021, 3PM, 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

Friday September 24, 2021, 3PM, online

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

Graph Transformation Theory and Applications

Friday September 10, 2021, 3PM, online

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

Graph Transformation Theory and Applications

Friday July 16, 2021, 3PM, online

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

Graph Transformation Theory and Applications

Friday July 2, 2021, 3PM, online

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

Graph Transformation Theory and Applications

Friday June 4, 2021, 3PM, online

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

Graph Transformation Theory and Applications

Friday May 21, 2021, 3PM, 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

Friday May 7, 2021, 3PM, online

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

Graph Transformation Theory and Applications

Wednesday April 28, 2021, 6PM, 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

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

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 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 March 12, 2021, 3PM, (online)

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

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.