Algorithms on marked directed graphs

Marked directed graphs are a special case of Petri nets introduced by Carl Petri as a model for information flow in systems exhibiting asynchronism and parallelism. Commoner, Holt, Even and Pnueli (1971) have studied several structural and algorithmic aspects of marked graphs using graph theory and network flow algorithms. Subsequently, Murata (1977) has studied these graphs using a circuit-theoretic approach. In this paper, the authors combine the ideas of both these works and present algorithms for certain problems on marked graphs. In particular, they introduce the concept of scatter in firing sequences and present algorithms for determining minimum scatter firing sequences for different classes of graphs. An approach for the general case and a lowerbound on the scatter of any firing sequence-leading from an initial marking to a reachable final marking on a given marked graph are presented.