True Concurrent Equivalences in Time Petri Nets

• Autorzy: Virbitskaite I. , Bushin D. , Best E.

Identyfikatory

DOI

10.3233/FI-2016-1454

• Języki publikacji: EN

Abstrakty

EN

The intention of the paper is towards a framework for developing, studying and comparing observational equivalences in the setting of a real-time true concurrent model. In particular, we introduce a family of trace and bisimulation equivalences in interleaving, step, partial order and causal net semantics in the setting of time Petri nets (elementary net systems whose transitions are labeled with time firing intervals, can fire only if their lower time bounds are attained, and are forced to fire when their upper time bounds are reached) [3]. We deal with the relationships between the equivalences showing the discriminating power of the approaches of the linear-time - branching-time and interleaving - partial order spectra and construct a hierarchy of equivalent classes of time Petri nets. This allows studying in complete detail the timing behaviour in addition to the degrees of relative concurrency and nondeterminism of processes.

Słowa kluczowe

EN

homotopy equivalences; Petri nets; bisimulation; interval analysis; set theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 149, nr 4
• Strony: 401--418
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Virbitskaite I.

• A.P. Ershov Institute of Informatics Systems, SB RAS 6, Acad. Lavrentiev avenue, 630090, Novosibirsk, Russia
• Novosibirsk State University 2, Pirogova st., Novosibirsk, 630090, Russia

autor

Bushin D.

• A.P. Ershov Institute of Informatics Systems, SB RAS 6, Acad. Lavrentiev avenue, 630090, Novosibirsk, Russia

autor

Best E.

• Carl von Ossietzky University of Oldenburg, Ammerlaender Heerstrasse 114-118, 26129 Oldenburg, Germany

Bibliografia

• [1] Vogler W. Modular Construction and Partial Order Semantics of Petri Nets. vol. 625 of Lecture Notes in Computer Science, 1992. ISBN:978-3-540-47282-7.
• [2] Tarasyuk IV. Equivalences for Behavioural Analysis of Concurrent and Distributed Computing Systems. – 2007. ”Geo” Publisher, Novosibirsk, 321 pages (in Russian).
• [3] Aura T, Lilius J. Time Processes for Time Petri Nets. in: 18th International Conference, ICATPN’97 Toulouse, France, 1997 Proceedings. vol. 1248 of Lecture Notes in Computer Science, 1997 p. 136–155. doi:10.1007/3-540-63139-9_34.
• [4] Bihler E, Vogler W. Timed Petri Nets: Efficiency of Asynchronous Systems. in: International School on Formal Methods for the Design of Computer, Communication, and Software Systems, Bertinora, Italy, 2004, Revised Lectures. vol. 3185 of Lecture Notes in Computer Science, 2004 p. 25–58. doi:10.1007/978-3-540-30080-9_2.
• [5] Chatain T, Jard C. Time Supervision of Concurrent Systems Using Symbolic Unfoldings of Time Petri Nets. in: Third International Conference, FORMATS 2005, Uppsala, Sweden, 2005. Proceedings. vol. 3829 of Lecture Notes in Computer Science, 2005 p. 196–210. doi:10.1007/11603009_16.
• [6] Cherief F. Back and Forth Bisimulations on Prime Event Structures. in: 4th International PARLE Conference Paris, France, 1992 Proceedings. vol. 605 of Lecture Notes in Computer Science, 1992 p. 841–858. doi:10.1007/3-540-55599-4_128.
• [7] De Nicola R, Montanari U, Vaandrager F. Back and Forth Bisimulations. in: CONCUR ’90 Theories of Concurrency: Unification and Extension Amsterdam, The Netherlands, 1990 Proceedings. vol. 458 of Lecture Notes in Computer Science, 1990 p. 152–165. Available from: http://dl.acm.org/citation.cfm?id=111970.111983.
• [8] Pomello L, Rozenberg G, Simone C. A Survey of Equivalence Notions for Net Based Systems. in: Advances in Petri Nets 1992, The DEMON Project Proceedings. vol. 609 of Lecture Notes in Computer Science, 1992 p. 410–472. doi:10.1007/3-540-55610-9_180.
• [9] Rozenberg G, Engelfriet J. Elementary Net Systems. in: Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, the Volumes Are Based. Proceedings. vol. 1491 of Lecture Notes in Computer Science, 1998 p. 12–121. Available from: http://dl.acm.org/citation.cfm?id=647444.727059.
• [10] Valero V, de Frutos D, Cuartero F. Timed Processes of Timed Petri Nets. in: 16th International Conference Turin, Italy, 1995 Proceedings. vol. 935 of Lecture Notes in Computer Science, 1995 p. 490–509. doi:10.1007/3-540-60029-9_56.
• [11] van Glabbeek R, Goltz U. Equivalence Notions for Concurrent Systems and Refinement of Action. in: Porabka-Kozubnik, Poland, 1989 Proceedings. vol. 379 of Lecture Notes in Computer Science, 1989, p. 237-248. doi:10.1007/3-540-51486-4_71.
• [12] Winkowski J. Algebras of Processes of Timed Petri Nets. in: 5th International Conference, Uppsala, Sweden, 1994, Proceedings. vol. 480 of Lecture Notes in Computer Science, 1994 p. 309–321.
• [13] Andreeva MV, Virbitskaite IB. Timed Observational Equivalences for Timed Stable Event Structures. Fundamenta Informaticae 2006;72(4):1–19. Available from: http://dl.acm.org/citation.cfm?id=2369376.2369378.
• [14] Best E, Devillers R, Kiehn A, Pomello L. Concurrent Bisimulations in Petri Nets. Acta Informatica 1991;28(3):231-264. doi:10.1007/BF01178506.
• [15] Boyer M, Roux OH. On the Compared Expressiveness of Arc, Place and Transition Time Petri Nets. Fundamenta Informaticae 2008;88(3):225–249. Available from: http://dl.acm.org/citation.cfm?id=1497079.1497081.
• [16] Devillers R. On the Definition of a Bisimulation Notion Based on Partial Words. Petri Net Newsletter 1988;29:16-19. Available from: issn:0931-1084.
• [17] Fecher H. A Completed Hierarchy of True Concurrent Equivalences. Information Processing Letters 2004;89(5):261-265. doi:10.1016/j.ipl.2003.11.008.
• [18] Rabinovich A, Trakhtenbrot BA. Behavior Structures and Nets. Fundamenta Informaticae 1988;11:357–404.
• [19] Pinchinat S. Bisimulations for the Semantics of Reactive Systems. Ph.D. thesis, Institut National Politechnique de Grenoble, January 1993 (in French).

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).