On Siphon Computation for Deadlock Control in a Class of Petri Nets Export

@article{citeulike:3171494, abstract = {As a structural object, siphons are well recognized in the analysis and control of deadlocks in resource allocation systems modeled with Petri nets. Many deadlock prevention policies characterize the deadlock behavior of the systems in terms of siphons and utilize this characterization to avoid deadlocks. This paper develops a novel methodology to find interesting siphons for deadlock control purposes in a class of Petri nets, i.e., a system of simple sequential processes with resources . Resource circuits in an are first detected, from which, in general, a small portion of emptiable minimal siphons can be derived. The remaining emptiable ones can be found by their composition. A polynomial-time algorithm for finding the set of elementary siphons is proposed, which avoids complete siphon enumeration. It is shown that a dependent siphon can always be controlled by properly supervising its elementary siphons. A computationally efficient deadlock control policy is accordingly developed. Experimental study shows the efficiency of the proposed siphon computation approach.}, author = {Li, Zhiwu and Zhou, Mengchu}, booktitle = {Systems, Man and Cybernetics, Part A, IEEE Transactions on}, citeulike-article-id = {3171494}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/TSMCA.2008.918605}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4490042}, doi = {10.1109/TSMCA.2008.918605}, journal = {Systems, Man and Cybernetics, Part A, IEEE Transactions on}, keywords = {citas, computation, nets, petri, siphons}, number = {3}, pages = {667--679}, posted-at = {2008-08-29 10:24:51}, priority = {2}, title = {On Siphon Computation for Deadlock Control in a Class of Petri Nets}, url = {http://dx.doi.org/10.1109/TSMCA.2008.918605}, volume = {38}, year = {2008} }

TY - JOUR ID - citeulike:3171494 L3 - citeulike-article-id:3171494 N2 - As a structural object, siphons are well recognized in the analysis and control of deadlocks in resource allocation systems modeled with Petri nets. Many deadlock prevention policies characterize the deadlock behavior of the systems in terms of siphons and utilize this characterization to avoid deadlocks. This paper develops a novel methodology to find interesting siphons for deadlock control purposes in a class of Petri nets, i.e., a system of simple sequential processes with resources . Resource circuits in an are first detected, from which, in general, a small portion of emptiable minimal siphons can be derived. The remaining emptiable ones can be found by their composition. A polynomial-time algorithm for finding the set of elementary siphons is proposed, which avoids complete siphon enumeration. It is shown that a dependent siphon can always be controlled by properly supervising its elementary siphons. A computationally efficient deadlock control policy is accordingly developed. Experimental study shows the efficiency of the proposed siphon computation approach. IS - 3 JF - Systems, Man and Cybernetics, Part A, IEEE Transactions on EP - 679 TI - On Siphon Computation for Deadlock Control in a Class of Petri Nets VL - 38 T2 - Systems, Man and Cybernetics, Part A, IEEE Transactions on SP - 667 KW - citas KW - computation KW - nets KW - petri KW - siphons AU - Li, Zhiwu AU - Zhou, Mengchu PY - 2008/// UR - http://dx.doi.org/10.1109/TSMCA.2008.918605 ER -