Towards a unified approach to encodability and separation results for process calculi
Towards a unified approach to encodability and separation results for process calculi
复制标题
DOI：
10.1016/j.ic.2010.05.002
复制
发表时间：
2010-09-01
影响因子：
1
通讯作者：
Gorla, Daniele
中科院分区：
文献类型：
--
作者：
Gorla, Daniele
我们提出了一种统一的方法来评估过程演算的相对表达能力。特别是，我们确定了一小部分标准（已经在文献中以某种方式提出），编码应满足这些标准才能被视为语言比较的有效手段。我们认为，这些标准的组合是一个有效的建议，因为：（i）文献中出现的几种众所周知的编码满足这些标准； （ii）这个概念并非微不足道，因为一些已知的编码不满足我们提出的所有标准：（iii）可以根据我们的标准制定一些众所周知的分离结果：以及（iv）一些广泛相信（但从未正式证明）的分离结果可以通过使用我们提出的标准来证明。此外，定义的标准引入了分离结果的通用证明技术，可以轻松实例化以覆盖已知的案例研究。 (C) 2010 Elsevier Inc. 保留所有权利。
We present a unified approach to evaluate the relative expressive power of process calculi. In particular, we identify a small set of criteria (that have already been somehow presented in the literature) that an encoding should satisfy to be considered a valid means for language comparison. We argue that the combination of such criteria is a valid proposal by noting that: (i) several well-known encodings appeared in the literature satisfy them; (ii) this notion is not trivial, because some known encodings do not satisfy all the criteria we have proposed: (iii) several well-known separation results can be formulated in terms of our criteria: and (iv) some widely believed (but never formally proved) separation results can be proved by using the criteria we propose. Moreover, the criteria defined induce general proof-techniques for separation results that can be easily instantiated to cover known case-studies. (C) 2010 Elsevier Inc. All rights reserved.