In: IEICE Trans. on Fundamentals in Electronics, Communications and Computer Science, Vol. E79-A, No. 11, pages 1791-1796. November 1996.
Abstract: This paper discusses analysis problems for Petri nets under the earliest firing rule. Under this rule, transitions must fire as soon as they are enabled. Marked Petri nets under the earliest firing rule are called earliest firing systems. First, some relations between the earliest and the normal firing systems are discussed. These include deadlock freedom, boundedness, persistency and liveness. Then, relation among three types of reachability are considered from the viewpoint of the earliest firing rule. Since earliest firing systems can simulate register machines, they have equivalent modeling power as Turing machines. This indicates, however, that most of the analysis problems for earliest firing systems with general net structures are undecidable. In this paper, net structures are restricted to a subclass called dissynchronous choice (DC) nets. It is shown that the reachability problem from an initial marking to dead markings (i.e., markings where no transition is enables) in earliest firing DC systems is equivalent to the usual reachability problem of the same systems under the normal firing rule. Then the result is applied to reachability problems of controlled DC systems in which some transitions in the net have external control input places. It is shown that for systems where every transition in the net has an external control input place, one type of reachability problem is decidable. Lastly, the liveness problem of earliest firing DC systems is considered and it is shown that this problem is equivalent to that of the underlying DC system under the normal firing rule. It is also shown that this liveness problem is decidable.
Keywords: Petri nets, decidable properties, dissynchronous choice nets, earliest firing rule, liveness property, reachability property, undecidable properties.