During last October we presented a paper at the 18th International Conference on System Theory, Control and Computing (ICSTCC 2014). It was at Sinaia, Romania and the paper was a further development of the work presented at PNSE (see Evolutionary computing and Petri Nets). We realized that we could use the incidence matrix of the Petri Net in order to look for siphons.
Authors: F. Tricas, JM Colom, JJ Merelo
Petri nets are graph based tools to model and study concurrent systems and their properties; one of them is liveness, which is related to the possibility of every part of the system to be activated eventually. Siphons are sets of places that are related to liveness properties. When we need to deal with realistic problems its computation is hard or even impossible and this is why in this paper we are approaching it using evolutionary computation, a meta-heuristic that has proved it can successfully find solutions when the search space is big. In a previous work a formulation of the siphon property based on linear constraints and a genetic algorithm was proposed for general Petri Nets. Here we propose to adapt an algebraic method based on the selection of rows of the matrix that cancel in an adequate way input and output transitions so the resulting selection is a siphon. We will also present an evaluation for a family of resource allocation systems (RAS). The proposed solution is based on a genetic algorithm (GA); we can see how siphons can be computed using this genetic algorithm, with experiments showing that in some cases they are able to find a few solutions in less time than previous deterministic algorithms.
The paper can be downloaded at the IEEE Xplore site (link above) and the accepted version is available at [pdf] Using the Incidence Matrix in an Evolutionary Algorithm for Computing Minimal Siphons in Petri Net Models.
The slides used at the conference are:
Our plan is to continue exploring theses kind of methods to see if we can improve the results obtained.