Computing Publications

Publications Home » Reversibility and models for conc...

Reversibility and models for concurrency

Iain Phillips, Irek Ulidowski

Conference or Workshop Paper
International Workshop on Structural Operational Semantics 2007
October, 2007
Volume 192
Issue 1
DOI 10.1016/j.entcs.2007.08.018

There is a growing interest in models of reversible computation driven by exciting application areas such as bio-systems and quantum computing. Reversible process algebras RCCS and CCSK were developed and general techniques for reversing other process operators were proposed. The paper shows that the notion of reversibility can bridge the gap between some interleaving models and non-interleaving models of concurrency, and makes them interchangeable. We prove that transition systems associated with reversible process algebras are equivalent as models to labelled prime event structures. Furthermore, we show that forward-reverse bisimulation corresponds to hereditary history-preserving bisimulation in the setting with no auto-concurrency and no auto-causation.

BibTEX file for the publication built & maintained by Ashok Argent-Katwala.