## Introduction to graph rewritingRachid Echahed (CNRS, LIG Grenoble) |

Rewriting techniques constitute a foundational theory of computing

science. They are being investigated for several structures, such as

first-order or lambda terms, strings or graphs, and have been

successfully used in many areas. Graph structures play an important

role in different scientific domains such as compu- ter science,

chemistry, physics, mathematics, natural science etc. Their pictorial

aspect makes them a very attractive and intuitive modeling

language. Compu- ting with graphs as first-class objects requires

mastering the transformation of their structures. In contrast to term

rewriting, there is no clear consensus yet on the way graph

transformations could be defined and handled. The aim of this lecture

is to give a brief overview of the approaches used to rewrite graph

structures.

**Outline of the lecture**

- Preliminary definitions. Some basic notions, not often used is

term rewriting, such as pushout and pullback will be introduced in

order to make the lecture self-contained. - Graph rewrite rules : Algebraic approaches. There are several

approaches to graph rewriting. Algebraic approaches will be discussed

first. The example of Double-Pushout rewriting will be presented and

illustrated through some examples. Other algebraic approaches will be

discussed (e.g., SeqPO or PBPO). - Graph rewrite rules : Algorithmic approaches. In a second time, an

algorithmic approach to graph rewriting based on elementary actions

will be defined and illustrated through some examples. The particular

case of TERMGRAPH-rewriting will be discussed. - Verification of Graph Rewrite Systems. Equational reasoning and

structural induction constitute basic techniques to reason about

first-order term rewrite systems. There is no clear counterpart of

such techniques in the case of graph rewriting. Some proposals towards

reasoning on graph rewriting will be discussed.

**References**

- Hartmut Ehrig, Karsten Ehrig, Ulrike Prange, Gabriele Taentzer :

Fundamentals of Algebraic Graph Transformation. Monographs in

Theoretical Computer Science. An EATCS Series, Springer 2006, ISBN

978-3-540-31187-4, pp. I-XIII, 1-390. - Grzegorz Rozenberg : Handbook of Graph Grammars and Computing by

Graph Transformations, Volume 1 : Foundations. World Scientific 1997,

ISBN 9810228848. - H. Ehrig, G. Engels, H.-J. Kreowski and G. Rozenberg : Handbook of

Graph Grammars and Computing by Graph Transformation, Volume 2 :

Applications, Languages and Tools. World Scientific 1999, ISBN

978-981-02-4020-2.