%0 Journal Article %1 CanoRovettoColom12 %A Cano, Elia E. %A Rovetto, Carlos A. %A Colom, José M. %B Discrete Event Dynamic Systems %C Hingham, MA, USA %D 2012 %I Springer US %J Discrete Event Dynamic Systems %K citas, citeulike computation, nets, petri, siphons %N 4 %P 403--428 %R 10.1007/s10626-012-0132-4 %T An algorithm to compute the minimal siphons in S 4 PR nets %U http://dx.doi.org/10.1007/s10626-012-0132-4 %V 22 %X Minimal siphons in the class of S 4PR nets have become a conceptual and practical central tool for the study of the resource allocation related aspects in discrete event dynamic systems as, for example, the existence of deadlocks. Therefore the availability of efficient algorithms to compute the minimal siphons is essential. In this paper we try to take advantage of the particular properties of the siphons in S 4PR to obtain an efficient algorithm. These properties allow us to express minimal siphons as the union of pruned minimal siphons containing only one resource. The pruning operation is built from the binary pruning relation defined on the set of minimal siphons containing only one resource. This pruning relation is represented by means of a directed graph. The computation of the minimal siphons is based on the maximal strongly connected components of this graph. The algorithm is highly economic in memory in all intermediate steps when compared to the classical algorithms.

@article{CanoRovettoColom12, abstract = {{Minimal siphons in the class of S 4PR nets have become a conceptual and practical central tool for the study of the resource allocation related aspects in discrete event dynamic systems as, for example, the existence of deadlocks. Therefore the availability of efficient algorithms to compute the minimal siphons is essential. In this paper we try to take advantage of the particular properties of the siphons in S 4PR to obtain an efficient algorithm. These properties allow us to express minimal siphons as the union of pruned minimal siphons containing only one resource. The pruning operation is built from the binary pruning relation defined on the set of minimal siphons containing only one resource. This pruning relation is represented by means of a directed graph. The computation of the minimal siphons is based on the maximal strongly connected components of this graph. The algorithm is highly economic in memory in all intermediate steps when compared to the classical algorithms.}}, added-at = {2017-09-08T10:52:59.000+0200}, address = {Hingham, MA, USA}, author = {Cano, Elia E. and Rovetto, Carlos A. and Colom, Jos\'{e} M.}, biburl = {https://www.bibsonomy.org/bibtex/22c3fce80c9f27b588f1c2be20132744c/fernand0}, booktitle = {Discrete Event Dynamic Systems}, citeulike-article-id = {10412044}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=2385642}, citeulike-linkout-1 = {http://dx.doi.org/10.1007/s10626-012-0132-4}, citeulike-linkout-2 = {http://www.springerlink.com/content/640m601h51266158}, citeulike-linkout-3 = {http://link.springer.com/article/10.1007/s10626-012-0132-4}, day = 26, doi = {10.1007/s10626-012-0132-4}, interhash = {4293e19313037cddae56857aca383046}, intrahash = {2c3fce80c9f27b588f1c2be20132744c}, issn = {0924-6703}, journal = {Discrete Event Dynamic Systems}, keywords = {citas, citeulike computation, nets, petri, siphons}, month = dec, number = 4, pages = {403--428}, posted-at = {2013-04-19 17:21:28}, priority = {2}, publisher = {Springer US}, timestamp = {2017-09-08T10:53:23.000+0200}, title = {{An algorithm to compute the minimal siphons in S 4 PR nets}}, url = {http://dx.doi.org/10.1007/s10626-012-0132-4}, volume = 22, year = 2012 }