[CL13] Computation of Minimal Siphons in Petri Nets by Using Binary Decision Diagrams

Revue Internationale avec comité de lecture : Journal ACM Transactions on Embedded Computing Systems, vol. 12(1), pp. 3:1-3:15, 2013
Résumé: 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.

Equipe: sys


@article {
title="{Computation of Minimal Siphons in Petri Nets by Using Binary Decision Diagrams}",
author="Y. Chen and G. Liu",
journal="ACM Transactions on Embedded Computing Systems",