This presentation provides an outlook on the topological approach to spatial and spatio-temporal model checking. We introduce spatial logics, the SLCS language, and its semantics applied to various classes of models: Closure Spaces, Graphs, Polyhedra, and Posets. Additionally, we briefly discuss minimization techniques via the Hennessy-Milner property, and current implementation methods, highlighting relevant tools and applications. Special attention is given to how these techniques are used in practical domains such as imaging and 3D mesh analysis.

Zoom meeting registration link

YouTube live stream

Multilevel modeling extends traditional modeling techniques with a potentially unlimited number of abstraction levels. Multilevel models can be formally represented by multilevel typed graphs whose manipulation and transformation are carried out by multilevel typed graph transformation rules. These rules are cospans of three graphs and two inclusion graph homomorphisms where the three graphs are multilevel typed over a common typing chain. In this paper, we show that typed graph transformations can be appropriately generalized to multilevel typed graph transformations improving preciseness, flexibility and reusability of transformation rules. We identify type compatibility conditions, for rules and their matches, formulated as equations and inequations, respectively, between composed partial typing morphisms. These conditions are crucial presuppositions for the application of a rule for a match—based on a pushout and a final pullback complement construction for the underlying graphs in the category —to always provide a well-defined canonical result in the multilevel typed setting. Moreover, to formalize and analyze multilevel typing as well as to prove the necessary results, in a systematic way, we introduce the category of typing chains and typing chain morphisms.

Zoom meeting registration link

YouTube live stream

We provide a general introduction to the AlgebraicJulia ecosystem and AlgebraicRewriting.jl, which allows for integrating general-purpose code with computation of many graph transformation constructions in a broad variety of categories. Practical applications of graph transformation depend on being able to apply sequences of rewrites in a controlled manner: we present work on a graphical language for the construction and composition of such programs, including computation of normal forms as well as scientific agent-based model simulations. This graphical language can be given semantics in many different contexts (e.g. deterministic, nondeterministic, probabilistic) and can be functorially migrated, which yields graph rewriting programs that operate in other categories.

Zoom meeting registration link

YouTube live stream

Tooling is essential for practical applications in any field. For Graph Transformation, one of the ways to quickly prototype your graph-like domain is by developing a model in GROOVE, a standalone tool that will give you isomorphism checking, state space exploration, and model checking based on a graph grammar consisting of a set of (optionally typed) rules and start graph, optionally complemented with a control program.

In this second part of the tutorials on GROOVE, the following advanced features will be covered: Nested rules, rule parameters, control (functions and recipes), and model checking. Participants are invited to install a local copy of GROOVE and to download the .zip file with examples from the tutorial, which is available on the event's GReTA page.

Zoom meeting registration link

YouTube live stream

In this talk I will present the state of the research on higher-arity algebras from the perspective of (labelled) hypergraph rewriting. Recent discoveries on ternary algebras enabled by the rewriting approach will be discussed and a proposal for computational foundations of formal objects generalizing diagrammatic calculi, such us the one in category theory, will be introduced. This presentation will be done using recently developed function paclets in Mathematica.

Zoom meeting registration link

YouTube live stream

Tooling is essential for practical applications in any field. For Graph Transformation, one of the ways to quickly prototype your graph-like domain is by developing a model in GROOVE, a standalone tool that will give you isomorphism checking, state space exploration and model checking based on a graph grammar consisting of a set of (optionally typed) rules and start graph, optionally complemented with a control program.

In this talk I will show the capabilities of the tool, especially touching on the more advanced features such as nested rules, attribute manipulation, recipes (aka transactions) and various analysis techniques. Some of these are recent extensions. I am also very interested in any type of feedback regarding potential use cases and desirable features.

Zoom meeting registration link

YouTube live stream

