同步和异步π演算的表达能力研究  被引量:1

Study on expressive power of synchronous and asynchronous π calculus

在线阅读下载全文

作  者:韩婷婷[1] 陈韬略[1] 颜锋[1] 吕建[1] 

机构地区:[1]南京大学计算机软件新技术国家重点实验室,南京,210093

出  处:《高技术通讯》2005年第8期18-22,共5页Chinese High Technology Letters

基  金:国家重点基础研究发展计划(973计划),国家高技术研究发展计划(863计划),国家自然科学基金

摘  要:以π演算为框架,通过研究同步和异步通信机制,澄清了各个算子对语言表达能力的影响.给出了一个编码,它以同步π演算作为编码的源语言,异步π演算作为对应的目标语言,在同步π演算中保留match算子、全复制算子、并行算子和受限算子以及输入输出前缀,而异步π演算保留lazy复制算子、并行算子、受限算子、输入前缀以及没有后继的输出消息.研究结果证明了编码在接口互模拟关系下是完全抽象的,从而证明了编码的正确性.进一步说明了在不考虑不确定选择算子的情况下同步通信机制和异步通信机制的等价性,并为π演算的实现提供了理论依据.How communication mechanisms affect expressive power is studied in the setting of pi-calculus. A coding is provided, whose source language is synchronous pi-calculus including match operator, fully replicated operator, input and output prefixes while the asynchronous pi-calculus as the target language contains lazy replicated operator, input prefix and output message. The property of fully abstraction with respect to barbed bisimulation was shown, thus demonstrated the soundness of the coding. The results show the equivalence of two communication mechanisms when lack of nondetenninistic choice operator and lay a solid theoretical basis for the implementation of pi-ealeulus.

关 键 词:同步π演算 异步π演算 编码 表达能力 语言表达能力 Π演算 异步 同步 通信机制 复制算子 

分 类 号:TP18[自动化与计算机技术—控制理论与控制工程] G633.3[自动化与计算机技术—控制科学与工程]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象