Trace, failure and testing equivalences for communicating processes

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.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: Trace, failure and testing equivalences for communicating processes

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