TY - GEN
T1 - A Novel Method for Reachability Determination in Petri Nets
AU - Li, Duan
AU - Sun, Xiaoling
AU - Gao, Jianjun
AU - Gu, Shenshen
AU - Zheng, Xiaojin
PY - 2009/6
Y1 - 2009/6
N2 - Reachability is one of the most important behavioral properties of Petri nets and the past four decades have witnessed great efforts in developing various implementable methodologies in determining reachability of Petri nets. We propose in this paper a novel method for solving the fundamental equation in the reachability analysis, which has been known to be NP-complete. More specifically, by adopting a revised version of the cell enumeration method for an arrangement of hyperplanes in discrete geometry, we develop an efficient solution scheme to identify firing count vector solution(s) to the fundamental equation on a bounded integer set, with a complexity bound of O((nω)n-m), where n is the number of transitions, m is the number of places and ω is the upper bound of the number of firings for every transition.
AB - Reachability is one of the most important behavioral properties of Petri nets and the past four decades have witnessed great efforts in developing various implementable methodologies in determining reachability of Petri nets. We propose in this paper a novel method for solving the fundamental equation in the reachability analysis, which has been known to be NP-complete. More specifically, by adopting a revised version of the cell enumeration method for an arrangement of hyperplanes in discrete geometry, we develop an efficient solution scheme to identify firing count vector solution(s) to the fundamental equation on a bounded integer set, with a complexity bound of O((nω)n-m), where n is the number of transitions, m is the number of places and ω is the upper bound of the number of firings for every transition.
KW - Cell enumeration
KW - Discrete optimization
KW - Integer programming
KW - Linear diophantine equations on bounded integer set
KW - Petri nets
KW - Reachability analysis
UR - https://www.scopus.com/pages/publications/79953765215
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-79953765215&origin=recordpage
U2 - 10.3182/20090603-3-RU-2001.0100
DO - 10.3182/20090603-3-RU-2001.0100
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9783902661432
T3 - IFAC Proceedings Volumes (IFAC-PapersOnline)
SP - 276
EP - 281
BT - PROCEEDINGS OF THE 13th IFAC SYMPOSIUM ON INFORMATION CONTROL PROBLEMS IN MANUFACTURING, INCOM '09
T2 - 13th IFAC Symposium on Information Control Problems in Manufacturing (INCOM '09)
Y2 - 3 June 2009 through 5 June 2009
ER -