Treffer: Applying the graph minor theorem to the verification of graph transformation systems
Title:
Applying the graph minor theorem to the verification of graph transformation systems
Authors:
Contributors:
The Pennsylvania State University CiteSeerX Archives
Publisher Information:
Springer
Publication Year:
2012
Collection:
CiteSeerX
Document Type:
Fachzeitschrift
text
File Description:
application/pdf
Language:
English
Rights:
Metadata may be used without restrictions as long as the oai identifier remains attached to it.
Accession Number:
edsbas.C23177F9
Database:
BASE
Weitere Informationen
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.