Minimum initial marking estimation in labeled petri nets

Abstract

This paper develops an algorithm for estimating the minimum initial marking based on the observation of a sequence of labels that is produced by underlying transition activity in a given labeled Petri net. We assume that the structure of the net is completely known while the initial marking of the net is unknown. Given the observation of the sequence of labels, we aim to estimate the minimum initial marking of the net, i.e., an initial marking that (i) allows for the -ring of at least one sequence of transitions that is consistent with both the observed sequence of labels and the net structure; and (ii) has the least total number of tokens (i.e., the minimum number of tokens summed over all places). We develop a recursive algorithm that can be used online to find the minimum initial marking with complexity that is polynomial in the length of the observed label sequence. Such minimum initial markings are useful for characterizing the minimum number of resources required at initialization for a variety of systems. © 2009 AACC.