On Some Analysis Properties of Petri Net Systems under the Earliest Firing Rule

Atsushi OHTA; Tomiji HISAMURA

On Some Analysis Properties of Petri Net Systems under the Earliest Firing Rule

Atsushi OHTA, Tomiji HISAMURA

Full Text Views

0

Cite this

Summary :

Petri net is a graphical and mathematical modeling tool for discrete event systems. This paper treats analysis problems for Petri nets under the earliest firing rule. Under this firing rule, transitions must fire as soon as they are enabled. Marked Petri nets under the earliest firing rule are called earliest firing systems, for short. First, some relations in analysis problems between the earliest and the normal firing systems are discussed. These problems include deadlock freedom, boundedness, persistency and liveness. Then, relations 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 powers to Turing machines. It suggests, however, that most of the analysis problems of 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 (markings where no transition can fire) 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.11 pp.1791-1796

Publication Date: 1996/11/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Description Models for Concurrent Systems and Their Applications)

Category

Cite this

Copy

Atsushi OHTA, Tomiji HISAMURA, "On Some Analysis Properties of Petri Net Systems under the Earliest Firing Rule" in IEICE TRANSACTIONS on Fundamentals, vol. E79-A, no. 11, pp. 1791-1796, November 1996, doi: .
Abstract: Petri net is a graphical and mathematical modeling tool for discrete event systems. This paper treats analysis problems for Petri nets under the earliest firing rule. Under this firing rule, transitions must fire as soon as they are enabled. Marked Petri nets under the earliest firing rule are called earliest firing systems, for short. First, some relations in analysis problems between the earliest and the normal firing systems are discussed. These problems include deadlock freedom, boundedness, persistency and liveness. Then, relations 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 powers to Turing machines. It suggests, however, that most of the analysis problems of 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 (markings where no transition can fire) 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_11_1791/_p

Copy

@ARTICLE{e79-a_11_1791,
author={Atsushi OHTA, Tomiji HISAMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On Some Analysis Properties of Petri Net Systems under the Earliest Firing Rule},
year={1996},
volume={E79-A},
number={11},
pages={1791-1796},
abstract={Petri net is a graphical and mathematical modeling tool for discrete event systems. This paper treats analysis problems for Petri nets under the earliest firing rule. Under this firing rule, transitions must fire as soon as they are enabled. Marked Petri nets under the earliest firing rule are called earliest firing systems, for short. First, some relations in analysis problems between the earliest and the normal firing systems are discussed. These problems include deadlock freedom, boundedness, persistency and liveness. Then, relations 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 powers to Turing machines. It suggests, however, that most of the analysis problems of 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 (markings where no transition can fire) 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={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - On Some Analysis Properties of Petri Net Systems under the Earliest Firing Rule
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1791
EP - 1796
AU - Atsushi OHTA
AU - Tomiji HISAMURA
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 1996
AB - Petri net is a graphical and mathematical modeling tool for discrete event systems. This paper treats analysis problems for Petri nets under the earliest firing rule. Under this firing rule, transitions must fire as soon as they are enabled. Marked Petri nets under the earliest firing rule are called earliest firing systems, for short. First, some relations in analysis problems between the earliest and the normal firing systems are discussed. These problems include deadlock freedom, boundedness, persistency and liveness. Then, relations 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 powers to Turing machines. It suggests, however, that most of the analysis problems of 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 (markings where no transition can fire) 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.
ER -