Well-Structured Graph Transformation Systems with Negative Application Conditions
Well-Structured Graph Transformation Systems with Negative Application Conditions
复制标题
具有负应用条件的结构良好的图转换系统
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Jan Stückrath
中科院分区：
文献类型：
--
作者：
B. König;Jan Stückrath
给定一个过渡系统及其状态的偏序，
可覆盖性问题是决定是否可以达到大于某个给定状态的状态的问题。对于图，典型的这种偏序是次序，它允许指定 广告图表”
作为子图的图。良好的结构化的过渡系统，使一个nite表示的向上闭集，并产生一个向后搜索算法，以确定覆盖。
如果使用次序且满足一定的规则条件，则无负应用条件的图变换系统构成良结构变换系统（WSTS）。
我们研究图形变换系统的负应用条件，并显示在哪些条件下，他们是结构良好的，因此可以进行向后搜索的决策过程检查覆盖性。
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 ad 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.