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.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.179-194, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_15〉
https://hal.inria.fr/hal-01402041
Contributeur : Hal Ifip
<>
Soumis le : jeudi 24 novembre 2016 - 10:50:38
Dernière modification le : jeudi 24 novembre 2016 - 11:14:10
Document(s) archivé(s) le : mardi 21 mars 2017 - 13:05:25
