Termination analysis for graph transformation systems

H.J.S. Bruggink, B. König, H. Zantema

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)
2 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationTheoretical Computer Science (8th IFIP TC 1/WG 2.2 International Conference, TCS 2014, Rome, Italy, September 1-3, 2014. Proceedings)
EditorsJ. Diaz, I. Lanese, D. Sangiorgi
Place of PublicationBerlin
PublisherSpringer
Pages179-194
ISBN (Print)978-3-662-44601-0
DOIs
Publication statusPublished - 2014
Event8th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science; 2014-09-01; 2014-09-03 -
Duration: 1 Sep 20143 Sep 2014

Publication series

NameLecture Notes in Computer Science
Volume8705
ISSN (Print)0302-9743

Conference

Conference8th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science; 2014-09-01; 2014-09-03
Period1/09/143/09/14
Other8th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science

Cite this