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.File | Dimensione | Formato | |
---|---|---|---|
HAL-lics.pdf Solo gestori archivio
Tipologia: versione post-print
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.