Embedding as a Tool for Language Comparison: On the CSP Hierarchy

摘要

The concept of embedding was recently introduced as a formal tool to study therelative expressive power of (concurrent) programming languages. The motion of 'modular embedding' is used to compare various dialects of Communicating Sequential Processes (CSP) and Asynchronous CSP (ACSP), which differ on the kind of communication primitives allowed in the guards: all, only input, or none. Concerning the synchronous paradigm, CSP is strictly more powerful than CSP(I) (the version of CSP with no communication primitives in the guards). The first separation result does not hold in the asynchronous variants of these languages; since asynchronous output guards cannot be influenced by the environment (they can always proceed), it is irrelevant to have or not to have them in the language. Therefore, ACSP and ACSP(I) are equivalent. Still, they are strictly more expressive than ACSP(0). The synchronous and asynchronous paradigms are compared. The asynchronous communication can be modeled synchronously by means of buffer processes. On the other hand, synchronous communication (when not fully used to control nondeterminism) can be modeled asynchronously by means of acknowlegement messages. As a consequence, CSP(I), ACSP, and ACSP(I) are equivalent. An interesting corollary of these results is that ACSP is strictly less powerful than CSP.