Japan Advanced Institute of Science and Technology

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

Author(s)

Citation

Issue Date

Type

Text version

URL

Rights

Description

Problem of Petri Nets

Hirohide Tanaka

Scho ol of Information Sinence,

Japan Advanced Institute of Science and Technology

February,15,2001

Keywords: discrete eventsystem

，

，

，

NP-hard

，

A system inwhichevents o ccur discreteand asynchronouslyis calleda discreteevent

systems(DES).Typicalapplicationsexist incomputernetworks,operatingsystems,com-

municationsystems,databasesystems,sequencecontrolsandsoon. Fromtherequirement

for the eective control of such applications, there have been many researches on DESs

from various viewpoints. Especially, the most of them concentrated the mo deling and

analysis to these systems. Petri net which is one of logic models iswidely used for mod-

eling and the simulation of a discrete event system, and has many applications, such as

an assembly line, the operation process of a plant, operating systems, a communication

protocol, and anasynchronous circuit.

Petri net is a directed bipartite graph which consists of two kinds of nodes called

place and transition. A non-negative numb er of tokens are assigned to each place, and

itsdistributionsituation (marking)changeswith reof transition. Whichisthe dynamic

characterof Petrinet. If this ability of dynamicexpressionis used well,itmay becomea

powerfulmodeling toolat actionanalysis.

LegalFiringSequenceProblemofPetrinets(LFSforshort)isdenedasfollows:\given

a Petri net PN, an initial marking M and a ring count vector X, with each component

X(t) denoting the prescrib ed total ring numb er of a transition t, nd a ring sequence

whichislegal onMwith respectto X,where is asequenceof transitionsand is called

legalonMwith resp ecttoXifand onlyifthe rsttransition of isrableonM,the rest

canberedonebyonesubsequentlyandeachtransitiontappearsexactlyX(t)timesin.

" This isan important problem in case the dynamic character of a system is analyzed.

LFS is very fundamental in the sense that it appears as a subproblem or a simpler

formofvariousbasicproblems inPetrinet theory,suchasthe well-knownmarkingreach-

ability problem, the minimum initial resource allocation problem, the liveness problem,

Copyright c

2001byHirohideTanaka

NP-hardevenforthe Petri netwithverysimplestructuresbyT.Watanabe

，

，

K.Onaga. Therefore,heuristicswhichcansolveLFSoroptimumLFSwithapracticaluse

scaleinrealistictimehasbeenproposed. ForapersistentPetrinet,anecientalgorithm

whichsolvesLFS is known.

In this paper,the ecientmethodofLFS isproposed. Inthis method,usingthe idea

ofpersistentset,anexplosionofthenumb erofstatesbyinterleavingoftheexcutionseries

whichis anobstacle insearchis suppressed.

The paper is organized as follows. In Chapter 2, denitions of Petri net and LFS

are given. In Chapter 3, the NP-hardness of LFS used when T.Watanab e, Y.Mizobata,

K.Onagaprovedisdescrib ed. InChapter4,examplesofLFSofpersistentnetisdescrib ed.

In Chapter 5, referring to the previous algorithm of LFS, we prop osed the metho d of

solving LFS using the persistent set. Finally, it experiments and the obtained result is

considered inChapter 6.