Composition-based Graph Rewriting


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.

(Joint work with Nachum Dershowitz and Fernando Orejas)

Friday, March 12, 2021 15:00 Europe/Paris
GReTA seminar
Jean-Pierre Jouannaud
Jean-Pierre Jouannaud
Professor Emeritus of Computer Science

Jean-Pierre Jouannaud is a French computer scientist, known for his work in the area of term rewriting. He was born on 21 May 1947 in Aix-les-Bains (France). From 1967 to 1969 he visited the Ecole Polytechnique (Paris). In 1970, 1972, and 1977, he wrote his Master thesis (DEA), PhD thesis (Thèse de 3ème cycle), and Habilitation thesis (Thèse d’état), respectively, at the Université de Paris VI. In 1979, he became an associate professor at the Nancy University; 1985 he changed to the Université de Paris-Sud, where he became a full professor in 1986.

He was member of the steering committee of several international computer science conferences: International Conference on Rewriting Techniques and Applications (RTA) 1989-1994, IEEE Symposium on Logic in Computer Science (LICS) 1993-1997, Conference for Computer Science Logic (CSL) 1993-1997, International Conference on Principles and Practice of Constraint Programming (CP) since 1994, and Federated Logic Conference (FLoC) 1995-1999. Since 1997, he is member of the EATCS council.