Improved Local Partitioning Minimal-Siphon Enumeration Method

Abstract

Siphon computation is a basic step for developing siphon-based deadlock control approaches in a Petri net (PN) system. This work studies the enumeration of minimal siphons in a PN. Due to the fact that the number of siphons in a PN theoretically grows exponentially with the net size, the siphon enumeration is basically time-consuming especially in a large-size net. To our best knowledge, the method of local partitioning minimal-siphon enumeration (LPMSE) has the best performance among all the methods applicable to any arbitrary PN. In this paper, we show that the improvement of LPMSE is possible and thereby develop an improved LPMSE. It is validated by experimental results that the improved LPMSE consumes less time than LPMSE.

Keywords

• Petri nets
• minimal siphons
• siphon computation
• problem partitioning