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