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

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.


  • 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

Comments are closed.