Acyclic and Cyclic Reversing Computations in Petri Nets

• Autorzy: Barylska Kamila , Gogolińska Anna

Identyfikatory

DOI

10.3233/FI-2021-2099

• Języki publikacji: EN

Abstrakty

EN

Reversible computations constitute an unconventional form of computing where any sequence of performed operations can be undone by executing in reverse order at any point during a computation. It has been attracting increasing attention as it provides opportunities for low-power computation, being at the same time essential or eligible in various applications. In recent work, we have proposed a structural way of translating Reversing Petri Nets (RPNs) – a type of Petri nets that embeds reversible computation, to bounded Coloured Petri Nets (CPNs) – an extension of traditional Petri Nets, where tokens carry data values. Three reversing semantics are possible in RPNs: backtracking (reversing of the lately executed action), causal reversing (action can be reversed only when all its effects have been undone) and out of causal reversing (any previously performed action can be reversed). In this paper, we extend the RPN to CPN translation with formal proofs of correctness. Moreover, the possibility of introduction of cycles to RPNs is discussed. We analyze which type of cycles could be allowed in RPNs to ensure consistency with the current semantics. It emerged that the most interesting case related to cycles in RPNs occurs in causal semantics, where various interpretations of dependency result in different net’s behaviour during reversing. Three definitions of dependence are presented and discussed.

Słowa kluczowe

EN

Computer Science - Computation and Language; Computer Science - Programming Languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 184, nr 4
• Strony: 273--296
• Opis fizyczny: Bibliogr. 18 poz., rys.

Twórcy

autor

Barylska Kamila

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Poland.

autor

Gogolińska Anna

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Poland.

Bibliografia

• [1] Araki T, Kasami T. Decidable Problems on the Strong Connectivity of Petri Net Reachability Sets. Theoretical Computer Science 4, 1977 pp. 99-119. doi:10.4230/LIPIcs.FSTTCS.2011.140.
• [2] Barylska K, Gogolinska A, Mikulski Ł, Philippou A, Pi ˛atkowski M, Psara K. Reversing Computations Modelled by Coloured Petri Nets. Proceedings of ATAED 2018, pp. 91-111. URL http://gnosis.library.ucy.ac.cy/handle/7/62364.
• [3] Barylska K, Evgeny E, Koutny M, Mikulski Ł, Pi ˛atkowski M. Reversing transitions in bounded Petri nets. Fundamenta Informaticae 2018. 157(4):341-357. doi:10.3233/FI-2018-1631.
• [4] Barylska K, M. Koutny, Ł. Mikulski, M. Piątkowski. Reversible computation vs. reversibility in Petri nets. Science of Computer Programming 151, 2018 pp. 48-60. doi:10.1016/j.scico.2017.10.008.
• [5] Best E, Desel J, Esparza J. Traps characterize home states in free choice systems. Theoretical Computer Science 1992. 101(2):161-176. doi:10.1016/0304-3975(92)90048-K.
• [6] Bouziane Z, Finkel A. Cyclic petri net reachability sets are semi-linear effectively constructible. Electronic Notes in Theoretical Computer Science 1997. 9:15-24. doi:10.1016/S1571-0661(05)80423-2.
• [7] Esparza J, Nielsen M. Decidability Issues for Petri Nets - a survey. J. Inf. Process. Cybern. 1994. 30(3):143-160.
• [8] de Frutos Escrig D, Koutny M, Mikulski Ł. An efficient characterization of Petri net solvable binary words. International Conference on Applications and Theory of Petri Nets and Concurrency. Springer, Cham, 2018 pp. 207-226. doi:10.1007/978-3-319-91268-4_11.
• [9] de Frutos Escrig D, Koutny M, Mikulski Ł. Reversing steps in Petri nets. Application and Theory of Petri Nets and Concurrency, 40th International Conference, PETRI NETS 2019 Proceedings, 2019 pp. 171-191. doi:10.1007/978-3-030-21571-2_11.
• [10] Jensen K, Kristensen LM. Coloured Petri Nets - Modelling and Validation of Concurrent Systems. Springer, 2009. ISBN-10:364242581X, 13:978-3642425813.
• [11] Melgratti H, Antares Mezzina C, Ulidowski I. Reversing P/T Nets. International Conference on Coordination Languages and Models. Springer, Cham, 2019. doi:10.23638/LMCS-16(4:5)2020.
• [12] Mikulski Ł, Lanese I. Reversing unbounded Petri nets. International Conference on Applications and Theory of Petri Nets and Concurrency. Springer, Cham, 2019. doi:10.1007/978-3-030-21571-2_13.
• [13] Philippou A, Psara K. Reversible computation in Petri nets. International Conference on Reversible Computation. Springer, Cham, LNCS vol 11106. 2018 pp. 84-101. doi:10.1007/978-3-319-99498-7_6.
• [14] Philippou A, and Psara K. Reversible computation in Cyclic Petri nets. Submitted for publication. 2020, ID:222208545.
• [15] Ratzer AV, Wells L, Lassen HM, Laursen M, Qvortrup JF, Stissing MS, Westergaard M, Christensen S, Jensen K. CPN tools for editing, simulating, and analysing coloured Petri nets. Proceedings of ICATPN 2003, LNCS vol. 2679, Springer, 2003 pp. 450-462. doi:10.1007/3-540-44919-1_28.
• [16] Reisig W. Understanding Petri Nets - Modeling Techniques, Analysis Methods, Case Studies. Springer, 2013. doi:10.1007/978-3-642-33278-4.
• [17] Schordan M, Jefferson D, Barnes P, Oppelstrup T, Quinlan D. Reverse code generation for parallel discrete event simulation. International Conference on Reversible Computation, Springer, Cham, 2015 pp. 95-110. doi:10.1007/978-3-319-20860-2_6.
• [18] CPN Tools project website, http://cpntools.org/

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)