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), 21 S.
Buch / Monographie / Fach: Informatik
Fakultät für Ingenieurwissenschaften » Informatik und Angewandte Kognitionswissenschaft
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