Context: Petri net slicing is a technique to reduce the size of a Petri net so that it can ease the analysis or understanding of the original Petri net. Objective: To Present two new Petri net slicing algorithms to isolate those places and transitions of a Petri net (the slice) that may contribute tokens to one or more places given (the slicing criterion). Method: The two algorithms proposed are formalized. The maximality of the first algorithm and the minimality of the second algorithm are formally proven. Both algorithms together with other three state-of-the-art algorithms have been implemented and integrated into a single tool so that we have been able to carry out a fair empirical evaluation. Results: Besides the two new Petri net slicing algorithms, a public, free, and open-source implementation of five algorithms is reported. The results of an empirical evaluation of the new algorithms and the slices that they produce are also presented. Conclusions: The first algorithm collects all places and transitions that may influence (in any computation) the slicing criterion, while the second algorithm collects the places and transitions needed to fire the smallest transition sequence that contributes tokens to some place in the slicing criterion. Therefore, the net computed by the first algorithm can reproduce any computation that contributes tokens to any place of interest. In contrast, the second algorithm loses this possibility but it often produces a much more reduced subnet (which still can reproduce some computations that contribute tokens to some places of interest). The first algorithm is proven maximal, and the second one is proven minimal.
翻译:背景:Petrie网切片是一种缩小Petri网规模的技术,这样可以方便分析或理解原始Petri网的大小。目标:提供两种新的Petri网切片算法,以孤立这些地方和Petri网(切片)的过渡,这种算法可能有助于给一个或一个以上地方(切片标准)的象征物。方法:提议的两种算法是正式的。第一个算法和第二个算法的最小性得到了正式证明。两种算法与其他三个最先进的算法一起,已经实施并融入一个单一工具,以便我们能够进行公平的实证评估。结果:除了两种新的Petri网切片算法(切片)的分离和过渡,这些算法可能会有助于给一个或更多的地方(在任何计算中),第一个算法的最小性算法可以让一个地方和某些最起码的算法成为最起码的算法。在某个地方,一个算法可以让一个最起码的算法成为最起码的算法。在某个地方和最起码的运算法的变法中,可以使一个地方的算法成为最起码的算法。在任何最接近的算法中可以降低的算法。