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