A Reversible Perspective on Petri Nets and Event Structures
Hernán Melgratti Claudio Antares Mezzina G. Michele Pinna
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 reversible causal nets, 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 post and preset of
transitions. In this way, we are able to operationally explain the full model
of reversible prime event structures.