Introduction to graph rewriting
Rachid 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
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,
- 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