%0 Journal Article %1 journals/tcs/JonesLL77 %A Jones, Neil D. %A Landweber, Lawrence H. %A Lien, Y. Edmund %D 1977 %J Theoretical Computer Science %K PetriNets %N 3 %P 277-299 %R 10.1016/0304-3975(77)90014-7 %T Complexity of Some Problems in Petri Nets. %U http://dblp.uni-trier.de/db/journals/tcs/tcs4.html#JonesLL77 %V 4 %X 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.

@article{journals/tcs/JonesLL77, 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.}, added-at = {2018-10-16T17:56:52.000+0200}, author = {Jones, Neil D. and Landweber, Lawrence H. and Lien, Y. Edmund}, biburl = {https://www.bibsonomy.org/bibtex/27062e136a1fd3142488a67d75f94b647/paves_intern}, doi = {10.1016/0304-3975(77)90014-7}, ee = {http://dx.doi.org/10.1016/0304-3975(77)90014-7}, interhash = {b103dc78c107fd8effa6bbc00cd035ed}, intrahash = {7062e136a1fd3142488a67d75f94b647}, journal = {Theoretical Computer Science}, keywords = {PetriNets}, number = 3, pages = {277-299}, timestamp = {2019-02-08T20:07:14.000+0100}, title = {Complexity of Some Problems in Petri Nets.}, url = {http://dblp.uni-trier.de/db/journals/tcs/tcs4.html#JonesLL77}, volume = 4, year = 1977 }