2012-01: Applying the Graph Minor Theorem to the Verification of Graph Transformation Systems
Salil Joshi, Prof. Dr. König, Barbara
In: Technische Berichte der Abteilung für Informatik und Angewandte Kognitionswissenschaft
Derivate 30451
351.8 KB in one file, last changed at 20.04.2012
| File | Files changed on | Size |
|---|---|---|
| tr-dbg-2012-1.pdf | 20.04.2012 16:09:55 | 351.8 KB |
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.
Bookmark:
Dokumententyp:
Wissenschaftliche Texte » Artikel, Aufsatz
Fakultät / Institut:
Fakultät für Ingenieurwissenschaften » Ingenieurwissenschaften - Campus Duisburg » Abteilung Informatik und Angewandte Kognitionswissenschaft
Dewey Dezimal-Klassifikation:
000 Informatik, Informationswissenschaft, allgemeine Werke » 000 Informatik, Wissen, Systeme
Language:
Englisch
Collection / Status:
E-Publications / Document published
Document created on:
20.04.2012
Files changed on:
20.04.2012
Medientyp:
Text
Source:
Technischer Bericht Nr. 2012-01 ISSN 1863-8554 Abteilung für Informatik und Angewandte Kognitionswissenschaft Fakultät für Ingenieurwissenschaften Universität Duisburg-Essen