Reversible prime event structures extend the well-known model of prime event structures to represent reversible computational processes. Essentially, they give abstract descriptions of processes capable of undoing computation steps. Since their introduction, event structures have played a pivotal role in connecting operational models (traditionally, Petri nets and process calculi) with denotational ones (algebraic domains). For this reason, there has been a lot of interest in linking different classes of operational models with different kinds of event structures. Hence, it is natural to ask which is the operational counterpart of reversible prime event structures. Such question has been previously addressed for a subclass of reversible prime event structures in which the interplay between causality and reversibility is restricted to the so-called cause-respecting reversible structures. In this paper, we present an operational characterisation of the full-fledged model and show that reversible prime event structures correspond to a subclass of conual Petri nets, called reversible causal nets. The distinctive feature of reversible causal nets is that causality is recovered from inhibitor arcs instead of the usual overlap between post and presets of transitions. In this way, we are able to operationally explain also out-of-causal order reversibility.

A distributed operational view of Reversible Prime Event Structures

Michele Pinna G.
Co-primo
2021-01-01

Abstract

Reversible prime event structures extend the well-known model of prime event structures to represent reversible computational processes. Essentially, they give abstract descriptions of processes capable of undoing computation steps. Since their introduction, event structures have played a pivotal role in connecting operational models (traditionally, Petri nets and process calculi) with denotational ones (algebraic domains). For this reason, there has been a lot of interest in linking different classes of operational models with different kinds of event structures. Hence, it is natural to ask which is the operational counterpart of reversible prime event structures. Such question has been previously addressed for a subclass of reversible prime event structures in which the interplay between causality and reversibility is restricted to the so-called cause-respecting reversible structures. In this paper, we present an operational characterisation of the full-fledged model and show that reversible prime event structures correspond to a subclass of conual Petri nets, called reversible causal nets. The distinctive feature of reversible causal nets is that causality is recovered from inhibitor arcs instead of the usual overlap between post and presets of transitions. In this way, we are able to operationally explain also out-of-causal order reversibility.
2021
978-1-6654-4895-6
Petri Nets, Reversibility; Event Structures
File in questo prodotto:
File Dimensione Formato  
HAL-lics.pdf

Solo gestori archivio

Tipologia: versione post-print (AAM)
Dimensione 521.9 kB
Formato Adobe PDF
521.9 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/324837
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 6
social impact