Abstract
We present an approach to construct the occurrence graph for ITCPN (Interval Timed Coloured Petri Nets). These models, defined by Van Der Aalst in [VAN] can simulate other timed Petri nets and allow to describe large and complex real-time systems. We define classes as sets of states between two occurrences, and we use these classes to define the occurrence graph of an ITCPN. Then an equivalence relation based on time is defined for classes, and we show that occurrence graphs reduced using this equivalence relation are finite if and only if the set of reachable markings is finite. These graphs can be used to verify all the dynamic properties such as reachability, boundedness, home, liveness and fairness properties but also performance properties: minimal and maximal bounds along a occurrence sequence or a cycle. Finally we complete delay based equivalence with a colour based equivalence in order to achieve further reduction.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C.André “Synchronized Elmentary Net Systems”. Advances in Petri Nets 1989, Grzegorz Rozenberg editor, LNCS 424, Springer-Verlag.
G.Berry, G.Gonthier “The synchroneous Programming Language ESTEREL: Design, Semantic, Implementation”. INRIA report 842, 1988.
B.Berthomieu, M.Menasche “An enumerative approach for analysing time Petri nets”. IFIP Congress 1983, Paris, North-Holland.
B.Berthomieu, M. Diaz “Modeling and verification of time dependent systems using time Petri nets”. IEEE Transactions on Software Engineering vol 17, N∘3, March 91.
H.Boucheneb, G.Berthelot “Towards a Simplified building of time Petri Net Reachability graphs”. Proc.of Petri Nets and Performance Models PNPM93, Toulouse France, October 1993, IEEE Computer Society Press.
G.Florin, S.Natkin “Evaluation based upon Stochastic Petri nets of the maximum troughput of a full duplex protocol”. Second European Workshop on Application and Theory of Petri Net, Springer-Verlag 1982.
K.Jensen “Coloured Petri Nets: Basic concepts, Analysis Methods and Practical use. volume 1: Basic Concepts”. To appear in EATCS Monographs on Theoritical Computer Science, Springer-Verlag.
K.Jensen “Coloured Petri Nets: Basic concepts, Analysis Methods and Practical use. volume 2: Analysis Methods?” To appear in EATCS Monographs on Theoritical Computer Science, Springer-Verlag.
M.Menasche, “Analyse des réseaux de Petri temporisés et application aux systèmes distribués”. Thèse de docteur ingénieur, université de Paul Sabatier. Toulouse, Novembre 82.
P.Merlin, D.J.Farber, “Recovability of communication protocols”. IEEE Trans. on Communications, 24 (1976).
R.Milner “Communication and Concurrency”. Prentice Hall international series in computer science.
J.Quemada, A.Azcorra, D.Frutos, “A timed Calculus for LOTOS”. Proc. of Formal Description Techniques FORTE 89, S.Vuong editor, Vancouver Canada December 89.
C.Ramchandani “Analysis of Asynchronous Concurrent Systems by Timed Petri Nets”; Project MAC, TR 120, MIT, 1974.
R.R.Razouk, “The derivation of performance expressions for communication protocols for timed Petri nets”. Computer Communication review, vol. 14, n∘ 12, pp 210–217, 1984.
J.Sifakis “Use of Petri Nets for Performance Evaluation”. Measuring, Modeling and Evaluating Computer Systems, H.Beilner and E.Gelenbe editors, North-Holland, 1977.
J.Sifakis, “An Overview and Synthesis on Timed Process Algebras”. Proc of the 3rd International Workshop CAV'91, Alborg, Denmark, July 91, LNCS 575, Springer-Verlag.
W.M.P. Van Der Aalst “Interval Timed Coloured Petri Nets and their Analysis”, Application and Theory of Petri Nets 1993, 14th International Conference, Chicago, Illinois, USA, LNCS 691, Springer-Verlag.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Berthelot, G., Boucheneb, H., Alger, U. (1994). Occurrence graphs for Interval Timed Coloured Nets. In: Valette, R. (eds) Application and Theory of Petri Nets 1994. ICATPN 1994. Lecture Notes in Computer Science, vol 815. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58152-9_6
Download citation
DOI: https://doi.org/10.1007/3-540-58152-9_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58152-9
Online ISBN: 978-3-540-48462-2
eBook Packages: Springer Book Archive