Reachability determination in acyclic Petri nets by cell enumeration approach

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 o...

Full description

Saved in:
Bibliographic Details
Published in:Automatica (Oxford) 2011-09, Vol.47 (9), p.2094-2098
Main Authors: Li, Duan, Sun, Xiaoling, Gao, Jianjun, Gu, Shenshen, Zheng, Xiaojin
Format: Article
Language:English
Subjects:
Applied sciences
Cell enumeration
Computer science
control theory
systems
Control theory. Systems
Counting
Enumeration
Exact sciences and technology
Firing
Hyperplanes
Linear Diophantine equations on bounded integer set
Mathematical analysis
Modelling and identification
Petri nets
Reachability analysis
Upper bounds
Vectors (mathematics)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0005-1098
1873-2836
DOI:10.1016/j.automatica.2011.06.017