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

König, Barbara LSF; Stückrath, Jan LSF

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.

Logo

Technical Report

Share and cite

Citation style:

König, Barbara / Stückrath, Jan: 2012-03. Well-Structured Graph Transformation Systems with Negative Application Conditions. 2012.

Could not load citation form. Default citation form is displayed.

Rights

Use and reproduction:
All rights reserved

Export