{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,24]],"date-time":"2024-10-24T04:22:41Z","timestamp":1729743761555,"version":"3.28.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"\n Event structures have emerged as a foundational model for concurrent computation, explaining computational processes by outlining the events and the relationships that dictate their execution. They play a pivotal role in the study of key aspects of concurrent computation models, such as causality and independence, and have found applications across a broad range of languages and models, spanning realms like persistence, probabilities, and quantum computing. Recently, event structures have been extended to address reversibility, where computational processes can undo previous computations. In this context, reversible event structures provide abstract representations of processes capable of both forward and backward steps in a computation. Since their introduction, event structures have played a crucial role in bridging operational models, traditionally exemplified by Petri nets and process calculi, with denotational ones, i.e., algebraic domains. In this context, we revisit the standard connection between Petri nets and event structures under the lenses of reversibility. Specifically, we introduce a subset of contextual Petri nets, dubbed\n reversible causal nets<\/jats:italic>\n , that precisely correspond to reversible prime event structures. The distinctive feature of reversible causal nets lies in deriving causality from inhibitor arcs, departing from the conventional dependence on the overlap between the postset and preset of transitions. In this way, we are able to operationally explain the full model of reversible prime event structures.\n <\/jats:p>","DOI":"10.1145\/3686154","type":"journal-article","created":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T16:21:45Z","timestamp":1722615705000},"page":"1-38","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Reversible Perspective on Petri Nets and Event Structures"],"prefix":"10.1145","volume":"25","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-0760-0618","authenticated-orcid":false,"given":"Hern\u00e1n","family":"Melgratti","sequence":"first","affiliation":[{"name":"ICC\u2014 Universidad de Buenos Aires, Conicet, Buenos Aires, Argentina"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-1556-2623","authenticated-orcid":false,"given":"Claudio Antares","family":"Mezzina","sequence":"additional","affiliation":[{"name":"Dipartimento di Scienze Pure e Applicate, Universit\u00e0 di Urbino, Urbino, Italy"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-8911-1580","authenticated-orcid":false,"given":"G. Michele","family":"Pinna","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, Universit\u00e0 di Cagliari, Cagliari, Italy"}]}],"member":"320","published-online":{"date-parts":[[2024,10,23]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-47361-7_1"},{"key":"e_1_3_2_3_2","first-page":"1","article-title":"Domain and Event Structure Semantics for Petri Nets with Read and Inhibitor Arcs","volume":"323","author":"Baldan Paolo","year":"2004","unstructured":"Paolo Baldan, Nadia Busi, Andrea Corradini, and G. Michele Pinna. 2004. Domain and Event Structure Semantics for Petri Nets with Read and Inhibitor Arcs. Theoretical Computer Science 323, 1\u20133 (2004), 129\u2013189.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_4_2","series-title":"CEUR Workshop Proceedings","first-page":"91","volume-title":"International Workshop on Algorithms & Theories for the Analysis of Event Data 2018 Satellite Event of the Conferences: 39th International Conference on Application and Theory of Petri Nets and Concurrency Petri Nets 2018 and 18th International Conference on Application of Concurrency to System Design ACSD","volume":"2115","author":"Barylska Kamila","year":"2018","unstructured":"Kamila Barylska, Anna Gogolinska, Lukasz Mikulski, Anna Philippou, Marcin Piatkowski, and Kyriaki Psara. 2018. Reversing Computations Modelled by Coloured Petri Nets. In International Workshop on Algorithms & Theories for the Analysis of Event Data 2018 Satellite Event of the Conferences: 39th International Conference on Application and Theory of Petri Nets and Concurrency Petri Nets 2018 and 18th International Conference on Application of Concurrency to System Design ACSD. CEUR Workshop Proceedings, Vol. 2115. CEUR-WS.org, 91\u2013111. DOI: http:\/\/ceur-ws.org\/Vol-2115"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-53479-2_4"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07734-5_10"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"1326","DOI":"10.1145\/3019612.3019806","volume-title":"SAC 2017","author":"Casu Giovanni","year":"2017","unstructured":"Giovanni Casu and G. Michele Pinna. 2017. Petri Nets and Dynamic Causality for Service-Oriented Computations. In SAC 2017. Ahmed Seffah, Birgit Penzenstadler, Carina Alves, and Xin Peng (Eds.). ACM, 1326\u20131333. DOI: 10.1145\/3019612.3019806"},{"key":"e_1_3_2_8_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1007\/11539452_31","volume-title":"Concurrency Theory, 16th International Conference, CONCUR 2005","volume":"3653","author":"Danos Vincent","year":"2005","unstructured":"Vincent Danos and Jean Krivine. 2005. Transactions in RCCS. In Concurrency Theory, 16th International Conference, CONCUR 2005. Lecture Notes in Computer Science, Vol. 3653. Springer, 398\u2013412. DOI: 10.1007\/11539452_31"},{"volume-title":"Software Architecture: The Hard Parts","year":"2021","author":"Ford Neal","key":"e_1_3_2_9_2","unstructured":"Neal Ford, Mark Richards, Pramod Sadalage, and Zhamak Dehghani. 2021. Software Architecture: The Hard Parts. O\u2019Reilly Media, Inc."},{"key":"e_1_3_2_10_2","first-page":"249","volume-title":"Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference","author":"Garcia-Molina Hector","year":"1987","unstructured":"Hector Garcia-Molina and Kenneth Salem. 1987. Sagas. In Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference. Umeshwar Dayal and Irving L. Traiger (Eds.). ACM Press, 249\u2013259. DOI: 10.1145\/38713.38742"},{"key":"e_1_3_2_11_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1007\/978-3-642-54804-8_26","volume-title":"Fundamental Approaches to Software Engineering\u201417th International Conference, FASE 2014","volume":"8411","author":"Giachino Elena","year":"2014","unstructured":"Elena Giachino, Ivan Lanese, and Claudio Antares Mezzina. 2014. Causal-Consistent Reversible Debugging. In Fundamental Approaches to Software Engineering\u201417th International Conference, FASE 2014. Lecture Notes in Computer Science, Vol. 8411. Springer, 370\u2013384. DOI: 10.1007\/978-3-642-54804-8_26"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-47361-7_7"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37036-6_21"},{"key":"e_1_3_2_14_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/978-3-030-21759-4_10","volume-title":"Formal Techniques for Distributed Objects, Components, and Systems\u201439th IFIP WG 6.1 International Conference, FORTE 2019","volume":"11535","author":"Lanese Ivan","year":"2019","unstructured":"Ivan Lanese, Adri\u00e1n Palacios, and Germ\u00e1n Vidal. 2019. Causal-Consistent Replay Debugging for Message Passing Programs. In Formal Techniques for Distributed Objects, Components, and Systems\u201439th IFIP WG 6.1 International Conference, FORTE 2019. Lecture Notes in Computer Science, Vol. 11535. Springer, 167\u2013184. DOI: 10.1007\/978-3-030-21759-4_10"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3648474"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/MITP.2021.3117920"},{"key":"e_1_3_2_17_2","first-page":"331","volume-title":"FORTE \u201992 Conference Proceedings","volume":"10","author":"Langerak Rom","year":"1993","unstructured":"Rom Langerak. 1993. Bundle Event Structures: A Non-interleaving Semantics for LOTOS. In FORTE \u201992 Conference Proceedings. IFIP Transactions, Vol. C-10. Michel Diaz and Roland Groz (Eds.). North-Holland, 331\u2013346."},{"key":"e_1_3_2_18_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/978-3-030-52482-1_16","volume-title":"Reversible Computation\u201412th International Conference, RC 2020","volume":"12227","author":"Medic Doriana","year":"2020","unstructured":"Doriana Medic, Claudio Antares Mezzina, Iain Phillips, and Nobuko Yoshida. 2020. Towards a Formal Account for Software Transactional Memory. In Reversible Computation\u201412th International Conference, RC 2020. Lecture Notes in Computer Science, Vol. 12227. Springer, 255\u2013263. DOI: 10.1007\/978-3-030-52482-1_16"},{"key":"e_1_3_2_19_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-3-030-52482-1_2","volume-title":"Reversible Computation\u201412th International Conference, RC 2020","volume":"12227","author":"Melgratti Hern\u00e1n C.","year":"2020","unstructured":"Hern\u00e1n C. Melgratti, Claudio Antares Mezzina, Iain Phillips, G. Michele Pinna, and Irek Ulidowski. 2020b. Reversible Occurrence Nets and Causal Reversible Prime Event Structures. In Reversible Computation\u201412th International Conference, RC 2020. Lecture Notes in Computer Science, Vol. 12227. Springer, 35\u201353. DOI: 10.1007\/978-3-030-52482-1"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470623"},{"issue":"4","key":"e_1_3_2_21_2","first-page":"5:1","article-title":"Reversing Place Transition Nets","volume":"16","author":"Melgratti Hern\u00e1n C.","year":"2020","unstructured":"Hern\u00e1n C. Melgratti, Claudio Antares Mezzina, and Irek Ulidowski. 2020a. Reversing Place Transition Nets. Logical Methods in Computer Science 16, 4 (2020), 5:1\u20135:28. DOI: https:\/\/lmcs.episciences.org\/6843","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-47361-7_1"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01178907"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90112-2"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667"},{"key":"e_1_3_2_26_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/978-3-319-99498-7_6","volume-title":"Reversible Computation\u201410th International Conference, (RC \u201918)","volume":"11106","author":"Philippou Anna","year":"2018","unstructured":"Anna Philippou and Kyriaki Psara. 2018. Reversible Computation in Petri Nets. In Reversible Computation\u201410th International Conference, (RC \u201918). Lecture Notes in Computer Science, Vol. 11106. Jarkko Kari and Irek Ulidowski (Eds.). Springer, 84\u2013101. DOI: 10.1007\/978-3-319-99498-7_6"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.JLAMP.2015.07.004"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36315-3_18"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21834-7_7"},{"volume-title":"Microservices Patterns: With Examples in Java","year":"2018","author":"Richardson Chris","key":"e_1_3_2_30_2","unstructured":"Chris Richardson. 2018. Microservices Patterns: With Examples in Java. Simon and Schuster."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1995.523257"},{"key":"e_1_3_2_32_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1007\/978-3-540-28629-5_42","volume-title":"MFCS\u201904 Conference Proceedings","volume":"3153","author":"Glabbeek Rob J. van","year":"2004","unstructured":"Rob J. van Glabbeek and Gordon D. Plotkin. 2004. Event Structures for Resolvable Conflict. In MFCS\u201904 Conference Proceedings. Lecture Notes in Computer Science, Vol. 3153. Jir\u00ed Fiala, V\u00e1clav Koubek, and Jan Kratochv\u00edl (Eds.). Springer, 550\u2013561. DOI: 10.1007\/978-3-540-28629-5_42"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.014"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-17906-2_31"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3686154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T16:05:08Z","timestamp":1729699508000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3686154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,23]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3686154"],"URL":"https:\/\/doi.org\/10.1145\/3686154","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2024,10,23]]},"assertion":[{"value":"2023-12-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
