首页> 外文期刊>Mathematical structures in computer science >On the expressive power of recursion, replication and iteration in process calculi
【24h】

On the expressive power of recursion, replication and iteration in process calculi

机译:论过程计算中递归,复制和迭代的表达能力

获取原文
获取原文并翻译 | 示例

摘要

In this paper we investigate the expressive power of three alternative approaches to the definition of infinite behaviours in process calculi, namely, recursive definitions, replication and iteration. We prove several results discriminating between the calculi obtained from a core CCS by adding the three mechanisms mentioned above. These results are derived by considering the decidability of four basic properties: termination (that is, all computations are finite); convergence (that is, the existence of a finite computation); barb (that is, the ability to perform an action on a given channel) and weak bisimulation. Our results, which are summarised in Table 1, show that the three calculi form a strict expressiveness hierarchy in that: all the properties mentioned are undecidable in CCS with recursion; only termination and barb are decidable in CCS with replication; all the properties are decidable in CCS with iteration.rnAs a corollary, we also obtain a strict expressiveness hierarchy with respect to weak bisimulation, since there exist weak bisimulation preserving encodings of iteration in replication and of replication in recursion, whereas there are no weak bisimulation preserving encodings in the other directions.
机译:在本文中,我们研究了三种可选方法在过程计算中定义无限行为的表示能力,即递归定义,复制和迭代。通过添加上述三种机制,我们证明了区分核心CCS的结石的几种结果。这些结果是通过考虑四个基本属性的可判定性得出的:终止(即所有计算都是有限的);以及收敛(即有限计算的存在);倒刺(即在给定通道上执行操作的能力)和弱双仿真。我们的结果总结在表1中,表明这三个演算形成了严格的表达层次,因为:提到的所有属性在CCS中都是不可确定的,具有递归性;具有复制功能的CCS中只能确定终止和倒钩;作为推论,我们还针对弱双仿真获得了严格的表达层次,因为存在弱双仿真,在复制中保留迭代的编码,在递归中保留迭代的编码,而没有弱双仿真保留其他方向的编码。

著录项

  • 来源
    《Mathematical structures in computer science》 |2009年第6期|1191-1222|共32页
  • 作者单位

    Dip. di Scienze dell'Informazione, Univ. di Bologna, Mura A.Zamboni 7, 40127 Bologna, Italy;

    Dip. di Scienze dell'Informazione, Univ. di Bologna, Mura A.Zamboni 7, 40127 Bologna, Italy;

    Dip. di Scienze dell'Informazione, Univ. di Bologna, Mura A.Zamboni 7, 40127 Bologna, Italy;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号