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

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