Readies and Failures in the Algebra of Communicating Processes
Authors:
- J. A. BergstraJBJ. A. Bergstra
- J. W. KlopJKJ. W. Klop
- E.-R. OlderogEOE.-R. Olderog
- 1 December 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 17 (6) , 1134-1177
Abstract
Readiness and failure semantics are studied in the setting of Algebra of Communicating Processes (ACP). A model of process graphs modulo readiness equivalence, respectively, failure equivalence, is constructed, and an equational axiom system is presented which is complete for this graph model. An explicit representation of the graph model is given, the failure model, whose elements are failure sets. Furthermore, a characterisation of failure equivalence is obtained as the maximal congruence which is consistent with trace semantics. By suitably restricting the communication format in ACP, this result is shown to carry over to subsets of Hoare’s Communicating Sequential Processes (CSP) and Milner’s Calculus of Communicating Systems (CCS). Also, the characterisation implies a full abstraction result for the failure model. In the above we restrict ourselves to finite processes without $\tau $-steps. At the end of the paper a comment is made on the situation for infinite processes with $\tau $-steps: notably we obtain that failure semantics is incompatible with Koomen’s fair abstraction rule, a proof principle based on the notion of bisimulation. This is remarkable because a weaker version of Koomen’s fair abstraction rule is consistent with (finite) failure semantics.Keywords
This publication has 15 references indexed in Scilit:
- A Complete Inference System for Regular Processes with Silent Moves1987
- On the consistency of Koomen's Fair Abstraction RuleTheoretical Computer Science, 1987
- Algebra of communicating processes with abstractionTheoretical Computer Science, 1985
- A Theory of Communicating Sequential ProcessesJournal of the ACM, 1984
- Testing equivalences for processesTheoretical Computer Science, 1984
- Process algebra for synchronous communicationInformation and Control, 1984
- Synchronous and asynchronous experiments on processesInformation and Control, 1983
- Full abstraction for a simple parallel programming language1979
- Communicating sequential processesCommunications of the ACM, 1978
- Fully abstract models of typed λ-calculiTheoretical Computer Science, 1977