Termination Analysis for Graph Transformation Systems

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〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

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

Fichier

978-3-662-44602-7_15_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

H. Bruggink, Barbara König, Hans Zantema. Termination Analysis for Graph Transformation Systems. 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〉. 〈hal-01402041〉

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

26