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)
Buch2012Informatik
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, BarbaraLSF
Erscheinungsort
Essen
Verlag
Abteilung für Informatik und Angewandte Kognitionswissenschaft, Fakultät für Ingenieurwissenschaften, Universität Duisburg-Essen
Erscheinungsjahr
2012
Umfang
21 S.
DuEPublico ID:
URN:
In Serie:
Titel:
Technischer Bericht
in:
Band 2012-01

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