Relating Distributed, Temporal and Causal Observations of Simple Processes¹

Article type: Research Article

Authors: Aceto, Luca

Affiliations: School of Cognitive and Computing Sciences, University of Sussex, Falmer, Brighton BN1 9QH, England, E-mail: luca@cogs.sussex.ac.uk

Note: [1] The work reported in this paper was mostly carried out while the author was at INRlA-Sophia Antipolis, France, and at the Hewlett-Packard Pisa Science Ceder, Pisa, Italy.

Abstract: The noninterleaving equivalences that have been proposed in the literature may be roughly divided into three classes, depending on the kind of observational scenarios underlying them. Some of them distinguish parallelism from nondeterminism by admitting explicit observations of the causal structure of systems; some others are based on the observation of distribution and still others on the assumption that actions have duration. In general, these three observational scenarios give rise to equivalences of incomparable discriminating power. In this paper, we show that three representative equivalences of the aforementioned classes, namely timed equivalence [Hen88], distributed bisimulation [CH89] and causal bisimulation [DD88], coincide over a language for finite parallel processes without communication and restriction. The proof of this result is algebraic in style and relies on a theorem giving a finite, ω-complete axiomatization of causal bisimulation over the language under consideration. We also give a model for our language based upon causal trees and prove that it is fully abstract with respect to the largest congruence contained in strong bisimulation and preserved by a very simple form of action refinement [AH89].

DOI: 10.3233/FI-1992-17406

Journal: Fundamenta Informaticae, vol. 17, no. 4, pp. 369-397, 1992