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-T_I basis partition is an NPhard problem, but a max-set-T_I 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.

Basis marking representation of Petri net reachability spaces and its application to the reachability problem

Ma, Ziyue
Primo
;
Tong, Yin
Secondo
;
GIUA, ALESSANDRO
Ultimo
2017

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-T_I basis partition is an NPhard problem, but a max-set-T_I 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.
Basis reachability graph; discrete-event systems; Petri nets
File in questo prodotto:
File Dimensione Formato  
2017_IEEE TRANSACTIONS ON AUTOMATIC CONTROL_62.3.pdf

Solo gestori archivio

Descrizione: articolo
Tipologia: versione editoriale
Dimensione 1.7 MB
Formato Adobe PDF
1.7 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
17tac_a_draft.pdf

accesso aperto

Tipologia: versione post-print
Dimensione 2.69 MB
Formato Adobe PDF
2.69 MB Adobe PDF Visualizza/Apri

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/178018
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 87
  • ???jsp.display-item.citation.isi??? 84
social impact