文章基本信息

标题：Efficient Analysis of Permutation Equivalence of Graph Derivations Based on Petri Nets
本地全文：下载
作者：Frank Hermann ; Andrea Corradini ; Hartmut Ehrig 等
期刊名称：Electronic Communications of the EASST
电子版ISSN：1863-2122
出版年度：2010
卷号：29
语种：English
出版社：European Association of Software Science and Technology (EASST)
摘要：In the framework of graph transformation systems with Negative Application Conditions (NACs) the classical notion of switch equivalence of derivations is extended to permutation equivalence, because there are intuitively equivalent derivations which are not switch-equivalent if NACs are considered. By definition, two derivations are permutation-equivalent, if they respect the NACs and disregarding the NACs they are switch equivalent. A direct analysis of permutation equivalence is very complex in general, thus we propose a much more efficient analysis technique. For this purpose, we construct a Place/Transition Petri net, called dependency net, which encodes the dependencies among rule applications of the derivation, including the inhibiting effects of the NACs. The analysis of permutation equivalence is important for analysing simulation runs within development environments for systems modelled by graph transformation. The application of the technique is demonstrated by a graph transformation system within the context of workflow modelling. We show the effectiveness of the approach by comparing the minimal costs of a direct analysis with the costs of the efficient analysis applied to a derivation of our example system.