Linear Time Algorithms for Liveness and Boundedness in Conflict-free Petri Nets

TitleLinear Time Algorithms for Liveness and Boundedness in Conflict-free Petri Nets
Publication TypeTechnical Report
Year of Publication1992
AuthorsAlimonti, P., Feuerstain E., & Nanni U.
Other Numbers713
Abstract

In this paper we consider the problems of deciding the set of potentially firable transitions, the liveness and boundedness for the class of Conflict-Free Petri Nets. For these problems we propose algorithms which are linear in the size of the description of the net, dramatically improving the best previous known results for these problems. Moreover the algorithm for the first problem is incremental: it is possible to perform an arbitrary sequence of updates, introducing new transitions and increasing the initial marking of the net, and queries, asking whether any transition is firable or any place reachable. Queries are answered in constant time, and the total cost for all the modifications is still linear in the size of the final net. Our approach is based on a representation of conflict-free Petri nets by means of directed hypergraphs. Figures are omitted in the ftp-able version of the paper. A complete version is available from ICSI.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-92-008.pdf
Bibliographic Notes

ICSI Technical Report TR-92-008

Abbreviated Authors

P. Alimonti, E. Feuerstain, and U. Nanni

ICSI Publication Type

Technical Report