Complexity of the deadlock problem for Petri nets modeling resource allocation systems

DOI10.1016/J.INS.2015.11.025MaRDI QIDQ2279727zbMATH OpenOpenAlexFDO

Authors GuanJun Liu

Publication date 13 December 2019

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ins.2015.11.025

zbMATH Keywords

collaborationdeadlockNP-completenessPetri netsPSPACE-completenessresource allocation systems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• Resource Allocation Systems: Some Complexity Results on the S4PR Class
• A Petri net perspective on the resource allocation problem in software engineering
• scientific article; zbMATH DE number 978207
• scientific article; zbMATH DE number 1354143
• Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings

Cites work

• An interleaving semantics for UML 2 interactions using Petri nets
• Complexity of some problems in Petri nets
• Complexity of the soundness problem of bounded workflow nets
• Complexity results for 1-safe nets
• Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings
• Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems
• Design of Optimal Petri Net Controllers for Disjunctive Generalized Mutual Exclusion Constraints
• Liveness of an extended S\(^{3}\)PR
• Modeling and monitoring of E-commerce workflows
• On the lower bound of monitor solutions of maximally permissive supervisors for a subclass \(\alpha\)-\(S^{3}\)PR of flexible manufacturing systems
• Real-time management of resource allocation systems. A discrete event systems approach.
• Robustness analysis of Petri nets for assembly/disassembly processes with unreliable resources
• Soundness of workflow nets: classification, decidability, and analysis
• The resource allocation problem in flexible manufacturing systems
• Understanding Petri Nets

Cited in

(11)

• Supervisory control of a class of Petri nets with unobservable and uncontrollable transitions
• Computation of strict minimal siphons in a class of Petri nets based on problem decomposition
• A Petri net perspective on the resource allocation problem in software engineering
• On the siphon-based characterization of liveness in sequential resource allocation systems
• Resource Allocation Systems: Some Complexity Results on the S4PR Class
• scientific article; zbMATH DE number 4045096 (Why is no real title available?)
• Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems
• Process completing sequences for resource allocation systems with synchronization
• Design of optimal Petri net supervisors for flexible manufacturing systems via weighted inhibitor arcs
• Structural methods for the control of discrete event dynamic systems -- the case of the resource allocation problem
• High-level Petri-net model for a resource-sharing problem

This page was built for publication: Complexity of the deadlock problem for Petri nets modeling resource allocation systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279727)