λ-演算到π-演算的一种编码

来源 :上海交通大学 | 被引量 : 0次 | 上传用户:Nick0409
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
人类发展的历史,就是解决问题的历史。计算机的出现,加快了人类解决问题的速度,也带来了与之相对应的问题。在一些反复出现的问题上,人们试图找出最优的解决方案,以期可以达到最快解决问题的目的。在寻找解决方案的过程中,数学模型成为了其中的关键。人们把问题的求解分为两个阶段:先将问题建模成数学模型,再对数学模型进行求解。在这种情况下,许许多多优秀的数学模型被提了出来,其中包括图灵机和λ-演算。事实上,两者的表达能力是等价的。随着计算机科学的发展,并行逐渐代替串行成为了主流的研究对象。串行计算有图灵机和λ-演算作为完备的模型可以进行科学研究,而并行计算却没有与之相对应的计算模型。为了解决这一问题,Milner提出了CCS,同时Hoare提出了CSP,两者都是优秀的并行计算模型。然而,这两个模型都不能完美的刻画并行计算的性质,原因在于静态的结构和不支持通信。在十九世纪八十年代末,Milner在CCS的基础上提出了一个表达能力更强的完备的并行计算模型—π-演算。但随之而来的问题是串行计算的模型和并行计算的模型之间的表达能力的关系。很容易知道,并行计算的模型可以对串行计算的模型进行编码,从而找出表达能力之间的关系。Milner在提出π-演算的同时,就给出了一种可以刻画简单的λ-演算的解决方案。但是这一方案存在着非常大的局限性,体现在不能刻画所有的四种归约策略。蔡小娟和傅育熙则另辟蹊径,利用更为强大的带匹配和失配算符的π-演算变种,以编程的方式实现了从λ-演算到π-演算的编码。这一方案虽然给出了一个完全抽象,但是由于目标语言太强,因此表达能力的问题还没有被完全解决。本文提出了一种在π-演算中消去匹配和失配算符的技术,结合蔡小娟和傅育熙的编码体系,证明了不包含匹配和失配算符的π-演算存在保持弱互模拟等价关系的编码。
其他文献
步态是指人走路的样子,心理学实验以及解剖学理论表明其具有一定的人人相异性,可以用来进行身份识别。同时,步态具有可远距离获取、易于采集,非接触性、难于隐藏或伪装等特点
随着网络融合的推进,用户需要一个智能的服务环境来动态聚合不同网络的能力。语义Web服务是基于本体的新一代Web服务技术,其开放和标准的服务接口是提供异构网络能力的一种新
近些年来,新兴的分形几何学在不断地发展,并且在一些研究领域中得到了广泛的应用,如计算机、地理、交通等等。分形几何的最基本特征是自相似性,即每个局部按照一定的比例放大
空间数据库的研究始于20世纪70年代的地图制图与遥感图像处理领域,其目的是为了有效地利用卫星遥感资源迅速绘制出各种专题地图。随着地理信息系统、计算机辅助设计与制造、机
森林火灾是林业灾害中对社会、经济及环境发展影响范围最广和破坏性最大的一种自然灾害。森林火灾是一个极其复杂的自然现象,受众多自然因素和社会因素的影响,包括可燃物类型