Ordered Firing in Petri Nets

Abstract

Two simple rules for solving conflicts and for ordering the firings of tronsitions in a Petri net are studied: 1. The "Maximum Strategy" (Salwicki, Müldner) whereby maximal sets of simultaneously fireble transitions are fired. 2. Firing in the order of enabling of transitions by some queue regimes. In both cases the computational power of Petri nets is extended up to the power of counter machines. As a consequence, the reachability, boundedness and liveness problems are all undecidable if the firing of transitions is ordered by the Maximum Strategy or by the considered queue regimes.