Contextual equivalences in configuration structures and reversibility

DOI10.1016/J.JLAMP.2016.08.004MaRDI QIDQ347363zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 7471661 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 7559463 (Why is no real title available?)
• 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)