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 transformations that change a graph while preserving consistency wrt a given set of constraints are an important type of transformation in many areas. For example, in search-based optimisation over graphs, aiming to find graph structures (e.g., models) that are optimal wrt some given objective functions, we need to be able to make changes to a graph without introducing violations of consistency constraints so that we can ensure to only generate feasible solutions. However, writing graph-transformation rules that ensure consistency-preservation while still allowing change to the graph is difficult: A change to the graph may introduce a constraint violation and, therefore, the rule must include components that repair any such new violations. Any such repair has the potential to introduce new constraint violations itself and, therefore, the number of potential repair paths to follow can quickly explode exponentially in size. In this talk, I present work addressing these challenges in the context of optimal product-line configuration. We introduce a new data structure – feature-activation diagrams – to capture the dependencies between changes and use this to efficiently derive consistency-preserving graph transformation rules encoded as variability-based rules. The rules we generate allow us to solve existing benchmarks for product-line configuration more efficiently than the state of the art and find more optimal configurations. Zoom meeting registration link YouTube live stream 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 The Digital Asset Modelling Language (DAML) enables low-code development of smart contract applications. Starting from a high-level but textual notation, DAML thus implements the lower end of a model-driven development process, from a platform-specific level to implementations on a range of blockchain platforms. We develop a notation based on class diagrams and visual contracts that map directly to DAML smart contracts. The approach supports an operational semantics in terms of graph transformation systems to capture the complex behavioural features of DAML, such as its role-based access control and the order of contract execution and archival. We use the Doodle case study from a DAML tutorial to introduce the mappings between DAML, visual models, and operational semantics. To implement, explore and analyse the operational semantics of the case study we present the graph transformation tool Groove, originally developed by Arend Rensink and his students to support the verification of object-oriented programs. It has since been employed to analyse a range of models, for P2P networks, workflows, component configurations, etc. Our use of Groove for the semantic underpinning and analysis of DAML follows its original purpose of program verification. We will use the opportunity to discuss Groove’s features and illustrate its use for creating and analysing graph transformation systems. Zoom meeting registration link YouTube live stream 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 Modern component-based distributed software systems are increasingly required to offer non-stop service and thus their updates must be carried out at runtime. Different authors have already proposed solutions for the safe management of dynamic updates. Our contribution aims at improving their efficiency without compromising safety. We propose a new criterion, called version consistency, which defines when a dynamic update can be safely and efficiently applied to the components that execute distributed transactions. Version consistency ensures that distributed transactions be served as if they were operated on a single coherent version of the system despite possible concurrent updates. The paper presents a distributed algorithm for checking version consistency efficiently, formalizes the proposed approach by means of a graph transformation system, and verifies its correctness through model checking. The paper also presents CONUP, a novel prototype framework that supports the approach and offers a viable, concrete solution for the use of version consistency. Both the approach and CONUP are evaluated on a significant third-party application. Obtained results witness the benefits of the proposed solution with respect to both timeliness and disruption. Zoom meeting registration link YouTube live stream 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 Decorated cospans are a general framework for composing open networks and mapping them to dynamical systems. We explain this framework and illustrate it with the example of stock and flow diagrams. These diagrams are widely used in epidemiology to model the dynamics of populations. Although tools already exist for building these diagrams and simulating the systems they describe, we have created a new software package called StockFlow which uses decorated cospans to overcome some limitations of existing software. Our approach cleanly separates the syntax of stock and flow diagrams from the semantics they can be assigned. We have implemented a semantics where stock and flow diagrams are mapped to ordinary differential equations, although others are possible. We illustrate this with code in StockFlow that implements a simplified version of a COVID-19 model used in Canada. This is joint work with Xiaoyan Li, Sophie Libkind, Nathaniel Osgood and Evan Patterson. Zoom meeting registration link YouTube live stream 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 The introduction of adhesive categories marked a watershed moment for the algebraic approaches to the rewriting of graph-like structures, as they provide an abstract framework where many general results can be recast and uniformly proved. However, checking that a category satisfies the adhesivity properties is sometimes far from immediate. In this talk we present a new criterion giving a sufficient condition for M,N-adhesivity, a generalisation of the original notion of adhesivity. We apply it to several existing categories, and in particular to hierarchical graphs, a formalism that is notoriously difficult to fit in the mould of algebraic approaches to rewriting and for which various alternative definitions float around. Zoom meeting registration link YouTube live stream 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 Graph transformation allows to extend formal language theory to the generation of graph languages. This has applications in areas such as model-driven software engineering, natural language processing, and shape analysis of programs. 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. Zoom meeting registration link YouTube live stream 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 Last year we proposed PBPO+, which extends the Pullback-Pushout (PBPO) approach by Corradini et al. with strong matching. Now, we have proved that in the setting of quasitoposes (and assuming regular monic matching), PBPO+ can define all rewrite relations definable by PBPO, AGREE, SqPO and DPO – as well as additional ones. In this sense, PBPO+ can be considered a unifying theory in this setting. In this talk we reflect on the notion of a quasitopos, and explain how from its many nice properties our result can be obtained. This is joint work with Jörg Endrullis and Aloïs Rosset. Zoom meeting registration link YouTube live stream 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 This talk will present recent results in the area of sequential and concurrent model synchronisations based on Triple Graph Grammars (TGGs). Sequential model synchronisation is the task of propagating information from one model to another. In contrast, in the concurrent case, both models have been modified independently from each other and conflicts may arise such that synchronization may additionally comprise the non-trivial task of conflict resolution. We will present our newly developed approaches for both synchronization scenarios. Their central qualities are that they have a solid formal foundation in the theory of algebraic graph rewriting and work far more incremental then previous approaches. In the first part, we will introduce TGGs and discuss a new concept for TGG-based concurrent model synchronisation. The second part of this talk will in particular stress the theoretical advances that allowed us to develop our approaches and illustrate the key ideas of the synchronization algorithms using non-trivial examples. Zoom meeting registration link YouTube live stream 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 This is the 3rd in a series of tutorials based on the book on /Graph Transformation for Software Engineers/ co-authored with Gabi Taentzer at the University of Marburg. The first tutorial in this series introduced the fundamental concepts and notations based on Part 1 of the book. The second tutorial provided an overview of the applications in Part 2 and covered in more detail the detection of inconsistent functional requirements, In this third tutorial we will focus on the use of graph transformation rules as /visual contracts/, to model services from both a provider’s and requester’s point of view, and match required with provided services. We also describe how to reverse engineer visual contracts from service implementations in Java. The book is available to buy from Springer and a free pdf copy can be found at the authors’ website. Zoom meeting registration link YouTube live stream 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 I will present a categorical diagram editor (https://amblafont.github.io/graph-editor/index.html) implemented in Elm that generates Coq proof scripts (based on the UniMath library), letting the user prove manually commutation of each subdiagram. Conversely, the editor can parse a Coq goal stating equality between two composition of morphisms and generate a diagram out of it. Zoom meeting registration link YouTube live stream 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 This tutorial will be based on the book on “Graph Transformation for Software Engineers” co-authored with Reiko Heckel, University of Leicester, appeared at Springer in 2020. It is the first textbook that explains the most commonly used concepts, notations, techniques and applications of graph transformation in general, broadly accessible terms, without focusing on one particular mathematical representation or implementation approach. While the first part of the book introduces into the fundamentals in a precise, yet informal way, aiming to provides a comprehensive and systematic survey of the concepts, notations and techniques of graph transformation, the second part presents and discusses a range of applications to both model-based software engineering and domain-specific language engineering. The variety of these applications demonstrate how broadly graphs and graph transformations can be used to model, analyse and implement complex software systems and languages. The second part of this tutorial gives an overview of all the applications presented in the book and presents one topic, the detecting of inconsistent requirements, in more detail. The book is available from [Springer](https://link.springer.com/book/10.1007/978-3-030-43916-3), and a free authors' copy is available [here](http://graph-transformation-for-software-engineers.org/). Zoom meeting registration link YouTube live stream 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 Low-code and no-code software development epitomize current approaches to reuse-based software engineering, where software systems are designed using domain-specific languages (DSLs) so that they can be readily deployed on the cloud as a service, with little or no traditional coding required. However, the engineering of low-code software development platforms themselves is a complex task and verifying that they are built correctly is a challenge. 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. Zoom meeting registration link YouTube live stream Graph Transformation Theory and Applications Friday February 11, 2022, 3PM, online Pablo Arrighi (Université Paris-Saclay, France) Quantum Causal Graph Dynamics Suppose that an entire graph evolves quantum mechanically and gets driven into superpositions of graphs of different connectivities and node populations. Suppose moreover that the evolution is causal, meaning that information can only propagate at a bounded speed, with respect to graph distance. We show that this quantum evolution must decompose into small, local unitary rewritings of graph disks. This unifies a result on Quantum Cellular Automata with another on Reversible Causal Graph Dynamics. To reach the result we formalize a notion of causality which is valid in the context of quantum superpositions of time-varying graphs, and has a number of good properties. References: 1, 2, 3 Zoom meeting registration link YouTube live stream Graph Transformation Theory and Applications Friday January 28, 2022, 3PM, online William Waites (University of Strathclyde, Scotland, UK) Rule-based Models of Epidemics Rule-based models, a particular kind of graph rewriting system initially intended for use in molecular biology, are conspicuously useful for understanding epidemics. They enable formulation of complex processes that blends the ease of understanding of “compartmental” models with the expressiveness of individual- or agent-based models. We illustrate this with a story, told in graph rewriting rules, of how the adaptive immune response to a pathogen works (simplified version) and how this response influences the population level dynamics of an epidemic. This model can be calibrated against real-world data and we see how some of the individual heterogeneity that is normally treated phenomenologically in the study of epidemics arises naturally from this account of immune response. Zoom meeting registration link YouTube live stream 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 The tutorial will be based on the book on “Graph Transformation for Software Engineers” co-authored with Gabriele Taentzer at Philipps-Universität Marburg appeared at Springer last year. It is the first textbook that explains the most commonly used concepts, notations, techniques and applications of graph transformation in general, broadly accessible terms, without focusing on one particular mathematical representation or implementation approach. In this spirit, the talk will cover the fundamentals in a precise, yet informal way, aiming to provides a comprehensive and systematic survey of the concepts, notations and techniques of graph transformation. The second part presents and discusses a range of applications to both model-based software engineering and domain-specific language engineering. The variety of these applications demonstrate how broadly graphs and graph transformations can be used to model, analyse and implement complex software systems and languages. The book is available from Springer, and a free authors' copy is available here. Zoom meeting registration link YouTube live stream