Siphons play an important role in the development of deadlock control methods by using Petri nets. The number of siphons increases exponentially with respect to the size of a Petri net. This article presents a symbolic approach to the computation of minimal siphons in Petri nets by using binary decision diagrams (BDD). The siphons of a Petri net can be found via a set of logic conditions. The logic conditions are symbolically modeled by using Boolean algebras. The operations of Boolean algebras are implemented by BDD that are capable of representing large sets of siphons with small shared data structures. The proposed method first uses BDD to compute all siphons of a Petri net and then a binary relation is designed to extract all minimal siphons. Finally, by using a number of examples, the efficiency of the proposed method is verified through different-sized problems.
%0 Journal Article
%1 ChenLiu13
%A Chen, Yufeng
%A Liu, Gaiyun
%C New York, NY, USA
%D 2013
%I ACM
%J ACM Trans. Embed. Comput. Syst.
%K citeulike computation, deadlock, siphons
%N 1
%R 10.1145/2406336.2406339
%T Computation of Minimal Siphons in Petri Nets by Using Binary Decision Diagrams
%U http://dx.doi.org/10.1145/2406336.2406339
%V 12
%X Siphons play an important role in the development of deadlock control methods by using Petri nets. The number of siphons increases exponentially with respect to the size of a Petri net. This article presents a symbolic approach to the computation of minimal siphons in Petri nets by using binary decision diagrams (BDD). The siphons of a Petri net can be found via a set of logic conditions. The logic conditions are symbolically modeled by using Boolean algebras. The operations of Boolean algebras are implemented by BDD that are capable of representing large sets of siphons with small shared data structures. The proposed method first uses BDD to compute all siphons of a Petri net and then a binary relation is designed to extract all minimal siphons. Finally, by using a number of examples, the efficiency of the proposed method is verified through different-sized problems.
@article{ChenLiu13,
abstract = {{Siphons play an important role in the development of deadlock control methods by using Petri nets. The number of siphons increases exponentially with respect to the size of a Petri net. This article presents a symbolic approach to the computation of minimal siphons in Petri nets by using binary decision diagrams (BDD). The siphons of a Petri net can be found via a set of logic conditions. The logic conditions are symbolically modeled by using Boolean algebras. The operations of Boolean algebras are implemented by BDD that are capable of representing large sets of siphons with small shared data structures. The proposed method first uses BDD to compute all siphons of a Petri net and then a binary relation is designed to extract all minimal siphons. Finally, by using a number of examples, the efficiency of the proposed method is verified through different-sized problems.}},
added-at = {2017-09-08T10:52:59.000+0200},
address = {New York, NY, USA},
author = {Chen, Yufeng and Liu, Gaiyun},
biburl = {https://www.bibsonomy.org/bibtex/21b3209f0e10bf15724c5ff45d55361d4/fernand0},
citeulike-article-id = {14040412},
citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=2406339},
citeulike-linkout-1 = {http://dx.doi.org/10.1145/2406336.2406339},
doi = {10.1145/2406336.2406339},
interhash = {4ef0458faa32df4cc785eda5c9a5278b},
intrahash = {1b3209f0e10bf15724c5ff45d55361d4},
issn = {1539-9087},
journal = {ACM Trans. Embed. Comput. Syst.},
keywords = {citeulike computation, deadlock, siphons},
month = jan,
number = 1,
posted-at = {2016-05-23 17:18:31},
priority = {2},
publisher = {ACM},
timestamp = {2017-09-08T10:53:23.000+0200},
title = {{Computation of Minimal Siphons in Petri Nets by Using Binary Decision Diagrams}},
url = {http://dx.doi.org/10.1145/2406336.2406339},
volume = 12,
year = 2013
}