2012-03: Well-Structured Graph Transformation Systems with Negative Application Conditions

Dateibereich 30851

389,7 KB in einer Datei, zuletzt geändert am 31.07.2013

Dateiliste / Details

DateiDateien geändert amGröße
wsts_nac_techreport.pdf04.07.2012 15:07:06389,7 KB
Given a transition system and a partial order on its states, the coverability problem is the question to decide whether a state can be reached that is larger than some given state. For graphs, a typical such partial order is the minor ordering, which allows to specify \bad graphs" as those graphs having a given graph as a minor. Well-structuredness of the transition system enables a nite representation of upward-closed sets and gives rise to a backward search algorithm for deciding coverability. It is known that graph tranformation systems without negative application conditions form well-structured transition systems (WSTS) if the minor ordering is used and certain condition on the rules are satised. We study graph transformation systems with negative application conditions and show under which conditions they are well-structured and are hence amenable to a backwards search decision procedure for checking coverability.
Lesezeichen:
Permalink | Teilen/Speichern
Dokumententyp:
Wissenschaftliche Texte » Artikel, Aufsatz
Fakultät / Institut:
Fakultät für Ingenieurwissenschaften » Informatik und Angewandte Kognitionswissenschaft » Informatik » Theoretische Informatik
Dewey Dezimal-Klassifikation:
000 Informatik, Informationswissenschaft, allgemeine Werke » 000 Informatik, Wissen, Systeme
Sprache:
Englisch
Kollektion / Status:
E-Publikationen / Dokument veröffentlicht
Dokument erstellt am:
04.07.2012
Dateien geändert am:
31.07.2013
Medientyp:
Text
Quelle:
Technischer Bericht Nr. 2012-03 ISSN 1863-8554 Abteilung für Informatik und Angewandte Kognitionswissenschaft Fakultät für Ingenieurwissenschaften Universität Duisburg-Essen