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

Derivate 30851

389.7 KB in one file, last changed at 31.07.2013

File list / details

FileFiles changed onSize
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.
Permalink | Share/Save
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
Collection / Status:
E-Publications / Document published
Document created on:
Files changed on:
Technischer Bericht Nr. 2012-03 ISSN 1863-8554 Abteilung für Informatik und Angewandte Kognitionswissenschaft Fakultät für Ingenieurwissenschaften Universität Duisburg-Essen