Abstract
Practical experiences show that only timed and coloured Petri nets are capable of modelling large and complex real-time systems. This is the reason we present the Interval Timed Coloured Petri Net (ITCPN) model. An interval timed coloured Petri net is a coloured Petri net extended with time; time is in tokens and transitions determine a delay for each produced token. This delay is specified by an upper and lower bound, i.e. an interval. The ITCPN model allows the modelling of the dynamic behaviour of large and complex systems, without losing the possibility of formal analysis. In addition to the existing analysis techniques for coloured Petri nets, we propose a new analysis method to analyse the temporal behaviour of the net. This method constructs a reduced reachability graph and exploits the fact that delays are described by an interval.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
W.M.P. van der Aalst, Interval Timed Petri Nets and their analysis. Computing Science Notes 91/09, Eindhoven University of Technology, Eindhoven, 1991.
-, Modelling and Analysis of Complex Logistic Systems, in Proceedings of the IFIP WG 5.7 Working Conference on Integration in Production Management Systems, Eindhoven, the Netherlands, 1992, pp. 203–218.
-, Timed coloured Petri nets and their application to logistics, PhD thesis, Eindhoven University of Technology, Eindhoven, 1992.
W.M.P. van der Aalst and A.W. Waltmans, Modelling logistic systems with EXSPECT, in Dynamic Modelling of Information Systems, H.G. Sol and K.M. van Hee, eds., Elsevier Science Publishers, Amsterdam, 1991, pp. 269–288.
C. Andre, Synchronized Elementary Net Systems, in Advances in Petri Nets 1989, G. Rozenberg, ed., vol. 424 of Lecture Notes in Computer Science, Springer-Verlag, New York, 1990, pp. 51–76.
ASPT, ExSpect 4.0 User Manual, Eindhoven University of Technology, 1993.
B. Berthomieu and M. Diaz, Modelling and verification of time dependent systems using Time Petri Nets, IEEE Transactions on Software Engineering, 17 (1991), pp. 259–273.
G. Chiola, C. Dutheillet, G. Franceschinis, and S. Haddad, On wellformed coloured nets and their symbolic reachability graph, in Proceedings of the 11th International Conference on Applications and Theory of Petri Nets, Paris, June 1990, pp. 387–411.
G. Florin and S. Natkin, Evaluation based upon Stochastic Petri Nets of the Maximum Throughput of a Full Duplex Protocol, in Application and theory of Petri nets: selected papers from the first and the second European workshop, C. Girault and W. Reisig, eds., vol. 52 of Informatik Fachberichte, Berlin, 1982, Springer-Verlag, New York, pp. 280–288.
H.J. Genrich and K. Lautenbach, System modelling with high level Petri nets, Theoretical Computer Science, 13 (1981), pp. 109–136.
K.M. van Hee, System Engineering: a Formal Approach (to appear), 1993.
K.M. van Hee, L.J. Somers, and M. Voorhoeve, Executable specifications for distributed information systems, in Proceedings of the IFIP TC 8 / WG 8.1 Working Conference on Information System Concepts: An In-depth Analysis, E.D. Falkenberg and P. Lindgreen, eds., Namur, Belgium, 1989, Elsevier Science Publishers, Amsterdam, pp. 139–156.
K.M. van Hee and P.A.C. Verkoulen, Integration of a Data Model and Petri Nets, in Proceedings of the 12th International Conference on Applications and Theory of Petri Nets, Aarhus, June 1991, pp. 410–431.
P. Hubner, A.M. Jensen, L.O. Jepsen, and K. Jensen, Reachability trees for high level Petri nets, Theoretical Computer Science, 45 (1986), pp. 261–292.
K. Jensen, Coloured Petri Nets, in Advances in Petri Nets 1986 Part I: Petri Nets, central models and their properties, W. Brauer, W. Reisig, and G. Rozenberg, eds., vol. 254 of Lecture Notes in Computer Science, Springer-Verlag, New York, 1987, pp. 248–299.
-, Coloured Petri Nets: A High Level Language for System Design and Analysis, in Advances in Petri Nets 1990, G. Rozenberg, ed., vol. 483 of Lecture Notes in Computer Science, Springer-Verlag, New York, 1990, pp. 342–416.
-, Coloured Petri Nets. Basic concepts, analysis methods and practical use., to appear in EATCS monographs on Theoretical Computer Science, Springer-Verlag, New York, 1992.
M. Ajmone Marsan, G. Balbo, A. Bobbio, G. Chiola, G. Conte, and A. Cumani, On Petri Nets with Stochastic Timing, in Proceedings of the International Workshop on Timed Petri Nets, Torino, 1985, IEEE Computer Society Press, pp. 80–87.
M. Ajmone Marsan, G. Balbo, and G. Conte, A Class of Generalised Stochastic Petri Nets for the Performance Evaluation of Multiprocessor Systems, ACM Transactions on Computer Systems, 2 (1984), pp. 93–122.
P. Merlin, A Study of the Recoverability of Computer Systems, PhD thesis, University of California, Irvine, California, 1974.
P. Merlin and D.J. Faber, Recoverability of communication protocols, IEEE Transactions on Communication, 24 (1976), pp. 1036–1043.
S. Morasca, M. Pezzè, and M. Trubian, Timed High-Level Nets, The Journal of Real-Time Systems, 3 (1991), pp. 165–189.
M. Odijk, ITPN analysis of ExSpect specifications with respect to production logistics, Master's thesis, Eindhoven University of Technology, Eindhoven, 1991.
C. Ramchandani, Performance Evaluation of Asynchronous Concurrent Systems by Timed Petri Nets, PhD thesis, Massachusetts Institute of Technology, Cambridge, 1973.
W. Reisig, Petri nets: an introduction, Prentice-Hall, Englewood Cliffs, 1985.
J. Sifakis, Use of Petri Nets for performance evaluation, in Proceedings of the Third International Symposium IFIP W.G. 7.3., Measuring, modelling and evaluating computer systems (Bonn-Bad Godesberg, 1977), H. Beilner and E. Gelenbe, eds., Elsevier Science Publishers, Amsterdam, 1977, pp. 75–93.
A. Valmari, Stubborn sets for reduced state space generation, in Proceedings of the 10th International Conference on Applications and Theory of Petri Nets, Bonn, June 1989.
W.M. Zuberek, Timed Petri Nets and Preliminary Performance Evaluation, in Proceedings of the 7th annual Symposium on Computer Architecture, vol. 8(3) of Quarterly Publication of ACM Special Interest Group on Computer Architecture, 1980, pp. 62–82.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van der Aalst, W.M.P. (1993). Interval timed coloured petri nets and their analysis. In: Ajmone Marsan, M. (eds) Application and Theory of Petri Nets 1993. ICATPN 1993. Lecture Notes in Computer Science, vol 691. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56863-8_61
Download citation
DOI: https://doi.org/10.1007/3-540-56863-8_61
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56863-6
Online ISBN: 978-3-540-47759-4
eBook Packages: Springer Book Archive