A tutorial on graph transformation

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

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

1 Citation (Scopus)
9 Downloads (Pure)

Abstract

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
PublisherSpringer
Pages83-104
Number of pages22
ISBN (Electronic)978-3-319-75396-6
ISBN (Print)978-3-319-75395-9
DOIs
Publication statusE-pub ahead of print/First online - 7 Feb 2018

Publication series

NameLecture Notes in Computer Science
Volume10800
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Gluing
Graph Transformation
Graph Rewriting
Leader Election
Tool Support
Graph in graph theory
Attribute

Keywords

  • Graph Transformation
  • Tutorial

Cite this

König, B., Nolte, D., Padberg, J., & Rensink, A. (2018). A tutorial on graph transformation. In R. Heckel, & G. Taentzer (Eds.), Graph Transformation, Specifications, and Nets: In Memory of Hartmut Ehrig (pp. 83-104). (Lecture Notes in Computer Science; Vol. 10800). Springer. https://doi.org/10.1007/978-3-319-75396-6_5
König, Barbara ; Nolte, Dennis ; Padberg, Julia ; Rensink, Arend. / A tutorial on graph transformation. Graph Transformation, Specifications, and Nets: In Memory of Hartmut Ehrig. editor / Reiko Heckel ; Gabriele Taentzer. Springer, 2018. pp. 83-104 (Lecture Notes in Computer Science).
@inbook{67972571644442c0bf6e1f8a90aeb169,
title = "A tutorial on graph transformation",
abstract = "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.",
keywords = "Graph Transformation, Tutorial",
author = "Barbara K{\"o}nig and Dennis Nolte and Julia Padberg and Arend Rensink",
year = "2018",
month = "2",
day = "7",
doi = "10.1007/978-3-319-75396-6_5",
language = "English",
isbn = "978-3-319-75395-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "83--104",
editor = "Reiko Heckel and Gabriele Taentzer",
booktitle = "Graph Transformation, Specifications, and Nets",

}

König, B, Nolte, D, Padberg, J & Rensink, A 2018, A tutorial on graph transformation. in R Heckel & G Taentzer (eds), Graph Transformation, Specifications, and Nets: In Memory of Hartmut Ehrig. Lecture Notes in Computer Science, vol. 10800, Springer, pp. 83-104. https://doi.org/10.1007/978-3-319-75396-6_5

A tutorial on graph transformation. / König, Barbara; Nolte, Dennis; Padberg, Julia; Rensink, Arend.

Graph Transformation, Specifications, and Nets: In Memory of Hartmut Ehrig. ed. / Reiko Heckel; Gabriele Taentzer. Springer, 2018. p. 83-104 (Lecture Notes in Computer Science; Vol. 10800).

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

TY - CHAP

T1 - A tutorial on graph transformation

AU - König, Barbara

AU - Nolte, Dennis

AU - Padberg, Julia

AU - Rensink, Arend

PY - 2018/2/7

Y1 - 2018/2/7

N2 - 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.

AB - 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.

KW - Graph Transformation

KW - Tutorial

UR - http://www.scopus.com/inward/record.url?scp=85041850755&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-75396-6_5

DO - 10.1007/978-3-319-75396-6_5

M3 - Chapter

SN - 978-3-319-75395-9

T3 - Lecture Notes in Computer Science

SP - 83

EP - 104

BT - Graph Transformation, Specifications, and Nets

A2 - Heckel, Reiko

A2 - Taentzer, Gabriele

PB - Springer

ER -

König B, Nolte D, Padberg J, Rensink A. A tutorial on graph transformation. In Heckel R, Taentzer G, editors, Graph Transformation, Specifications, and Nets: In Memory of Hartmut Ehrig. Springer. 2018. p. 83-104. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-75396-6_5