Complexity of some problems in Petri nets |
| |
Authors: | Neil D Jones Lawrence H Landweber Y Edmund Lien |
| |
Affiliation: | Department of Computer Science, University of Kansas, Lawrence, Kansas 66045, U.S.A.;Computer Sciences Department, University of Wisconsin, 1210 W. Daylon, Madison, Wisconsin 53706, U.S.A.;Department of Computer Science, University of Kansas, Lawrence, Kansas 66045, U.S.A. |
| |
Abstract: | We consider the complexity of several standard problems for various classes of Petri nets. In particular, the reachability problem, the liveness problem and the k-boundedness problems are analyzed. Some polynomial time and polynomial space complete problems for Petri nets are given. We then show that the problem of deciding whether a Petri net is persistent is reducible to reachability, partially answering a question of Keller. Reachability and boundedness are proved to be undecidable for the Time Petri net introduced by Merlin. Also presented is the concept of controllability, i.e., the capability of a set of transitions to disable a given transition. We show that the controllability problem requires exponential space, even for 1-bounded nets. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|