In: Technical Report 0008, ICSI, Berkeley. 1992.
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.