Petri Nets with TimeWindows: A Comparison to Classical Petri Nets

• Autorzy: Wegener J-T. , Popova-Zeugmann L.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Petri nets with time windows

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 93, nr 1-3
• Strony: 337--352
• Opis fizyczny: Bibliogr. 13 poz., tab., wykr.

Twórcy

autor

Wegener J-T.

autor

Popova-Zeugmann L.

• Department of Computer Science, Humboldt University Berlin, Germany,

Bibliografia

• [1] Parosh Aziz Abdulla, Pritha Mahata, and Richard Mayr. Dense-timed petri nets: Checking zenoness, token liveness and boundedness. The Journal of Logical Methods in Computer Science, 2007.
• [2] Hans-Michael Hanisch. Analysis of place/transition nets with timed arcs and its application to batch process control. In Application and Theory of Petri Nets, pages 282-299, 1993.
• [3] John E. Hopcroft, R. Motwani, and J. D. Ullman. Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Pearson Studium, 2002.
• [4] Kurt Lautenbach. Exakte Bedingungen der Lebendigkeit für eine Klasse von Petri-Netzen. Phd thesis, GMG, Bonn, 1973.
• [5] Karsten Lemmer. Diagnose diskreter modellierter Systeme mit Petrinetzen. Dissertation, Technische Universität, Braunschweig, 1995.
• [6] Morgan Magnin, Didier Lime, and Olivier (H.) Roux. Symbolic state space of stopwatch petri nets with discrete-time semantics. In The 29th International Conference on Application and Theory of Petri Nets and other models of concurrency (ICATPN 2008), volume 5062 of Lecture Notes in Computer Science, Xi'an, China, June 2008. Springer.
• [7] Merlin, Ph.M. A Study of the Recoverability of Computing Systems. PhD thesis, University of California, Computer Science Dept., Irvine, January 1974.
• [8] L. Popova-Zeugmann. Petri Nets with Time Restrictions. Systems Analysis, Modeling, Simulation(SAMS), pages 13-20, 1993.
• [9] Popova-Zeugmann, L. Time and Petri Nets (in German). Habilitation Thesis, Humboldt University at Berlin, Berlin, 2007.
• [10] Popova-Zeugmann, L. and Schlatter, D. Analyzing Path in Time Petri Nets. Fundamenta Informaticae (FI) 37, IOS Press, Amsterdam, pages 311-327, 1999.
• [11] C. Ramchandani. Analysis of asynchronous concurrent systems by Timed Petri Nets. Project MAC-TR 120, MIT, February 1974.
• [12] J. Sifakis. Performance evaluation of systems using nets. In Brauer, W., editor, Lecture Notes in Computer Science: Net Theory and Applications, Proc. of the Advanced Course on General Net Theory of Processes and Systems, Hamburg, 1979, volume 84, pages 307-319, Berlin, Heidelberg, New York, 1980. Springer-Verlag.
• [13] JuacunWang. Timed Petri Nets. Kluwer Academic Publishers, Boston, Dordrecht, London, 1998.