Reversing Transitions in Bounded Petri Nets

• Autorzy: Barylska K. , Erofeev E. , Koutny M. , Mikulski Ł. , Piątkowski M.

Identyfikatory

DOI

10.3233/FI-2018-1631

• Języki publikacji: EN

Abstrakty

EN

Reversible computation deals with mechanisms for undoing the effects of actions executed by a dynamic system. This paper is concerned with reversibility in the context of Petri nets which are a general formal model of concurrent systems. A key construction we investigate amounts to adding ‘reverse’ versions of selected net transitions. Such a static modification can severely impact on the behaviour of the system, e.g., the problem of establishing whether the modified net has the same states as the original one is undecidable. We therefore concentrate on nets with finite state spaces and show, in particular, that every transition in such nets can be reversed using a suitable set of new transitions.

Słowa kluczowe

EN

Petri net; reversibility; reversible computation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 157, nr 4
• Strony: 341--357
• Opis fizyczny: Bibliogr. 14 poz., rys., tab.

Twórcy

autor

Barylska K.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Chopina 12/18, Poland

autor

Erofeev E.

• Parallel Systems, Department of Computing Science, Carl von Ossietzky Universität, D-26111 Oldenburg, Germany

autor

Koutny M.

• School of Computing Science, Newcastle University, Newcastle upon Tyne, NE1 7RU, United Kingdom

autor

Mikulski Ł.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Chopina 12/18, Poland

autor

Piątkowski M.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Chopina 12/18, Poland

Bibliografia

• [1] Berry G, and Boudol G. The chemical abstract machine. Theoretical Computer Science, 1992;96(1):217-248. URL https://doi.org/10.1016/0304-3975(92)90185-I.
• [2] Cardelli L, and Laneve C. Reversible structures. In: Fages F (ed.), Proceedings of 9th International Computational Methods in Systems Biology (CMSB’11). ACM, 2011 pp. 131-140. doi:10.1145/2037509.2037529.
• [3] Danos V, and Krivine J. Reversible Communicating Systems. In: Proceedings of 15th International Conference on Concurrency Theory (CONCUR’04), volume 3170 of Lecture Notes in Computer Science (LNCS), pp. 292-307. Springer-Verlag (New York), 2004. URL https://doi.org/10.1007/978-3-540-28644-8_19.
• [4] Danos V, and Krivine J. Transactions in RCCS. In: Proceedings of 16th International Conference on Concurrency Theory (CONCUR’05), volume 3653 of Lecture Notes in Computer Science (LNCS), pp.398-412. Springer-Verlag (New York), 2005. URL https://doi.org/10.1007/11539452_31.
• [5] Lanese I, Mezzina CA, and Stefani JB. Reversing Higher-Order Pi. In: Proceedings of 21th International Conference on Concurrency Theory (CONCUR’10), volume 6269 of Lecture Notes in Computer Science. Springer, 2010 pp. 478-493. URL https://doi.org/10.1007/978-3-642-15375-4_33.
• [6] Phillips I, and Ulidowski I. Reversibility and asymmetric conflict in event structures. Journal of Logic and Algebraic Methods in Programming, 2015;84(6):781-805. URL https://doi.org/10.1016/j.jlamp.2015.07.004.
• [7] Phillips I, Ulidowski I, and Yuen S. A Reversible Process Calculus and the Modelling of the ERK Signalling Pathway. In: Proceedings of 4th Workshop on Reversible Computation (RC’12), volume 7581 of Lecture Notes in Computer Science. Springer, 2012 pp. 218-232. URL https://doi.org/10.1007/978-3-642-36315-3_18.
• [8] Phillips I, and Ulidowski I. Reversing algebraic process calculi. Journal of Logic and Algebraic Programming, 2007;73(1-2):70-96. URL https://doi.org/10.1016/j.jlap.2006.11.002.
• [9] Danos V, Krivine J, Sobocinski P. General Reversibility. Electronic Notes Theoretical Computer Science, 2007;175(3):75-86. URL https://doi.org/10.1016/j.entcs.2006.07.036.
• [10] Barylska K, Koutny M, Mikulski Ł, and Piątkowski M. Reversible Computation vs. Reversibility in Petri Nets. In: Devitt S., Lanese I. (eds) Reversible Computation-Proceedings of the 8th International Conference RC 2016. Lecture Notes in Computer Science, vol. 9720. Springer, 2016 pp. 105-118. URL https://doi.org/10.1007/978-3-319-40578-0_7.
• [11] Barylska K, Mikulski L, Piatkowski M, Koutny M, and Erofeev E. Reversing Transitions in Bounded Petri Nets. In: Proceedings of the 25th International Workshop on Concurrency, Specification and Programming, Rostock, Germany, September 28-30, 2016 pp. 74-85. URL http://ceur-ws.org/Vol-1698.
• [12] Murata T. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 1989;77(4):541-580. doi: 10.1109/5.24143.
• [13] Barylska K, Best E, Erofeev E, Mikulski Ł, and Piątkowski M. On Binary Words Being Petri Net Solvable. Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data, ATAED, CEUR Workshop Proceedings, volume 1371, 2015 pp. 1-15. URL http://ceur-ws.org/Vol-1371.
• [14] Dickson LE. Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Amer. Journal Math., 1913;35:413-422. URL http://www.jstor.org/stable/2370405.

Uwagi

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