Basis Marking Representation of Petri Net Reachability Spaces and Its Application to the Reachability Problem
Top Cited Papers
- 27 May 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 62 (3) , 1078-1093
Abstract
In this paper, a compact representation of the reachability graph of a Petri net is proposed. The transition set of a Petri net is partitioned into the subsets of explicit and implicit transitions in such a way that the subnet induced by implicit transitions does not contain directed cycles. The firing of implicit transitions can be abstracted so that the reachability set of the net can be completely characterized by a subset of reachable markings called basis makings. We show that to determine a max-cardinality-TI basis partition is an NP-hard problem, but a max-set-TI basis partition can be determined in polynomial time. The generalized version of the marking reachability problem in a Petri net can be solved by a practically efficient algorithm based on the basis reachability graph. Finally, this approach is further extended to unbounded nets.Keywords
Funding Information
- National Natural Science Foundation of China (61374068, 61472295)
- Recruitment Program of Global Experts
- ShaanXi Huashan Scholarship
- Science Technology Development Fund, MSAR (078/2015/A3)
This publication has 31 references indexed in Scilit:
- Discrete event diagnosis using labeled Petri nets. An application to manufacturing systemsControl Engineering Practice, 2011
- Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systemsAutomatica, 2011
- Fault detection for discrete event systems using Petri nets with unobservable transitionsAutomatica, 2010
- Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systemsIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2004
- Modular Analysis of Petri NetsThe Computer Journal, 2000
- THE APPLICATION OF PETRI NETS TO WORKFLOW MANAGEMENTJournal of Circuits, Systems and Computers, 1998
- A Petri net based deadlock prevention policy for flexible manufacturing systemsIEEE Transactions on Robotics and Automation, 1995
- A method for stepwise refinement and abstraction of Petri netsJournal of Computer and System Sciences, 1983
- Persistence of vector replacement systems is decidableActa Informatica, 1981
- Finiteness of the Odd Perfect and Primitive Abundant Numbers with n Distinct Prime FactorsAmerican Journal of Mathematics, 1913