## 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 October 6, 2023, 3PM, online

**Ryan Wisnesky** (Conexus AI, San Francisco, California, USA) *Functorial Data Migration*

Graph Transformation Theory and Applications

Friday October 20, 2023, 3PM, online

**Francesco Di Giovanni** (Department of Computer Science and Technology, University of Cambridge, UK) *On over-squashing and expressivity: can GNNs mix variables? From theory to physics-inspired solutions*

### Previous talks

#### Year 2023

Graph Transformation Theory and Applications

Friday September 22, 2023, 3PM, online

**Jens H. Weber** (Department of Computer Science, University of Victoria, Canada) *Functional Graph Programs - Foundations and Applications*

Applications of graph transformation (GT) systems often require control structures that can be used to direct GT processes. Most existing GT tools follow a stateful computational model, where a single graph is repeatedly modified “in-place” when GT rules are applied. The implementation of control structures in such tools is not trivial. Common challenges include dealing with the non-determinism inherent to rule application and transactional constraints when executing compositions of GTs, in particular atomicity and isolation. The complexity of associated transaction mechanisms and rule application search algorithms (e.g., backtracking) complicates the definition of a formal foundation for these control structures. Compared to these stateful approaches, functional graph rewriting presents a simpler (stateless) computational model, which simplifies the definition of a formal basis for (functional) GT control structures. In this talk, I will discuss the “Graph Transformation control Algebra” (GTA) as a foundation for functional graph rewriting and its application in the tool GrapeVine.

Graph Transformation Theory and Applications

Friday September 8, 2023, 3PM, online

**Malin Altenmüller** (Mathematically Structured Programming Group, University of Strathclyde, Glasgow, UK) *A Category of Surface-Embedded Graphs*

Graph Transformation Theory and Applications

Friday June 16, 2023, 3PM, online

**Dániel Varró** (Linköping University, Sweden and McGill University, Canada) *Automated generation of domain-specific graph models*

Graph Transformation Theory and Applications

Friday June 2, 2023, 3PM, online

**Fernando Orejas** (Department of Computer Science, Universitat Politècnica de Catalunya, Spain) *Unification of Drags and Confluence of Drag Rewriting*

Graph Transformation Theory and Applications

Friday May 19, 2023, 3PM, online

**David Sprunger** (Department of Mathematics and Computer Science, Indiana State University, USA) *Rewriting for Monoidal Closed Categories*

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*

Graph Transformation Theory and Applications

Friday April 21, 2023, 3PM, online et salle 146 à Olympe de Gouges

**Uwe Wolter** (Department of Informatics, University of Bergen, Norway) *A Journey from Graphs to Generalized Sketches*

We discuss why traditional Ehresmann Sketches are not fully adequate for the formalization of Software Models and argue in favor of Generalized Sketches. Ehresmann Sketches utilize only the properties commutative, limit or colimit, respectively, while we are allowed to work with arbitrary “user defined” properties in Generalized Sketches. Makkai proposed Sketch Implications as a tool to axiomatize the meaning of “user defined” properties and we elucidate that especially limit and colimit properties can be expressed by means of Sketch Implications. On the other side, we can utilize Sketch Implications as a tool to describe the structure of Software Models.

Compared to Graph Transformations, Sketch Transformations give us a more refined and expressive tool at hand to formalize Model Transformations. It looks like, however, that only the use of cospan transformation rules instead of the traditional span transformation rules would enable us to derive full advantage of sketches.

Joint event with the "Catégories supérieures, polygraphes et homotopie" workgroup

Graph Transformation Theory and Applications

Friday April 21, 2023, 2PM, online et salle 146 à Olympe de Gouges

**Uwe Wolter** (Department of Informatics, University of Bergen, Norway) *An Outline of the Theory of Generalized Sketches*

In the talk we present Generalized Sketches à la Makkai/Diskin as a quite natural generalization of traditional Ehresmann sketches. Generalized Sketches à la Makkai/Diskin can be defined in arbitrary categories. They built upon “atomic statements in context” and utilize sketch implications for axiomatization purposes. Going beyond atomic statements, we outline the definition of arbitrary first-order statements in arbitrary categories enabling us to enhance the expressiveness of Generalized Sketches. In analogy to first-order statements, we can also define arbitrary first-order sketch conditions generalizing thereby different kinds of “nested graph constraints and conditions”.

We intend to discuss, on the way, two essential constructions Makkai’s work on Generalized Sketches relies on: “Syntactic representation of models” and “internalization of atomic statements”.

Joint event with the "Catégories supérieures, polygraphes et homotopie" workgroup

Graph Transformation Theory and Applications

Friday March 24, 2023, 3PM, online

**Elvira Pino And Fernando Orejas** (Department of Computer Science, Universitat Politècnica de Catalunya, Spain) *A Logical Approach to Graph Databases*

While relational databases were designed upon logical and algebraic foundations, the development of graph databases has been quite ad-hoc. In this sense, the aim of this paper is to provide them with some logical foundations. More precisely, in previous work we introduced a navigational logic, called GNL (Graph Navigational Logic) that allows us to describe graph navigational properties, and which is equipped with a deductive tableau method that we proved to be sound and complete.

In this presentation we will introduce a new formal model for property graphs. Then, we will show how graph queries à la Cypher can be expressed using a fragment of GNL, defining for them a logical and an operational semantics, based on the inference rules for GNL. Finally, we show that both semantics are equivalent.

Graph Transformation Theory and Applications

Friday February 24, 2023, 3PM, online

**Alexandre Fernandez** (Department of Computer Science, LIP, ENS de Lyon, France) *Spatialized Synchronous Computations with Global Transformations*

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.