Least-cost transition firing sequence estimation in labeled Petri nets with unobservable transitions
Date
2011Source
IEEE Transactions on Automation Science and EngineeringVolume
8Issue
2Pages
394-403Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
This paper proposes an approach for estimating the least-cost transition firing sequence(s) that matches (match) the observation of a sequence of labels produced by transition activity in a given labeled Petri net. Each transition in the labeled net is associated with a (possibly empty) label and also with a nonnegative cost which captures its likelihood (e.g., in terms of the amount of workload or power required to execute the transition). Given full knowledge of the structure of the labeled Petri net and the observation of a sequence of labels, we aim at finding the transition firing sequence(s) that is (are) consistent with both the observed label sequence and the Petri net, and also has (have) the least total cost (i.e., the least sum of individual transition costs). The existence of unobservable transitions makes this task extremely challenging since the number of firing sequences that might be consistent can potentially be infinite. Under the assumption that the unobservable transitions in the net form an acyclic subnet and have strictly positive costs, we develop a recursive algorithm that is able to find the least-cost firing sequence(s) by reconstructing only a finite number of firing sequences. In particular, if the unobservable transitions in the net are contact-free, the proposed recursive algorithm finds the least-cost transition firing sequences with complexity that is polynomial in the length of the observed sequence of labels. © 2010 IEEE.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Article
A magnetostructural investigation of an abrupt spin transition for 1-phenyl-3-trifluoromethyl-1,4-dihydrobenzo[e][1,2,4]triazin-4-yl
Constantinides, Christos P.; Berezin, Andrey A.; Zissimou, Georgia A.; Manoli, Maria; Leitus, G. M.; Bendikov, M.; Probert, M. R.; Rawson, J. M.; Koutentis, Panayiotis Andreas (2014)1-Phenyl-3-trifluoromethyl-1,4-dihydrobenzo[e][1,2,4]triazin-4-yl is the first example of a hydrazyl radical that shows a reversible sharp spin transition fully completed within 5(1) K. The nominally first-order transition ...
-
Conference Object
Antipodal finline-to-microstrip transition for operation in the Ka band
Olsen, A. O.; Steenson, P.; Iezekiel, Stavros (2000)
-
Article
Diol-type ligands as central 'players' in the chemistry of high-spin molecules and single-molecule magnets
Tasiopoulos, Anastasios J.; Perlepes, Spyros P. (2008)The combination of diol-type ligands with paramagnetic transition metal ions has led to the isolation of a host of new homometallic and heterometallic clusters, high-spin molecules and single molecule magnets ranging in ...