On the Compared Expressiveness of Arc, Place and Transition Time Petri Nets

• Autorzy: Boyer M. , Roux O.H.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we consider safe Time Petri Nets where time intervals (strict and large) are associated with places (P-TPN), arcs (A-TPN) or transitions (T-TPN). We give the formal strong and weak semantics of these models in terms of Timed Transition Systems. We compare the expressiveness of the six models w.r.t. (weak) timed bisimilarity (behavioral semantics). The main results of the paper are : (i) with strong semantics, A-TPN is strictly more expressive than P-TPN and T-TPN ; (ii) with strong semantics P-TPN and T-TPN are incomparable ; (iii) T-TPN with strong semantics and T-TPN with weak semantics are incomparable. Moreover, we give a complete classification by a set of 9 relations explained in Fig. 19 (p. 247).

Słowa kluczowe

EN

Time Petri Net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 88, nr 3
• Strony: 225--249
• Opis fizyczny: bibliogr. 25 poz.

Twórcy

autor

Boyer M.

autor

Roux O.H.

• ONERA, Toulouse Research Center 2, av. Edouard Belin, BP 4025, 31055 Toulouse Cedex 4, France,

Bibliografia

• [1] Abdulla, P. A., Nylén, A.: Timed Petri Nets and BQOs, 22nd International Conference on Application and Theory of Petri Nets (ICATPN'01), 2075, Springer-Verlag, United Kingdom, 2001.
• [2] Aura, T., Lilius, J.: A Causal Semantics for Time Petri Nets, Theoretical Computer Science, 243(2), 2000, 409-447.
• [3] Berthomieu, B.: La méthode des classes d'états pour l'analyse des réseaux temporels.Mise en oeuvre, extension `a la multi-sensibilisation, Modélisation des Systèmes Réactifs (MSR'01), Toulouse (Fr), 17-19 Octobre 2001.
• [4] Berthomieu, B., Diaz, M.: Modeling and Verification of Time Dependent Systems Using Time Petri Nets, IEEE transactions on software engineering, 17(3),March 1991, 259-273.
• [5] Boyer,M.: Translation from timed Petri nets with interval on transitions to interval on places (with urgency), Workshop on Theory and Practice of Timed Systems, 65, Elsevier Science, Grenoble, France, April 2002.
• [6] Boyer, M., Diaz, M.: Multiple enabledness of transitions in time Petri nets, Proc. of the 9th IEEE International Workshop on Petri Nets and Performance Models, IEEE Computer Society, Aachen, Germany, September 11-14 2001.
• [7] Boyer, M., Roux, O. H.: Comparison of the expressiveness w.r.t. timed bisimilarity of k-bounded Arc, Place and Transition Time Petri Nets with weak and strong single server semantics, Technical Report RI2006-15, IRCCyN, 2006, (http://www.irccyn.ec-nantes.fr/hebergement/Publications/2006/3437.pdf).
• [8] Boyer, M., Roux, O. H.: Comparison of the expressiveness of Arc, Place and Transition Time Petri Nets, Proceeding of the 28th International Conference on Application and Theory of Petri Nets and Other Models of Concurrency (ICATPN) (J. Kleijn, A. Yakovlev, Eds.), 4546, Springer-Verlag, Siedlce, Poland, june 2007.
• [9] Boyer, M., Vernadat, F.: Language and bisimulation relations between subclasses of timed Petri nets with strong timing semantic, Technical report, LAAS, 2000.
• [10] Bérard, B., Cassez, F., Haddad, S., Lime, D., Roux, O. H.: Comparison of Different Semantics for Time Petri Nets, Automated Technology for Verification and Analysis (ATVA'05), 3707, Springer, Taiwan, October 2005.
• [11] Bérard, B., Cassez, F., Haddad, S., Lime, D., Roux, O. H.: Comparison of the expressiveness of Timed Automata and Time Petri Nets, 3rd International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS 05), 3829, Springer, Uppsala, Sweden, 2005.
• [12] Bérard, B., Cassez, F., Haddad, S., Lime, D., Roux, O. H.: When are timed automata weakly timed bisimilar to time Petri nets ?, 25th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2005), 3821, Springer, Hyderabad, India, 2005.
• [13] Cassez, F., Roux, O. H.: Structural Translation from Time Petri Nets to Timed Automata - Model-Checking Time Petri Nets via Timed Automata, The journal of Systems and Software, 79(10), 2006, 1456-1468.
• [14] Cerone, A., Maggiolo-Schettini, A.: Timed based expressivity of time Petri nets for system specification, Theoretical Computer Science, 216, 1999, 1-53.
• [15] de Frutos Escrig, D., Ruiz, V. V., Alonso, O. M.: Decidability of properties of timed-arc Petri nets, 21st International Conference on Application and Theory of Petri Nets (ICATPN'00), 1825, Springer-Verlag, Aarhus, Denmark, jun 2000.
• [16] Hanisch, H.: Analysis of place/transition nets with timed-arcs and its application to batch process control, 14th International Conference on Application and Theory of Petri Nets (ICATPN'93), 691, 1993.
• [17] Jones, N. D., Landweber, L. H., Lien, Y. E.: Complexity of Some Problems in Petri Nets., Theoretical Computer Science 4, 1977, 277-299.
• [18] Khansa, W., Denat, J.-P., Collart-Dutilleul, S.: P-Time Petri Nets for manufacturing systems, International Workshop on Discrete Event Systems, WODES'96, Edinburgh (U.K.), august 1996.
• [19] Khanza,W.: Réseau de Petri P-Temporels. Contribution `a l'étude des systèmes `a évènements discrets, Ph.D. Thesis, Université de Savoie, 1992.
• [20] Merlin, P. M.: A study of the recoverability of computing systems, Ph.D. Thesis, Dep. of Information and Computer Science, University of California, Irvine, CA, 1974.
• [21] Pezzè, M.: Time Petri Nets: A Primer Introduction, Tutorial presented at the Multi-Workshop on Formal Methods in Performance Evaluation and Applications, Zaragoza, Spain, september 1999.
• [22] Ramchandani, C.: Analysis of asynchronous concurrent systems by timed Petri nets, Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1974, Project MAC Report MAC-TR-120.
• [23] Sifakis, J.: Performance Evaluation of Systems using Nets, Net theory and applications : Proc. of the advanced course on general net theory, processes and systems (Hamburg, 1979), 84, Springer-Verlag, 1980.
• [24] Srba, J.: Timed-Arc Petri Nets vs. Networks of Timed Automata, Proceedings of the 26th International Conference on Application and Theory of Petri Nets (ICATPN 2005), 3536, Springer-Verlag, 2005.
• [25] Walter, B.: Timed Net forModeling and Analysing protocols with time, Proceedings of the IFIP Conference on Protocol Specification Testing and Verification, North Holland, 1983.