Combinator演算族的π演算语义

Combinator演算族的π演算语义

张红, 刘磊

吉林大学计算机科学与技术学院，长春 130012

收稿日期:2005-05-11 修回日期:1900-01-01 出版日期:2006-05-26 发布日期:2006-05-26
通讯作者: 刘磊

πCalculus Semantics for Combinator Calculi

ZHANG Hong, LIU Lei

College of Computer Science and Technology, Jilin University, Changchun 130012, China

Received:2005-05-11 Revised:1900-01-01 Online:2006-05-26 Published:2006-05-26
Contact: LIU Lei

摘要/Abstract

摘要： 以SKI演算作为Combinator演算族的代表，通过形式化的手段给出了SKI演算的π演算语义；通过一个实例验证了所论方法的正确性. 所给出的转换方法证明了π演算的表达能力： π演算为图灵完备的. 由于高阶函数式语言与Combinator演算族之间存在着自然的转换, 所给的转换思想不仅为在π演算的理论框架下研究Combinator演算族提供了基础, 也为探讨高阶函数式语言的表示和实现问题提供了新途径.

关键词: π演算, Combinator演算族, SKI演算, 语义

Abstract: πCalculus is used to encode the semantics for the SKIcalculus which is a representative of combinator calculi. SKI calculus is Turing complete, and this work shows the expressiveness of πcalculus. Furthermore, this work provides a precondition for uniting and comparing combinator calculi, lambdacalculus as well as higherorder functions with other concurrent models under the theory of πcalculus.

Key words: πcalculus, Combinator calculi, SKIcalculus, semantics

中图分类号:

TP311

张红, 刘磊. Combinator演算族的π演算语义[J]. J4, 2006, 44(03): 391-396.

ZHANG Hong, LIU Lei. πCalculus Semantics for Combinator Calculi[J]. J4, 2006, 44(03): 391-396.

[1]	曲豫宾, 陈翔, 李龙. 可缓解类重叠问题的跨版本软件缺陷预测方法[J]. 吉林大学学报(理学版), 2021, 59(2): 372-378.
[2]	齐向明, 孙煦骄. 基于语义簇的中文文本聚类算法[J]. 吉林大学学报(理学版), 2019, 57(5): 1193-1199.
[3]	周诗源, 王英林. 基于抽取规则和本体映射的语义搜索算法[J]. 吉林大学学报(理学版), 2018, 56(2): 329-334.
[4]	王铁君, 王维兰. 唐卡领域本体研究与构建[J]. 吉林大学学报(理学版), 2017, 55(02): 363-370.
[5]	谭涛, 谭乐婷, 贺春林. 一种新的基于稀疏编码Hash的跨模多媒体数据检索算法[J]. 吉林大学学报(理学版), 2017, 55(02): 345-351.
[6]	董立岩, 张高祥, 孙博, 郎一宁. 从自然语言向SPARQL语言映射的歧义消解算法[J]. 吉林大学学报(理学版), 2016, 54(03): 535-538.
[7]	宋国平, 韩啸, 王井丰. 一种基于上下文规则的词义消歧算法[J]. 吉林大学学报(理学版), 2014, 52(02): 326-330.
[8]	李瑞霞, 苏守宝, 周先存. 一种基于语义相关度的XML关键字查询排序方法[J]. 吉林大学学报(理学版), 2013, 51(06): 1118-1122.
[9]	黄文博, 燕杨, 李博. 一种融合PLSA模型和树模型的文本病历语义分析新方法[J]. 吉林大学学报(理学版), 2013, 51(04): 666-670.
[10]	张凯勇, 周春光, 王康平, 郭东伟, 翟延冬. 基于扩展关系的信息量计算方法[J]. J4, 2011, 49(06): 1068-1072.
[11]	张东娜, 周春光, 刘彦斌, 郭东伟. 一种基于WordNet和Corpus Statistics的语义相似性计算方法[J]. J4, 2010, 48(05): 811-816.
[12]	陈巍, 欧阳丹彤, 叶育鑫. RIF2Jess: 应用Jess实现RIF规则推理[J]. J4, 2010, 48(03): 414-420.
[13]	惠玥, 徐沛娟, 付燕宁. 语义 Web 服务组合策略[J]. J4, 2009, 47(03): 558-562.
[14]	金英, 郑晓娟, 张晶, 孙旭东. 基于多语言范例的“形式语义学”教学辅助系统[J]. J4, 2009, 47(03): 530-536.
[15]	包铁, 刘淑芬, 戚志涵. 可执行元模型方法的研究与应用[J]. J4, 2009, 47(01): 69-74.