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.
https://hal.inria.fr/hal-01402041 Contributor : Hal IfipConnect in order to contact the contributor Submitted on : Thursday, November 24, 2016 - 10:50:38 AM Last modification on : Thursday, November 24, 2016 - 11:14:10 AM Long-term archiving on: : Tuesday, March 21, 2017 - 1:05:25 PM
H. Sander Bruggink, Barbara König, Hans Zantema. Termination Analysis for Graph Transformation Systems. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.179-194, ⟨10.1007/978-3-662-44602-7_15⟩. ⟨hal-01402041⟩