Salil, Joshi; König, Barbara:
Applying the Graph Minor Theorem to the Verification of Graph Transformation Systems
Essen: Abteilung für Informatik und Angewandte Kognitionswissenschaft, Fakultät für Ingenieurwissenschaften, Universität Duisburg-Essen, 2012
(Technischer Bericht ; 2012-01)
Buch / Fach: Informatik
Fakultät für Ingenieurwissenschaften » Informatik und Angewandte Kognitionswissenschaft
Titel:
Applying the Graph Minor Theorem to the Verification of Graph Transformation Systems
Autor(in):
Salil, Joshi; König, Barbara im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen
Erscheinungsort:
Essen
Verlag:
Abteilung für Informatik und Angewandte Kognitionswissenschaft, Fakultät für Ingenieurwissenschaften, Universität Duisburg-Essen
Erscheinungsjahr:
2012
In Serie:
Technischer Bericht, Band 2012-01
Umfang:
21 S.
DuEPublico ID:
URN:

Abstract:

We show how to view certain subclasses of (single-pushout) graph transformation systems as well-structured transition systems, which leads to decidability of the covering problem via a backward analysis. As the well-quasi order required for a well-structured transition system we use the graph minor ordering. We give an explicit construction of the backward step and apply our theory in order to show the correctness of a leader election protocol