Investigating Reversibility of Steps in Petri Nets

• Autorzy: de Frutos Escrig David , Koutny Maciej , Mikulski Łukasz

Identyfikatory

DOI

10.3233/FI-2021-2082

• Języki publikacji: EN

Abstrakty

EN

In reversible computations one is interested in the development of mechanisms allowing to undo the effects of executed actions. The past research has been concerned mainly with reversing single actions. In this paper, we consider the problem of reversing the effect of the execution of groups of actions (steps). Using Petri nets as a system model, we introduce concepts related to this new scenario, generalising notions used in the single action case. We then present properties arising when reverse actions are allowed in place/transition nets (PT-nets). We obtain both positive and negative results, showing that allowing steps makes reversibility more problematic than in the interleaving/sequential case. In particular, we demonstrate that there is a crucial difference between reversing steps which are sets and those which are true multisets. Moreover, in contrast to sequential semantics, splitting reverses does not lead to a general method for reversing bounded PT-nets. We then show that a suitable solution can be obtained by combining split reverses with weighted read arcs.

Słowa kluczowe

EN

Petri net; reversible computation; step semantics; action splitting; net synthesis; direct reversibility; mixed reversibility; weighted activator arcs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 183, nr 1-2
• Strony: 67--96
• Opis fizyczny: Bibliogr. 27 poz., rys., wykr.

Twórcy

autor

de Frutos Escrig David

• Facultad de Ciencias Matemáticas, Universidad Complutense de Madrid

autor

Koutny Maciej

• School of Computing, Newcastle University, Newcastle

autor

Mikulski Łukasz

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University

Bibliografia

• [1] Danos V, Krivine J. Reversible Communicating Systems. In: Proc. of CONCUR’04, volume 3170 of LNCS, pp. 292-307. 2004. doi:10.1007/978-3-540-28644-8_19.
• [2] Danos V, Krivine J. Transactions in RCCS. In: Proc. of CONCUR’05, volume 3653 of LNCS, pp. 398-412. 2005. doi:10.1007/11539452_31.
• [3] Cohen M. Systems for financial and electronic commerce, 2013. US Patent 8,527,406.
• [4] Phillips I, Ulidowski I. Reversing algebraic process calculi. J. of Log. and Alg. Prog., 2007. 73(1-2):70-96. doi:10.1016/j.jlap.2006.11.002.
• [5] Lanese I, Mezzina C, Stefani JB. Reversing Higher-Order Pi. In: Proc. of CONCUR’10, volume 6269 of LNCS. 2010 pp. 478-493. doi:10.1007/978-3-642-15375-4_33.
• [6] Phillips I, Ulidowski I. Reversibility and asymmetric conflict in event structures. J. of Log. and Alg. Meth. in Prog., 2015. 84(6):781-805. doi:10.1016/j.jlamp.2015.07.004.
• [7] Cardelli L, Laneve C. Reversible structures. In: Proc. of CMSB’11. 2011 pp. 131-140. doi:10.1145/2037509.2037529.
• [8] Danos V, Krivine J, Sobocinski P. General Reversibility. Electr. Notes Theor. Comp. Sci., 2007. 175(3):75-86. doi:10.1016/j.entcs.2006.07.036.
• [9] Vos AD. Reversible Computing - Fundamentals, Quantum Computing, and Applications. 2010. doi:10.1002/9783527633999.
• [10] Esparza J, Nielsen M. Decidability issues for Petri nets. BRICS Report Series, 1994. 1(8).
• [11] Colange M, Baarir S, Kordon F, Thierry-Mieg Y. Crocodile: a Symbolic/Symbolic tool for the analysis of Symmetric Nets with Bag. In: Proc. of ATPN’11. Springer, 2011 pp. 338-347. doi:10.1007/978-3-642-21834-7_20.
• [12] Hujsa T, Delosme JM, Kordon AM. On the Reversibility of Live Equal-Conflict Petri Nets. In: Proc. of ATPN’15, volume 9115 of LNCS. 2015 pp. 234-253. doi:10.1007/978-3-319-19488-2_12.
• [13] Özkan H, Aybar A. A Reversibility Enforcement Approach for Petri Nets Using Invariants. WSEAS Transactions on Systems, 2008. 7:672-681. ISSN:1109-2777.
• [14] Melgratti HC, Mezzina CA, Ulidowski I. Reversing P/T Nets. In: COORDINATION 2019, volume 11533 of Lecture Notes in Computer Science. Springer, 2019 pp. 19-36. doi:10.1007/978-3-030-22397-7_2.
• [15] Philippou A, Psara K. Reversible Computation in Petri Nets. In: RC 2018, volume 11106 of Lecture Notes in Computer Science. Springer, 2018 pp. 84-101. arXiv:1804.04607 [cs.LO].
• [16] Barylska K, Koutny M, Mikulski Ł, Piątkowski M. Reversible computation vs. reversibility in Petri nets. Sci. Comput. Program., 2018. 151:48-60. doi:10.1016/j.scico.2017.10.008.
• [17] Bouziane Z, Finkel A. Cyclic Petri net reachability sets are semi-linear effectively constructible. In: Proc. of Infinity’97. 1997 pp. 15-24. doi:10.1016/S1571-0661(05)80423-2.
• [18] Mikulski Ł, Lanese I. Reversing Unbounded Petri Nets. In: Proc. of ATPN’19, volume 11522 of LNCS. Springer, 2019 pp. 213-233. doi:10.1007/978-3-030-21571-2_13.
• [19] Barylska K, Erofeev E, Koutny M, Mikulski Ł, Piątkowski M. Reversing Transitions in Bounded Petri Nets. Fundam. Inform., 2018. 157(4):341-357. doi:10.3233/FI-2018-1631.
• [20] Barylska K, Best E, Erofeev E, Mikulski Ł, Piątkowski M. Conditions for Petri Net Solvable Binary Words. ToPNoC, 2016. 11:137-159. doi:10.1007/978-3-662-53401-4_7.
• [21] Erofeev E, Barylska K, Mikulski Ł, Piątkowski M. Generating All Minimal Petri Net Unsolvable Binary Words. In: Proc. of PSC’16. 2016 pp. 33-46.
• [22] de Frutos-Escrig D, Koutny M, Mikulski Ł. An Efficient Characterization of Petri Net Solvable Binary Words. In: Proc. of ATPN’18. 2018 pp. 207-226. doi:10.1007/978-3-319-91268-4_11.
• [23] de Frutos-Escrig D, Koutny M, Mikulski Ł. Reversing Steps in Petri Nets. In: Proc. of ATPN’19, volume 11522 of LNCS. Springer, 2019 pp. 171-191. doi:10.1007/978-3-030-21571-2_11.
• [24] Kleijn H, Koutny M. Causality Semantics of Petri Nets with Weighted Inhibitor Arcs. In: Proc. of CONCUR’02, volume 2421 of LNCS. Springer, 2002 pp. 531-546. doi:10.1007/3-540-45694-5_35.
• [25] Badouel E, Darondeau P. Theory of Regions. In: LNCS 1491. 1996 pp. 529-586.
• [26] Darondeau P, Koutny M, Pietkiewicz-Koutny M, Yakovlev A. Synthesis of Nets with Step Firing Policies. Fundam. Inform., 2009. 94(3-4):275-303. doi:10.3233/FI-2009-132.
• [27] Reisig W. Understanding Petri Nets - Modeling Techniques, Analysis Methods, Case Studies. 2013. doi:10.1007/978-3-642-33278-4.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)