In: Theoretical Computer Science, Vol. 216, No. 1-2, pages 1-53. 1999.
Abstract: Various models of time Petri Nets have been successfully used to adequately specify time-critical systems. For such systems correctness depends not only on the actions that are performed, but also on the times when they are performed. Therefore, the semantics must take explicitly into account the timings of actions, and also concepts of time-based expressivity are needed to compare the expressive power of the various models. In the paper we introduce a general framework that includes many Petri net models, present in the literature, which differ from one another with respect to timing location, timing strength and time domain. Then we introduce an operational semantics that takes into account both sequentialization and timing of actions. When abstracting time away we reobtain previously reported results, which are useful when one is interested in modeling systems that are not time-critical. On the other hand, when abstracting the sequentialization of actions away we define a new kind of expressivity in terms of which we compare the various models we have considered.
Keywords: expressive power, formal languages, semantics, time Petri nets, time-critical systems.