Rachid Echahed

Introduction to graph rewriting Rachid Echahed (CNRS, LIG Grenoble)

Slides of the lectures

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.