A tutorial on graph transformation

Barbara König, Dennis Nolte*, Julia Padberg, Arend Rensink

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

    19 Citations (Scopus)
    745 Downloads (Pure)


    Graph transformation or graph rewriting has been developed for nearly 50 years and has become a mature and manifold formal technique. Basically, rewrite rules are used to manipulate graphs. These rules are given by a left-hand side and a right-hand side graph and the application comprises matching the left-hand side and replacing it with the right-hand side of the rule. In this contribution we give a tutorial on graph transformation that explains the so-called double-pushout approach to graph transformation in a rigorous, but non-categorical way, using a gluing construction. We explicate the definitions with several small examples. We also introduce attributes and attributed graph transformation in a lightweight form. The paper is concluded by a more extensive example on a leader election protocol, the description of tool support and pointers to related work.

    Original languageEnglish
    Title of host publicationGraph Transformation, Specifications, and Nets
    Subtitle of host publicationIn Memory of Hartmut Ehrig
    EditorsReiko Heckel, Gabriele Taentzer
    Number of pages22
    ISBN (Electronic)978-3-319-75396-6
    ISBN (Print)978-3-319-75395-9
    Publication statusPublished - 7 Feb 2018

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349
    NameTheoretical Computer Science and General Issues


    • Graph transformation
    • Tutorial


    Dive into the research topics of 'A tutorial on graph transformation'. Together they form a unique fingerprint.

    Cite this