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

Ziyue, Ma; Tong, Yin; Zhiwu, Li; Giua, Alessandro

doi:10.1109/TAC.2016.2574120

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; Tong, Yin; Li, Zhiwu; Giua, Alessandro. - In: IEEE TRANSACTIONS ON AUTOMATIC CONTROL. - ISSN 0018-9286. - 62:3(2017), pp. 1078-1093.

Trovami (UniCASearch)

Titolo:	Basis marking representation of Petri net reachability spaces and its application to the reachability problem
Autori:	Ma, Ziyue Tong, Yin Li, Zhiwu GIUA, ALESSANDRO mostra contributor esterni nascondi contributor esterni
Data di pubblicazione:	2017
Rivista:	IEEE TRANSACTIONS ON AUTOMATIC CONTROL
Citazione:	Basis marking representation of Petri net reachability spaces and its application to the reachability problem / Ma, Ziyue; Tong, Yin; Li, Zhiwu; Giua, Alessandro. - In: IEEE TRANSACTIONS ON AUTOMATIC CONTROL. - ISSN 0018-9286. - 62:3(2017), pp. 1078-1093.
Handle:	http://hdl.handle.net/11584/178018
Tipologia:	1.1 Articolo in rivista

File in questo prodotto:

File	Descrizione	Tipologia	Licenza
17tac_a_draft.pdf	Articolo principale	versione post-print		Open Access Visualizza/Apri

Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/11584/178018

Citazioni

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

UNICA IRIS Institutional Research Information System

File in questo prodotto: