Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10398841 | Automatica | 2011 | 5 Pages |
Abstract
Reachability is one of the most important behavioral properties of Petri nets. We propose in this paper a novel approach for solving the fundamental equation in the reachability analysis of acyclic Petri nets, 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((nu)nâm), where n is the number of transitions, m is the number of places and u is the upper bound of the number of firings for all individual transitions.
Related Topics
Physical Sciences and Engineering
Engineering
Control and Systems Engineering
Authors
Duan Li, Xiaoling Sun, Jianjun Gao, Shenshen Gu, Xiaojin Zheng,