Full Axiomatisation of Timed Processes of Interval-Timed Petri Nets

• Autorzy: Pelz E.

Identyfikatory

DOI

10.3233/FI-2018-1636

• Języki publikacji: EN

Abstrakty

EN

In this paper we use partial order semantics to express the truly concurrent behaviour of Interval-Timed Petri nets (ITPNs) in their most general setting, i.e. with autoconcurrency and zero duration, as studied with its standard maximal step semantics in [1]. First we introduce the notion of timed processes for ITPNs inductively. Then we investigate if the equivalence of inductive and axiomatic process semantics - true for classical Petri nets - could hold for ITPNs too. We will see that the notions of independence and immediate firing obligation seem to be antagonistic ones, and that local axioms, adequate to define processes of classical Petri nets, are not sufficient to caracterize timed processes of ITPNs. We propose several original “global” axioms which reveal to be an effective solution. Thus we yield finally a full axiomatic definition of timed processes for ITPNs.

Słowa kluczowe

EN

Petri nets; axiomatic set theory; semantics; integer approximations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 157, nr 4
• Strony: 427--442
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Pelz E.

• LACL, Université Paris-Est Créteil, France

Bibliografia

• [1] Pelz E, Kabouche A, Popova-Zeugmanm L. Interval-Timed Petri Nets with Auto-concurrent Semantics and their State Equation. In: Proc. of International Workshop on Petri Nets and Software Engineering (PNSE’15), CEUR Workshop, 2015 pp. 245-265. URL http://ceur-ws.org/Vol-1372.
• [2] Petri CA. Fundamentals of a Theory of Asynchronous Information Flow. In: IFIP Congress. North-Holland, 1962 pp. 386-391. URL http://dblp.uni-trier.de/db/conf/ifip/ifip1962.html#Petri62.
• [3] Merlin P. A Study of the Recoverability of Communication Protocols. Ph.D. thesis, Irvine, 1974.
• [4] Ramchandani C. Analysis of Asynchronous Concurrent Systems by Timed Petri Nets. Project MAC-TR 120, MIT, 1974. doi:MIT-LCS-TR-120.pdf.
• [5] Heiner M, Popova-Zeugmann L. Worst-case Analysis of Concurent Systems with Duration Interval Petri Nets. In: Schnieder E, Abel D (eds.), Entwurf komplexer Automatisierungssysteme. TU Braunschweig, IfRA, 1997. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.2471&rep=rep1&type=pdf.
• [6] Starke PH. Processes in Petri Nets. Elektronische Informationsverarbeitung und Kybernetik, 1981;17(8/9):389-416.
• [7] Best E, Fernández C. Nonsequential Processes-A Petri Net View, volume 13 of EATCS Monographs on Theoretical Computer Science. Springer, 1988. doi:10.1007/978-3-642-73483-0.
• [8] Aura T, Lilius J. Time Processes for Time Petri-Nets. In: Proc. of 18th International Conference ICATPN ’97, volume 1248 of LNCS. Springer, 1997 pp. 136-155. URL https://doi.org/10.1007/3-540-63139-9_34.
• [9] Valero Ruiz V, de Frutos-Escrig D, Cuartero F. Timed Processes of Timed Petri Nets. In: Proc. of 16th International Conference, ICATPN ’95, volume 616 of LNCS. Springer, 1995 pp. 490-509. URL https://doi.org/10.1007/3-540-60029-9_56.
• [10] Fleischhack H, Stehno C. Computing a Finite Prefix of a Time Petri Net. In: Proc. of 23th International Conference ICATPN’02, volume 2360 of LNCS, 2002 pp. 163-181. URL https://doi.org/10.1007/3-540-48068-4_11.
• [11] Fleischhack H, Pelz E. Hierarchical Timed High Level Nets and their Branching Processes. In: Proc. of 24th International Conference ICATPN’03, volume 2679 of LNCS. Springer, 2003 pp. 397-416. URL https://doi.org/10.1007/3-540-44919-1_25.
• [12] Winkowski J. Algebras of Processes of Timed Petri Nets. In: Proc. of 5th International Conference CONCUR ’94, volume 836 of LNCS. Springer, 1994 pp. 194-209. URL https://doi.org/10.1007/978-3-540-48654-1_18.
• [13] Best E, Devillers R. Sequential and Concurrent Behaviour in Petri Net Theory. Theoretical Computer Science, 1987;55(1):87-136. URL https://doi.org/10.1016/0304-3975(87)90090-9.
• [14] Bui Thanh C, Klaudel H, Pommereau F. Petri nets with causal time for system verification. Electr. Notes Theor. Comput. Sci., 2002;68(5):85-100. URL https://doi.org/10.1016/S1571-0661(04)80521-8.
• [15] Goltz U, Reisig W. The Non-sequential Behavior of Petri Nets. Information and Control, 1983;57(2/3):125-147. URL https://doi.org/10.1016/S0019-9958(83)80040-0.
• [16] Pelz E. Timed Processes of Interval-Timed Petri Nets. In: Concurrency, Specification and Programming, CS&P 2016, 2016 pp. 13-24. URL http://ceur-ws.org/Vol-1698.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).