Software interoperability is a recurring issue in nearly every bigger software project where two or more (legacy) software systems are involved. One aspect of interoperability, that is considered especially tricky is semantic interoperability, i.e., aligning the concepts, entities, data structures from multiple systems with each other. The model-driven software engineering community has investigated this issue under different names: model management, model synchronisation, inter-model consistency. From a theoretical side, there are two noteworthy common approaches: Goguen’s Colimit-approach (for general systems' theory) and Triple Graph Grammars (TGGs). The former describes that idea that one may always consider a “global integrated system” as the colimit of a diagram of interacting systems, while the latter is the foundation for a powerful framework of binary model synchronizers derived from a declarative description (grammar). In our investigation, it, however, turned out that both approaches each have significant drawback when considering them in practical applications: The colimit turns out to be a “forgetful” operation and TGGs are limited to a binary setting (it is a well-known fact from logic and databases that there are multi-ary relations that cannot be factored into a system of binary relations). Thus, we invented a novel formalism, called comprehensive systems, first introduced in [1]( https://link.springer.com/chapter/10.1007/978-3-030-45234-6_17), and theoretically flashed out in [2]( https://dl.acm.org/doi/10.1007/s00165-021-00555-2) and [3]( https://linkinghub.elsevier.com/retrieve/pii/S0304397521004059). Comprehensive systems provide an alternative to the colimit approach, which can be thought of as instead of “merging” a diagram into a singular object, they “flatten” the whole diagram. Moreover, they are designed for a general n-ary ($n \geq 2$) settings and thus can be considered as a generalization of triple graphs. In a series of papers, we have shown that comprehensive systems admit SPO and DPO rewriting in the setting of a weak adhesive HLR category. From a practical perspective, comprehensive systems serve as the theoretical foundation of a prototypical software interoperability tool called [CorrLang](https://corrlang.io).

In this talk, I will provide a brief historical overview over interoperability, model management, and model synchronisation, provide the motivation for comprehensive systems, sketch their theoretical properties (with an emphasis on partial morphisms), and, if time allows, demonstrate how comprehensive systems are reified in a concrete tool (CorrLang).

Zoom meeting registration link

YouTube live stream

The laws of Physics are time-reversible, making no qualitative distinction between the past and the future—yet we can only go towards the future. This apparent contradiction is known as the `arrow of time problem'. Its current resolution states that the future is the direction of increasing entropy. But entropy can only increase towards the future if it was low in the past, and past low entropy is a very strong assumption to make, because low entropy states are rather improbable, non-generic. Recent works from the Physics literature suggest, however, we may do away with this so-called `past hypothesis', in the presence of reversible dynamical laws featuring expansion. We prove that this is the case, for a synchronous graph rewriting-based toy model. It consists in graphs upon which particles circulate and interact according to local reversible rules. Some rules locally shrink or expand the graph. Generic states always expand; entropy always increases—thereby providing a local explanation for the arrow of time. This discrete setting allows us to deploy the full rigour of theoretical Computer Science proof techniques.·

Zoom meeting registration link

YouTube live stream

I will discuss how Message Passing Neural Networks (MPNNs) model mixing among features in a graph. I will show that MPNNs need as many layers as the commute time between nodes to model strong mixing. This allows to derive a measure for over-squashing and to clarify how the latter limits the expressivity of MPNNs to learn functions with long-range interactions. I will then discuss a novel paradigm for message-passing that determines “when” messages are being propagated based on the geometry of the data and introduces a delay mechanism to greatly enhance the power of MPNNs to capture long-range interactions achieving superior performance than Graph-Transformers even remaining sub-quadratic.

Zoom meeting registration link

YouTube live stream

In this talk we describe functorial data migration from a re-writing perspective, by way of the open-source CQL tool from categoricaldata.net. We describe how co-presheaves and their lifting problems can be finitely presented, how solving word problems in categories enables computational category theory, and some techniques for performing functorial data migration using chase algorithms.

Zoom meeting registration link

YouTube live stream

Abstract:

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.

Zoom meeting registration link

YouTube live stream

We introduce a categorical formalism for rewriting surface-embedded graphs. Such graphs can represent string diagrams in a non-symmetric setting where we guarantee that the wires do not intersect each other. The main technical novelty is a new formulation of double pushout rewriting on graphs which explicitly records the boundary of the rewrite. Using this boundary structure we can augment these graphs with a rotation system, allowing the surface topology to be incorporated.

Zoom meeting registration link

YouTube live stream

Graphs are key abstractions in science and engineering. They may represent linked data in graph databases or social networks, complex designs of cyber-physical systems, or critical validation scenarios for autonomous systems. Synthetic graph generators are essential when the use of real graph models is restricted (to respect privacy regulations or intellectual properties of companies) or impractical (to find corner-cases for safety assurance). In this talk, I will provide an overview of major challenges and recent research results on automated graph generation which aims to derive domain-specific graph models which are simultaneously consistent (CO), realistic (RE), diverse (DI) and scalable (SC). In particular, I will present a graph solver that combines advanced graph algorithms with 3-valued logic satisfiability techniques.

Zoom meeting registration link

YouTube live stream

Drags are a recent, natural generalization of terms which admit arbitrary cycles. A key aspect of drags is that they can be equipped with a composition operator so that rewriting amounts to replace a drag by another in a composition. In this paper, we develop a unification algorithm for drags that allows to check the local confluence property of a set of drag rewrite rules.

Zoom meeting registration link

YouTube live stream

Previous work has shown that string diagrams for freely generated symmetric monoidal categories can be viewed as hypergraphs with interfaces, and the axioms of these categories can be realized by rewriting systems. This work proposes hierarchical hypergraphs as a suitable formalization of string diagrams for monoidal closed categories. We then show double pushout rewriting captures the axioms of these closed categories.

Zoom meeting registration link

YouTube live stream

The transformation of graphs can be described using rules. They can also be expressed by an energy function that defines the steady state probabilities for different graph conformations. Years ago a result was obtained relating graph energy functions and systems of graph transformation rules. Implementating the algorithm that takes an energy function and generates the corresponding rules showed us that other options were also available, that is, that different algorithms could produce different systems of graph transformation rules for the same energy function. We wonder, then, what is the relationship between theses algorithms and why it would be preferable to use one or the other.

Zoom meeting registration link

YouTube live stream

In the talk we present the Generalized Sketch Formalism à la Makkai/Diskin as a straightforward and quite natural generalization of specification formalisms based on graphs and graph transformations.

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.

Zoom meeting registration link

YouTube live stream

Based on a new concept of first-order generalized sketches we coined lately “Logics of Statements in Context” to provide a unified view on formalisms like Algebraic Specifications, Prolog, First-Order Logic, Ehresmann Sketches, Description Logics, Generalized Sketches à la Makkai/Diskin, Diagram Predicate Framework, Graph Conditions, and others.

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

Zoom meeting registration link

YouTube live stream

Graph databases are now playing an important role because they allow us to overcome some limitations of relational databases. In particular, graph databases differ from relational databases in that the topology of data is as important as the data itself. Thus, typical graph database queries are navigational, asking whether some nodes are connected by paths satisfying some specific properties.

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.

Zoom meeting registration link

YouTube live stream

This presentation outlines some ideas of my PhD about Global Transformations. These form a general method to describe local and synchronous spatialized dynamical systems such as Cellular Automata and Lindenmayer systems. This work originated from the goal of extending such systems to dynamical graphs. This talk first introduces the categorical formalism, and providing examples of such systems over different structures such as words or graphs. It also give simple instances of many categorical constructions, such as comma categories, colimits and Kan extensions. These tools are then used to relate the local specification of a system and its global behavior. The extension of this formalism to non-deterministic computations is finally considered.

Zoom meeting registration link

YouTube live stream

Domain-specific modelling languages (DSMLs) are “little” languages that are developed for a particular domain of interest and allow capturing descriptions of problems and systems in terminology close to that domain. So-called executable DSMLs (xDSMLs) come with a high-level specification of their semantics, often as an operational semantics, so that models expressed in the xDSML can be executed directly. Graph transformations are one mechanism that can be used to capture such semantics. A challenge with xDSMLs is that a new such language needs to be developed for every new domain, making the approach potentially costly. If we were able to better reuse existing xDSMLs, we could bring the cost of language development down. One area where this is particularly interesting is in the specification and analysis of non-functional properties of systems (eg, performance properties). In this talk, I will show how such properties can be modularised into their own xDSML and how these language modules can be woven into a given base xDSML via the amalgamation of graph transformation systems. I will give an overview of the concepts and some interesting properties, and will then show GTSMorpher, a tool implementing these ideas in the Eclipse ecosystem.

Zoom meeting registration link

YouTube live stream

The seminar gives a very short introduction of gothic churches (the historical and cultural part) and their virtual construction (the CAAD part). The main section shows that about 800 years ago intelligent design principles (algorithmic and parametric design) and reuse techniques (product and process reuse, classes of systems, domain knowledge, agile development) have been used in the design of gothic cathedrals. Two examples, the cathedrals of Reims and York, are discussed in more detail. There are even relations to graph rewriting which, however, are only touched.

Zoom meeting registration link

YouTube live stream

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

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

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

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

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

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

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

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

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

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

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

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

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

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

We introduce Check-Transfer-Enforce Systems (CTEs) as a general model of behavior of (semi-)autonomous agents, based on the idea of distinguishing the ability of an agent to change its state from the actual changes that can be performed under contextual constraints. In this model, based on many-sorted term algebras, a Request-Guarantee (qg)-agent is characterised by a collection of moves specifying which terms are requested to be present in the current state of the agents and which terms are guaranteed to be present in the successor state, if the move is executed. We show how this approach allows an encoding and a generalisation of a number of well-known existing models. The approach is naturally extended to the case of pairs of communicating qg-agents. An abstract view of the approach can be given in the setting of enriched categories.

Zoom meeting registration link

YouTube live stream

Software systems and the artifacts they consist of often exist in many different variants. When creating new variants, developers typically rely on the “clone and own” strategy of copying and modifying existing variants, a simple and intuitive approach with significant long-term disadvantages. In this talk, I present a line of work on supporting variants in software engineering by explicitly addressing variability as a feature in graph transformations. I focus on three transformation scenarios: one where the input graph has variability (representing the established notion of a software product line), one where rules have variability (leading to variability-based rules), and a combination of the first two scenarios. Each scenario is supported with formal constructions, efficient transformation algorithms, and tool support. Our work shows that a systematic way of supporting variability in transformations can improve the maintainability and the performance of a software system.

Zoom meeting registration link

YouTube live stream

Libraries of machine checked code are, nowadays, organized around hierarchies of algebraic structures. Unfortunately the language of Type Theory and the features provided by the Coq system make the construction of a hierarchy hard even for expert users. The difficulty begins with the non-orthogonal choices, between storing information as record fields or parameters, and between using type classes and canonical structures for inference. To this, one may add the concerns about performance and about the usability, by a non expert, of the final hierarchy.

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.

Zoom meeting registration link

YouTube live stream

Computational notebooks (CNs) have gained popularity in data science, artificial intelligence, and engineering. CNs are used to document experiments and make them repeatable by incorporating executable segments and renderings of computational results. Unfortunately, computations by graph transformations are not supported by current CNs. In order to close this gap, we have developed GRAPEPress, a tool that combines the GRAPE graph transformation language with the CN tool Gorilla. This talk introduces the GRAPE language as well as its integration with the CN tool Gorilla.

Zoom meeting registration link

YouTube live stream

SMTCoq is a tool to make the Coq proof assistant and SMT solvers cooperate, with the same degree of confidence as Coq. In this talk, I will give an overview of its potential:

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

Zoom meeting registration link

YouTube live stream

This talk marks the beginning of GReTA-ExACT, a new online working group within the GReTA community. The aim of this working group will consist in providing an interdisciplinary forum for exploring the diverse aspects of applied category theory relevant in graph transformation systems and their generalizations, in developing a methodology for formalizing diagrammatic proofs as relevant in rewriting theories via proof assistants such as Coq, and in establishing a community-driven wiki system and repository for mathematical knowledge in our research field (akin to a domain-specific Coq-enabled variant of the nLab). A further research question will consist in exploring the possibility for deriving reference prototype implementations of concrete rewriting systems (e.g., over multi- or simple directed graphs) directly from the category-theoretical semantics, in the spirit of the translation-based approaches as in [1],[2] (utilizing theorem provers such as Microsoft Z3).

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

Zoom meeting registration link

YouTube live stream

This event will consist of two talks: “Investigating claimed Advantages and Disadvantages of Model Transformation Languages” (by Stefan Höppner) and “Current State of Performance Engineering of Model Transformations” (by Raffaela Groner). Please refer to https://www.irif.fr/~greta/event/2021-oct-08 for the respective abstracts.

Zoom meeting registration link

YouTube live stream

In the first part of the talk, I will present generalized maps that represent quasi-manifolds through their subdivision into topological cells (vertices,edges, faces, volumes). We defined generalized maps as constrained labeled graphs. Arc labels encode topological relations of the subparts modeled object while node labels describe the geometric data used to represent the object. Modeling operations are designed regardless of the object's underlying topology. Therefore, we generalize DPO rules with a functorial approach to encode semi-global relabeling with a product operation. Rules and their extensions (called rule schemes) are considered valid if any application to a well-formed graph results in an equally well-formed graph. We provide set-theoric conditions on rules and rule schemes to ensure the preservation of the model consistency. In the second part of the talk, I will present how this approach allows the design of geometric modelers (software used to create and edit geometric objects) in Jerboa. The set-theoric conditions can be checked via graph traversal in Jerboa's rule editor to ensure that the code derived from the rule will never break the model. The generated code can be used as an add-on in other software or Jerboa's generic viewer. 

Zoom meeting registration link

YouTube live stream

Reverse-mode automatic differentiation, especially in the presence of complex language features, is notoriously hard to implement correctly, and most implementations focus on differentiating straight-line imperative first-order code. Generalisations exist, however, that can tackle more advanced features; for example, the algorithm described by Pearlmutter and Siskind in their 2008 paper can differentiate higher-order functions written in a pure functional language. We show that AD algorithms can benefit enormously from being translated into the language of string diagrams in two steps: first, we describe a Pearlmutter-Siskind style AD algorithm as a set of rules for transforming hierarchical graphs; rules which can -and indeed have been- be implemented correctly and efficiently for a non-trivial language. Then, we present a proof of soundness for it by reducing the above rewrite rules to a suitable graphical version of the axioms of Cartesian reverse differential categories, expressed as string diagrams.

Zoom meeting registration link

YouTube live stream

Quantum circuits give a de facto “assembly language” for quantum computation. Hence, the design, optimisation, and verification of quantum circuits is an important task in developing efficient, correct software to run on quantum computers. In this talk, I will survey some of the latest developments in applying the ZX-calculus - a graphical theory of interacting quantum processes - to three important problems in quantum software: the optimisation of quantum circuits, functional verification of circuits, and development of heuristics for efficient classical simulation.

Zoom registration

YouTube live stream

A celebrated theorem of Chandra and Merlin states that Conjunctive Queries inclusion is decidable. Its proof transforms logical formulas to hypergraphs: each query has a natural model – a kind of graph – and query inclusion reduces to the existence of a graph homomorphism between natural models. In this talk, we introduce the diagrammatic language Graphical Conjunctive Queries (GCQ) and show that it has the same expressivity as Conjunctive Queries. GCQ terms are string diagrams, and their algebraic structure allows us to derive a sound and complete axiomatisation of query inclusion, which turns out to be exactly Carboni and Walters’ notion of cartesian bicategory of relations. Our completeness proof exploits the combinatorial nature of string diagrams as (certain cospans of) hypergraphs: Chandra and Merlin’s insights inspire a theorem that relates such cospans with spans. Completeness and decidability of the (in)equational theory of GCQ follow as a corollary. Categorically speaking, our contribution is a model-theoretic completeness theorem of free cartesian bicategories (on a relational signature) for the category of sets and relations.

Zoom registration

YouTube live stream

We propose an abstract notion of networks of exchanges modelling the global money market of decentralised finance. We formalise routing and arbitrage on such networks as convex optimisation problems. We provide bounds with closed formulas in the specific case of “constant product” automated markets and a restricted form of cyclic arbitrage. We compute the associated lower bounds on actual data derived from the Ethereum blockchain. (joint work with Hamza El Khalloufi and Julien Prat)

Zoom registration

YouTube live stream

Graph rewriting systems are naturally endowed with a notion of parallelism due to the locality of the effect of rules. These aspects have been studied in the classical theory from an interleaving perspective, based on sequential independence, shift equivalence and related notions. In the last three decades the theory has been enriched with notions, constructions and results which provide a direct account of causality and non-determinism in graph derivations, borrowed from (and extending) the theory of Petri Nets. In the talk I will present a personal overview of the development of this theory starting from the basic structural relation between nets and graph rewriting systems, and I will survey some more recent developments.

Zoom registration

YouTube live stream

A vast swath of computation and computer science theory takes place on combinatorial data structures, which are often presented as variations on the theme of graphs. Catlab.jl is a Julia package for computational category theory, which includes an implementation of C-Sets, also known as copresheafs or category actions. C-Sets always form an adhesive category and can be used for general rewriting systems. This talk will present the theory and implementation of C-Sets along with some examples. In particular, Colored Graphs and String Diagrams (syntax for symmetric monoidal categories) will be shown.

Zoom registration

YouTube live stream

About the speaker:

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.

Zoom registration

YouTube live stream

String diagrams are an elegant, convenient and powerful syntax for arrows of symmetric monoidal categories. In recent years, they have been used as compositional descriptions of computational systems from various fields, including quantum foundations, linear algebra, control theory, automata theory, concurrency theory, and even linguistics. All of these applications rely on diagrammatic reasoning, which is to string diagrams as equational reasoning is to ordinary terms.

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

YouTube recording

This talk will summarize some recent results obtained in connection with the Wolfram Physics Project: a systematic attempt to reduce fundamental physics to the problem of hypergraph rewriting. Specifically, we will discuss the construction of an efficient hypergraph rewriting scheme using the formalism of Wolfram model multiway systems, with a categorical semantics defined via double-pushout rewrites over selective adhesive categories, and equipped with a dagger-symmetric monoidal structure that exhibits surprising formal connections to categorical quantum mechanics. We will also demonstrate that, by equipping such a multiway system with an additional notion of causal structure (defined via the semantics of precausal categories), we are able to introduce new inference rules of selective resolution, paramodulation and factoring that generalize the standard Knuth-Bendix completion rules for term rewriting systems, and significantly improve the efficiency of automated diagrammatic reasoning algorithms over hypergraphs. Time permitting, we will discuss some near-term practical applications of these methods for quantum information theory (allowing for more efficient diagrammatic simplification of quantum circuits), as well as numerical general relativity (allowing for more explicit numerical simulation of graph-theoretic models of space and time).

YouTube recording

In the first part of the presentation, some aspects of formal graph language theory are discussed. A few variants of graph grammars were introduced in the early 1970s as generalizations of Chomsky grammars. This first step into a formal graph language theory was further developed by the investigation of edge and hyperedge replacement on one hand and on some variants of node replacement on the other hand starting in the late 1970s. Since then, a good number of structural and decidability properties were proved. In particular, it turned out that hyperedge replacement grammars behave to a large degree in a context-free manner. In the second part of the presentation, the novel approach of fusion grammars is surveyed.

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.

YouTube live stream recording

Double Pushout (DPO) rewriting, the dominant model for graph rewriting, emerged in the early 70’s, strongly influenced at that time by graph grammars. Developed by Hartmut Ehrig and his many collaborators, graph rewriting was from the beginning based on category theory, with the major insight that the two basic rewriting constructions, namely matching and replacement, were intimately related to graph morphisms and their pushouts. A new model has emerged recently, so-called Composition based rewriting (Core), in which rewriting is based on a composition operator over directed rooted labelled graphs (drags), so that matching a drag G against a drag L amounts to compose L with some context drag C, and rewriting G with L → R to compose R with C. We will describe Core for drags before to relate it precisely to DPO and extend it to adhesive categories of graphs and beyond. We will also show how to define composition abstractly in any category of graphs satisfying appropriate properties among which adhesivity (wrt monomorphisms). Major differences between DPO and Core will be discussed.

YouTube live stream recording

This will be an overview of our ongoing work on fast graph programs in the language GP 2. We will present programs which in some cases match the time complexity of graph algorithms in imperative languages. In other cases we need to assume that input graphs have a bounded degree, to reach the speed of conventional algorithms.

YouTube live stream recording

An overview presentation of the work we have been doing over the past years on MDEOptimiser, a tool that uses evolutionary search over EMF models to solve multi-objective optimisation problems. Graph transformations are used to encode mutation operators, opening interesting opportunities for automatically generating domain-specific mutation operators.

YouTube live recording

Confluence has been studied for graph transformation since several decades now. Confluence analysis has been applied, for example, to determining uniqueness of model transformation results in model-driven engineering. It is strongly related to conflict analysis for graph transformation, i.e. detecting and inspecting all possible conflicts that may occur for a given set of graph transformation rules. The latter finds applications, for example, in software analysis and design. Both conflict and confluence analysis rely on the existence and further analysis of a finite and representative set of conflicts for a given set of graph transformation rules.

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.

YouTube live recording of the seminar

Program transformations are frequently developed, e.g., to realize programming language extensions or dynamic program analyses such as profiling. They are typically implemented by manipulating bytecode as the availability of source code is not guaranteed. There are standard libraries such as ASM that are typically used for implementing Java bytecode manipulations. To check their correctness, they are usually tested by applying them to different programs, running the manipulated programs and observing their behaviors. As part of the second step, the Java virtual machine verifies the bytecode, which can uncover errors in the bytecode introduced by the manipulation. That approach uses different technologies that are not well linked making the process of developing and testing bytecode manipulations difficult. In this talk, we intend to perform bytecode manipulation by using concepts and techniques of model-driven engineering. We are convinced that the declarative nature of model transformation rules allows the debugging and analyzing of bytecode manipulations in more details than classically done. Following this path, a meta-model for bytecode is needed including OCL constraints for bytecode verification. We show that basing bytecode manipulation on model transformation can provide more immediate guidance and feedback to the developer, especially when model transformation is formally based on graph transformation. Bytecode verification can take place directly in the manipulated model with the help of OCL checking, eliminating the need to use multiple technologies. In some cases, it is even possible to automatically determine application conditions under which bytecode manipulations are correct by construction; then bytecode verification after a bytecode manipulation can be avoided altogether.

YouTube live recording of the seminar

Graph rewriting systems are natural verification and validation tools: they provide visual, intuitive representations of complex systems while specifying the dynamic behaviour of the system in a formal way. In this talk we will describe the use of strategic port graph rewriting as a basis for the implementation of a visual modelling tool: PORGY. We will present attributed hierarchical port graphs (AHP) and a notion of strategic AHP-rewriting as a mechanism to model the behaviour of dynamic systems. The system modelled is represented by an initial graph and a collection of graph rewrite rules, together with a user-defined strategy to control the application of rules. The traditional operators found in strategy languages for term rewriting have been adapted to deal with the more general setting of graph rewriting, and some new constructs have been included in the strategy language to deal with graph traversal and management of rewriting positions in the graph. In the second part of the talk, we describe PORGY and give examples of application in the areas of biochemistry, social networks and finance.

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

YouTube live recording of the seminar

Any computational method in chemistry must choose some level of precision in the modeling. One choice is made in the methods of quantum chemistry based on quantum field theory. While highly accurate, the methods are computationally very demanding, which restricts their practical use to single reactions of molecules of moderate size even when run on supercomputers. At the same time, most existing computational methods for systems chemistry and biology are formulated at the other abstraction extreme, in which the structure of molecules is represented either not at all or in a very rudimentary fashion that does not permit the tracking of individual atoms across a series of reactions.

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.

video recording of the seminar on YouTube

We review the integration of (first-order) logic respectively nested conditions into graph transformation. Conditions can serve various purposes: they can constrain graph rewriting, symbolically specify sets of graphs, be used in query languages and in verification (for instance in Hoare logic and for behavioural equivalence checking).

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.

video recording of the seminar on YouTube