Contextual equivalences in configuration structures and reversibility

DOI10.1016/J.JLAMP.2016.08.004zbMATH Open1353.68193arXiv1511.05750OpenAlexW2963245642MaRDI QIDQ347363FDOQ347363

Authors: Clément Aubert, Ioana Cristescu 

Publication date: 30 November 2016

Published in: Journal of Logical and Algebraic Methods in Programming (Search for Journal in Brave)

Abstract: Contextual equivalence equate terms that have the same observable behaviour in any context. A standard contextual equivalence for CCS is the strong barbed congruence. Configuration structures are a denotational semantics for processes in which one define equivalences that are more discriminating, i.e. that distinguish the denotation of terms equated by barbed congruence. Hereditary history preserving bisimulation (HHPB) is such a relation. We define a strong back-and-forth barbed congruence on RCCS, a reversible variant of CCS. We show that the relation induced by the back-and-forth congruence on configuration structures is equivalent to HHPB, thus providing a contextual characterization of HHPB.

Full work available at URL: https://arxiv.org/abs/1511.05750

Recommendations

• Reversibility of extreme relational structures
• Reverse bisimulations on stable configuration structures
• Contextual isomorphisms
• Reversibility and determinism in sequential multiset rewriting
• A hierarchy of reverse bisimulations on stable configuration structures
• Reversibility in the higher-order \(\pi\)-calculus
• Concurrencies in reversible concurrent calculi
• Conditionally reversible computations and weak universality in category theory

zbMATH Keywords

process algebrasformal semanticsprocess calculicontextual characterizationhereditary history-preserving bisimulationreversible CCSstrong barbed congruence

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Semantics in the theory of computing (68Q55) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• Bisimulation from open maps
• Reversing algebraic process calculi
• Reversing Higher-Order Pi
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A compositional semantics for the reversible \(\pi\)-calculus
• CONCUR 2004 - Concurrency Theory
• CONCUR 2005 – Concurrency Theory
• Refinement of actions and equivalence notions for concurrent systems
• Configuration structures, event structures and Petri nets
• On reduction-based process semantics
• Barbed bisimulation
• On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes
• Self-assembling trees
• Reversibility and models for concurrency
• A hierarchy of reverse bisimulations on stable configuration structures
• Evaluating functions as processes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reversible barbed congruence on configuration structures
• A logic for true concurrency
• Bisimulation and action refinement

Cited In (14)

• Reversible barbed congruence on configuration structures
• Concurrencies in reversible concurrent calculi
• Event structures for the reversible early internal \(\pi\)-calculus
• The correctness of concurrencies in (reversible) concurrent calculi
• Title not available (Why is that?)
• A hierarchy of reverse bisimulations on stable configuration structures
• Static versus dynamic reversibility in CCS
• Towards a categorical representation of reversible event structures
• Reverse bisimulations on stable configuration structures
• Title not available (Why is that?)
• Explicit Identifiers and Contexts in Reversible Concurrent Calculus
• Comparative Transition System Semantics for Cause-Respecting Reversible Prime Event Structures
• Event structure semantics of (controlled) reversible CCS
• Forward-reverse observational equivalences in CCSK

This page was built for publication: Contextual equivalences in configuration structures and reversibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q347363)