Algebraical Characterisation of Interval-Timed Petri Nets with Discrete Delays

• Autorzy: Popova-Zeugmann L. , Pelz E.
• Języki publikacji: EN

Abstrakty

EN

In this paper we consider Interval-Timed Petri nets (ITPN) which are an extension of Timed Petri nets. They are considered to behave with discrete delays. The class of ITPNs is Turing complete and therefore the reachability of an arbitrary marking in such a net is not decidable. We introduce a time dependent state equation for a firing sequence of ITPNs, which is analogous to the state equation for a firing sequence in standard Petri nets and we prove its correctness using linear algebra. Our result is original and delivers both a necessary condition for reachability and a sufficient condition for non-reachability of an arbitrary marking in an ITPN.

Słowa kluczowe

EN

Interval-Timed Petri nets; state equation; reachability; Interval-Timed Petri net analysis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 120, nr 3/4
• Strony: 341--357
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Popova-Zeugmann L.

autor

Pelz E.

• Department of Computer Science Humboldt University, Germany,

Bibliografia

• [1] Berthomieu, B. and Diaz, M. Modeling and Verification of Time Dependent Systems Using Time Petri Nets. In Advances in Petri Nets 1984, volume 17, No. 3 of IEEE Trans. on Software Eng., pages 259-273, 1991.
• [2] Berthomieu, B. and Menasche, M. An Enumerative Approach for Analyzing Time Petri Nets. In Proceedings IFIP Congress, September 1983.
• [3] Fleischhack, H. and Pelz, E. Hierarchical Timed High Level Nets and their Branching Processes. In Proceedings of ICATPN'03, LNCS 2679, Springer, pages 397-416, 2003.
• [4] Heiner, M. and Popova-Zeugmann, L. Worst-case Analysis of Concurrent Systems with Duration Interval Petri Nets. In Proceedings of 5. Fachtagung Entwurf komplexer Automatisierungssysteme, TU Braunschweig, 1997.
• [5] Klaudel, H. and Pommereau, F. Asynchronous links in the PBC and M-nets. In Proceedings of ASIAN'99, LNCS 1742, Springer, pages 190-200, 1999.
• [6] Pelz, E. and Fleischhack, H. Compositional high level Petri nets with timing constraints - a comparison. In Proceedings of ASCD, IEEE Press, pages 132-141, 2003.
• [7] L. Popova. On Time Petri Nets. J. Inform. Process. Cybern. EIK 27(1991)4, pages 227-244, 1991.
• [8] Popova-Zeugmann, L. Time and Petri Nets. (in German), Habilitation, Humboldt Universität zu Berlin, 2007.
• [9] Popova-Zeugmann, L. and Werner, M. and Richling, J. Using State-equation to Prove Non-reachability in Timed Petrinets. Fundamenta Informaticae (FI), 61, IOS-Press, Amsterdam, pages 187-202, 2003.
• [10] Ramchandani, C. Analysis of asynchronous concurrent systems by Timed Petri Nets. Project MAC-TR 120, MIT, February 1974.
• [11] Sifakis, J. Performance Evaluation of Systems Using Nets. In Net Theory and Applications, Procceedings of the Advanced Course on General Net Theory of Processes and Systems, LNCS 84, Springer, pages 307-319, 1980.