A siphon is a structural object in Petri nets that is important both from a theoretical and a practical point of view. Particularly, the performance of siphon-based deadlock control policies largely depends on siphon enumeration. This work studies complete minimal-siphon enumeration in ordinary Petri nets. A recent approach, called global partitioning minimal-siphon enumeration (GPMSE) has been recently proposed by Cordone et al. [1] and provides good performance compared with other methods. In this paper we show that further improvements are possible and we propose a novel approach, called improved GPMSE, which requires lower computational complexity and memory consumption than the original method, especially for nets with large size. Experimental results are presented to validate the above claim.

Complete enumeration of minimal siphons in ordinary Petri nets based on problem partitioning

SEATZU, CARLA;GIUA, ALESSANDRO
2015

Abstract

A siphon is a structural object in Petri nets that is important both from a theoretical and a practical point of view. Particularly, the performance of siphon-based deadlock control policies largely depends on siphon enumeration. This work studies complete minimal-siphon enumeration in ordinary Petri nets. A recent approach, called global partitioning minimal-siphon enumeration (GPMSE) has been recently proposed by Cordone et al. [1] and provides good performance compared with other methods. In this paper we show that further improvements are possible and we propose a novel approach, called improved GPMSE, which requires lower computational complexity and memory consumption than the original method, especially for nets with large size. Experimental results are presented to validate the above claim.
978-1-4799-7886-1
Petri nets;computational complexity;GPMSE;complete minimal-siphon enumeration;computational complexity;discrete event system;memory consumption;ordinary Petri net;partitioning minimal-siphon enumeration;problem partitioning;siphon-based deadlock control policy;Computational complexity;Conferences;Indexes;Memory management;Petri nets;Search problems;System recovery;Discrete event systems;Petri nets;Siphons
File in questo prodotto:
File Dimensione Formato  
15cdc_c_draft.pdf

non disponibili

Descrizione: conference paper
Tipologia: versione post-print
Dimensione 181 kB
Formato Adobe PDF
181 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11584/178040
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact