Applying the Graph Minor Theorem to the Verification of Graph Transformation Systems
Duisburg: DuEPublico, 2012
(Technische Berichte der Abteilung für Informatik und Angewandte Kognitionswissenschaft ; 2012-01)
2012bookOA Gold
Computer ScienceFaculty of Engineering » Computer Science and Applied Cognitive Science
Title in English:
Applying the Graph Minor Theorem to the Verification of Graph Transformation Systems
Author:
Salil, Joshi;König, BarbaraUDE
- GND
- 1050396502
- LSF ID
- 15982
- ORCID
-
0000-0002-4193-2889
- Other
- connected with university
Place of publication:
Duisburg
Publisher:
DuEPublico
Year of publication:
2012
Open Access?:
OA Gold
Extent:
21 S.
DuEPublico 1 ID
Language of text:
English
Abstract in English:
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