*For the most recent entries see the
Petri Nets Newsletter.*

## On some analysis properties of Petri net systems under the earliest firing rule.

Ohta, A.;
Hisamura, T.
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.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*