Computation of strict minimal siphons in a class of Petri nets based on problem decomposition

Dan You; Shou Guang Wang; Meng Chu Zhou

doi:10.1016/j.ins.2017.05.011

Computation of strict minimal siphons in a class of Petri nets based on problem decomposition

Dan You, Shou Guang Wang, Meng Chu Zhou

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

18 Scopus citations

Abstract

Efficient siphon computation plays an important role in deadlock control. This work, based on problem decomposition, develops a new method to compute all strict minimal siphons (SMS) in a class of Petri nets called Systems of Simple Sequential Processes with Resources (S³PR). It is proved to be of polynomial complexity with respect to the number of SMSs. Therefore, it is readily applicable to an S³PR with a large number of SMSs. Its superiority over the existing methods is validated via experimental results.

Original language	English (US)
Pages (from-to)	87-100
Number of pages	14
Journal	Information sciences
Volume	409-410
DOIs	https://doi.org/10.1016/j.ins.2017.05.011
State	Published - Oct 1 2017

All Science Journal Classification (ASJC) codes

Software
Control and Systems Engineering
Theoretical Computer Science
Computer Science Applications
Information Systems and Management
Artificial Intelligence

Keywords

Deadlock
Discrete event systems (DES)
Petri nets
Polynomial complexity
Problem decomposition
Siphon computation

Access to Document

10.1016/j.ins.2017.05.011

Cite this

@article{42d8670c44f94e9c8ae9a60f9ce56e0f,

title = "Computation of strict minimal siphons in a class of Petri nets based on problem decomposition",

abstract = "Efficient siphon computation plays an important role in deadlock control. This work, based on problem decomposition, develops a new method to compute all strict minimal siphons (SMS) in a class of Petri nets called Systems of Simple Sequential Processes with Resources (S3PR). It is proved to be of polynomial complexity with respect to the number of SMSs. Therefore, it is readily applicable to an S3PR with a large number of SMSs. Its superiority over the existing methods is validated via experimental results.",

keywords = "Deadlock, Discrete event systems (DES), Petri nets, Polynomial complexity, Problem decomposition, Siphon computation",

author = "Dan You and Wang, {Shou Guang} and Zhou, {Meng Chu}",

note = "Publisher Copyright: {\textcopyright} 2017",

year = "2017",

month = oct,

day = "1",

doi = "10.1016/j.ins.2017.05.011",

language = "English (US)",

volume = "409-410",

pages = "87--100",

journal = "Information sciences",

issn = "0020-0255",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Computation of strict minimal siphons in a class of Petri nets based on problem decomposition

AU - You, Dan

AU - Wang, Shou Guang

AU - Zhou, Meng Chu

PY - 2017/10/1

Y1 - 2017/10/1

N2 - Efficient siphon computation plays an important role in deadlock control. This work, based on problem decomposition, develops a new method to compute all strict minimal siphons (SMS) in a class of Petri nets called Systems of Simple Sequential Processes with Resources (S3PR). It is proved to be of polynomial complexity with respect to the number of SMSs. Therefore, it is readily applicable to an S3PR with a large number of SMSs. Its superiority over the existing methods is validated via experimental results.

AB - Efficient siphon computation plays an important role in deadlock control. This work, based on problem decomposition, develops a new method to compute all strict minimal siphons (SMS) in a class of Petri nets called Systems of Simple Sequential Processes with Resources (S3PR). It is proved to be of polynomial complexity with respect to the number of SMSs. Therefore, it is readily applicable to an S3PR with a large number of SMSs. Its superiority over the existing methods is validated via experimental results.

KW - Deadlock

KW - Discrete event systems (DES)

KW - Petri nets

KW - Polynomial complexity

KW - Problem decomposition

KW - Siphon computation

UR - http://www.scopus.com/inward/record.url?scp=85019179059&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85019179059&partnerID=8YFLogxK

U2 - 10.1016/j.ins.2017.05.011

DO - 10.1016/j.ins.2017.05.011

M3 - Article

AN - SCOPUS:85019179059

SN - 0020-0255

VL - 409-410

SP - 87

EP - 100

JO - Information sciences

JF - Information sciences

ER -

Computation of strict minimal siphons in a class of Petri nets based on problem decomposition

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this