DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2020.7

How Reversibility Can Solve Traditional Questions: The Example of Hereditary History-Preserving Bisimulation

Authors: Clément Aubert and Ioana Cristescu

Published in: LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)

Abstract

Reversible computation opens up the possibility of overcoming some of the hardware’s current physical limitations. It also offers theoretical insights, as it enriches multiple paradigms and models of computation, and sometimes retrospectively enlightens them. Concurrent reversible computation, for instance, offered interesting extensions to the Calculus of Communicating Systems, but was still lacking a natural and pertinent bisimulation to study processes equivalences. Our paper formulates an equivalence exploiting the two aspects of reversibility: backward moves and memory mechanisms. This bisimulation captures classical equivalences relations for denotational models of concurrency (history- and hereditary history-preserving bisimulation, (H)HPB), that were up to now only partially characterized by process algebras. This result gives an insight on the expressiveness of reversibility, as both backward moves and a memory mechanism - providing "backward determinism" - are needed to capture HHPB.

Cite as

Clément Aubert and Ioana Cristescu. How Reversibility Can Solve Traditional Questions: The Example of Hereditary History-Preserving Bisimulation. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aubert_et_al:LIPIcs.CONCUR.2020.7,
  author =	{Aubert, Cl\'{e}ment and Cristescu, Ioana},
  title =	{{How Reversibility Can Solve Traditional Questions: The Example of Hereditary History-Preserving Bisimulation}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Konnov, Igor and Kov\'{a}cs, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.7},
  URN =		{urn:nbn:de:0030-drops-128196},
  doi =		{10.4230/LIPIcs.CONCUR.2020.7},
  annote =	{Keywords: Formal semantics, Process algebras and calculi, Distributed and reversible computation, Configuration structures, Reversible CCS, Bisimulation}
}

Search Results

Documents authored by Cristescu, Ioana

How Reversibility Can Solve Traditional Questions: The Example of Hereditary History-Preserving Bisimulation

Abstract

Cite as

Thanks for your feedback!

Could not send message