Embedding as a Tool for Language Comparison: On the CSP Hierarchy
Embedding as a Tool for Language Comparison: On the CSP Hierarchy
复制标题
嵌入作为语言比较工具：在 CSP 层次结构上
DOI：
10.1007/3-540-54430-5_85
复制
发表时间：
1991
期刊：
影响因子：
0.6
通讯作者：
C. Palamidessi
中科院分区：
文献类型：
--
作者：
F. S. Boer;C. Palamidessi
嵌入的概念最近被引入作为一种正式的工具来研究（并发）编程语言的相对表达能力。我们使用“模块化嵌入”的概念来比较CSP和ACSP（异步CSP）的各种方言，它们在警卫中允许的通信原语类型上有所不同：全部、仅输入或没有。关于同步范式，我们表明CSP严格地比\(CSP_\mathcal{I}\)（没有输出保护的CSP版本）更强大，并且\(CSP_\mathcal{I}\)严格地比\(CSP_{\not 0}\)（在保护中没有通信原语的CSP版本）更强大。第一个分离结果在这些语言的异步变体中不成立：因为异步输出保护不会受到环境的影响（它们总是可以继续），所以在语言中是否有它们是无关紧要的。因此，ACSP和\(ACSP_\mathcal{I}\)是等价的。不过，严格来说，它们比\(ACSP_{\not 0}\)更具表现力。最后，我们将比较同步和异步范式。异步通信可以通过“缓冲”进程同步建模。另一方面，同步通信（在不完全用于控制不确定性的情况下）可以通过确认消息异步建模。因此，\(CSP_\mathcal{I}\)、ACSP和\(ACSP_\mathcal{I}\)是等价的。这些结果的一个有趣的推论是，ACSP的功率严格低于CSP。
The concept of embedding has recently been introduced as a formal tool to study the relative expressive power of (concurrent) programming languages. We use the notion of “modular embedding” to compare various dialects of CSP and ACSP (Asynchronous CSP), which differ on the kind of communication primitives allowed in the guards: all, only input, or none. Concerning the synchronous paradigm, we show that CSP is strictly more powerful than \(CSP_\mathcal{I}\)(the version of CSP with no output guards), and that \(CSP_\mathcal{I}\)is strictly more powerful than \(CSP_{\not 0}\)(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_\mathcal{I}\)are equivalent. Still, they are strictly more expressive than \(ACSP_{\not 0}\). Finally, we come to compare the synchronous and asynchronous paradigms. 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 acknowledgement messages. As a consequence, \(CSP_\mathcal{I}\), ACSP, and \(ACSP_\mathcal{I}\)are equivalent. An interesting corollary of these results is that ACSP is strictly less powerful than CSP.