Trace, failure and testing equivalences for communicating processes
type: Item
instance of: scholarly article
title: Trace, failure and testing equivalences for communicating processes
zbMATH Open document ID: 0646.68033
DOI: 10.1007/BF01407903
published in: International Journal of Parallel Programming
publication date: 1987-01-01T00:00:00Z
review text: A basic question in the theory of communicating processes is ``When should two processes be considered equivalent ?''. Attempts to answer this question have led to the concepts of observation equivalence, bisimulations, testing equivalence, failure equivalence, etc. The main point of this paper is to increase the understanding and motivation for two of these equivalences, namely failure and testing equivalences. The approach starts with the idea that the equivalence of processes should be reducible to the visible sequences of actions which a process performs in various contexts. This idea is implemented by a string-based semantic order for communicating processes where divergence is catastrophic. Under some assumptions about contexts, the resulting semantics is shown to be equivalent to the improved failure semantics of \textit{S. D. Brookes} and \textit{A. W. Roscoe} [Lect. Notes Comput. Sci. 197, 281-305 (1985; Zbl 0565.68023)] and also to the must testing-semantics of \textit{M. C. B. Hennessy} [Inf. Control 59, 36-83 (1983; Zbl 0544.68028)] and \textit{M. C. B. Hennessy} and \textit{R. De Nicola} [Lect. Notes Comput. Sci. 154, 548- 560 (1983; Zbl 0515.68029)]. This characterization gives independent support for the appropriateness of failures and testing.
Mathematics Subject Classification ID: 68N25
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 4055019
zbMATH Keywords: communicating processes
zbMATH Keywords: testing equivalence
zbMATH Keywords: failure equivalence
zbMATH Keywords: string-based semantic order
zbMATH Keywords: improved failure semantics
zbMATH Keywords: must testing- semantics
author: Michael Main
MaRDI profile type: Publication
cites work: Q3680258
cites work: Synchronous and asynchronous experiments on processes
cites work: Guarded commands, nondeterminacy and formal derivation of programs
cites work: Power domains
cites work: Q3666247
cites work: Q3664417
cites work: Semantics of communicating processes
cites work: A Theory of Communicating Sequential Processes
cites work: Formal verification of parallel programs
cites work: A calculus of communicating systems
cites work: Communicating sequential processes
cites work: Observation equivalence as a testing equivalence
cites work: Q3681902
full work available at URL: https://doi.org/10.1007/bf01407903
OpenAlex ID: W2058636690
description: scientific article; zbMATH DE number 4055019