TCS / Research / Publications / Time Processes of Time Petri Nets
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Time Processes of Time Petri Nets


Tuomas Aura. Time processes of time Petri nets. Research Report A38, Helsinki University of Technology, Digital Systems Laboratory, Espoo, Finland, August 1996.


The objective of this thesis is to give time Petri nets a partial order semantics, like the nonsequential processes of untimed net systems. A time process of a time Petri net is defined as a traditionally constructed causal process with a valid timing. This means that the events of the process are labeled with occurrence times which must satisfy specific validness criteria. An efficient algorithm for checking validness of known timings is presented. Interleavings of the time processes are defined as linearizations of the causal partial order of events where also the time order of events is preserved. The relationship between firing schedules of a time Petri net and the interleavings of the time processes of the net is shown to be bijective. Also, a sufficient condition is given for when the invalidity of timings for a process can be inferred from its initial subprocess. An alternative characterization for the validness of timings results in an algorithm for constructing the set of all valid timings for a process. The set of all valid timings is presented as sets of alternative linear constraints, which can be used in optimization problems. The techniques developed can be used to compute, for example, the maximum time separation of two events in a process. The existence of a valid timing for a given process can be decided in NP time.


Time Petri nets, processes, timing analysis, partial order semantics, causality, net theory

Suggested BibTeX entry:

    address = {Espoo, Finland},
    author = {Tuomas Aura},
    institution = {Helsinki University of Technology, Digital Systems Laboratory},
    month = {August},
    number = {A38},
    pages = {58},
    title = {Time Processes of Time {P}etri Nets},
    type = {Research Report},
    year = {1996},

NOTE: Reprint of Master's thesis; see URL below.
PostScript (531 kB)
GZipped PostScript (175 kB)
See ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.