An Efficient Computing of the First Passage Time in an Extended Stochastic Petri Net

Hong-ju MOON  Wook Hyun KWON  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.6   pp.1267-1276
Publication Date: 2000/06/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Concurrent Systems
Keyword: 
first passage time,  extended stochastic Petri net,  timed stochastic state machine,  semi-Markov process,  

Full Text: PDF>>
Buy this Article



Summary: 
This paper presents an efficient method to derive the first passage time of an extended stochastic Petri net by simple algebraic operations. The reachability graph is derived from an extended stochastic Petri net, and then converted to a timed stochastic state machine which is a semi-Markov process. The mean and the variance of the first passage time are derived by algebraic manipulations with the mean and the variance of the transition time, and the transition probability for each transition in the state machine model. For the derivation, three reduction rules are introduced on the transition trajectories in a well-formed regular expression. An efficient algorithm is provided to automate the suggested method.