GReTA seminar #8: "Composition-based Graph Rewriting"

Описание: Speaker: Jean-Pierre Jouannaud (Laboratoire d'Informatique (LIX), École Polytechnique, Palaiseau, France)

Abstract:

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.


About the GReTA seminars:

The GReTA – Graph TRansformation Theory and Applications virtual seminar series aims to serve as a platform for the international graph rewriting community, to promote recent developments and trends in the field, and to permit a regular networking and interaction between members of this community. Seminars are held twice a month in the form of Zoom sessions (some of which will be live-streamed to YouTube). Please refer to http://www.irif.fr/~greta for further details (including information on how to register for participating in the Zoom meetings).