Petri Nets with Time Windows: A Comparison to Classical Petri Nets

Issue title: Concurrency Specification and Programming (CS&P)

Article type: Research Article

Authors: Wegener, Jan-Thierry | Popova-Zeugmann, Louchka

Affiliations: Department of Mathematics, Humbold University, Berlin, Germany. [email protected] | Department of Computer Science, Humboldt University, Berlin, Germany. [email protected]

Note: [] Address for correspondence: Department of Computer Science, Humboldt University, Berlin, Germany

Abstract: We present Petri nets with time windows (tw-PN) where each place is associated with an interval (window). Every token which arrives at a place gets a real-valued clock which shows its "age". A transition can fire when all needed tokens are "old enough". When a token reaches an "age" equal to the upper bound of the place where it is situated, the "token's age", i.e., clock will be reset to zero. Following this we compare these time dependent Petri nets with their (timeless) skeletons. The sets of both their reachable markings are equal, their liveness behaviour is different, and neither is equivalent to Turing machines. We also prove the existence of runs where time gaps are possible in the tw-PN, which is an extraordinary feature.

DOI: 10.3233/FI-2009-0106

Journal: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 337-352, 2009