A causal semantics for time Petri nets

✍ Scribed by Tuomas Aura; Johan Lilius

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 463 KB
• Volume: 243
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(99)00114-0

✦ Synopsis

The objective of this work is to give time Petri nets a partial order semantics, akin to the nonsequential processes of untimed net systems. To this end a time process of a time Petri net is deÿned as a traditionally constructed causal process with a valid timing. A timing is a labelling that attaches occurrence times to the events of the process that must satisfy speciÿc validness criteria. The main result of the paper is the bijective correspondence between ÿring schedules (the classical interleaving semantics of time Petri nets) and linearizations of time processes. The result shows that time processes correctly represent the behavior of the system. Using the deÿnition of validness, an e cient algorithm for checking validness of given timings is derived. Also a su cient condition is given for when the invalidity of timings for a process can be inferred from its initial subprocess. To compute, e.g. the maximum time separation between two events in a time process an alternative characterization of validness is developed. This deÿnition is used to derive an algorithm for constructing the set of all valid timings for a process. The set of valid timings is presented as sets of alternative linear constraints, which can be used in optimization problems. It is shown that the existence of a valid timing for a given process can be decided in NP time.