Maximal and minimal dynamic Petri net slicing

Context: Petri net slicing is a technique to reduce the size of a Petri netto ease the analysis or understanding of the original Petri net. Objective:Presenting two new Petri net slicing algorithms to isolate those places andtransitions of a Petri net (the slice) that may contribute tokens to one ormore places given (the slicing criterion). Method: The two algorithms proposedare formalized. The maximality of the first algorithm and the minimality of thesecond algorithm are formally proven. Both algorithms, together with threeother state-of-the-art algorithms, have been implemented and integrated into asingle 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, andopen-source implementation of five algorithms is reported. The results of anempirical evaluation of the new algorithms and the slices they produce are alsopresented. Conclusions: The first algorithm collects all places and transitionsthat may contribute tokens (in any computation) to the slicing criterion, whilethe second algorithm collects the places and transitions needed to fire theshortest transition sequence that contributes tokens to some place in theslicing criterion. Therefore, the net computed by the first algorithm canreproduce any computation that contributes tokens to any place of interest. Incontrast, the second algorithm loses this possibility, but it often produces amuch more reduced subnet (which still can reproduce some computations thatcontribute tokens to some places of interest). The first algorithm is provenmaximal, and the second one is proven minimal