Termination Analysis for Graph Transformation Systems


H.J. Sander Bruggink, Barbara König, and Hans Zantema. Termination analysis for graph transformation systems. Technical report, University of Duisburg-Essen, 2014.


We introduce two techniques for proving termination of graph transformation systems. We do not fix a single initial graph, but consider arbitrary initial graphs (uniform termination), but also certain sets of initial graphs (non-uniform termination). The first technique, which can also be used to show non-uniform termination, uses a weighted type graph to assign weights to graphs. The second technique reduces uniform termination of graph transformation systems of a specific form to uniform termination of cycle rewriting, a variant of string rewriting.

Suggested BibTeX entry:

    author = {H.J. Sander Bruggink and Barbara K{\"o}nig and Hans Zantema},
    institution = {University of Duisburg-Essen},
    title = {Termination Analysis for Graph Transformation Systems},
    year = {2014}

PDF (400 kB)Conference version
© University of Duisburg-Essen, Theoretical Computer Science group