模型独立框架下高阶π演算及表达能力研究

发布时间：2018-01-19 22:02

本文关键词： 高阶进程演算编码表达能力互模拟　出处：《上海交通大学》2012年硕士论文　论文类型：学位论文

【摘要】：进程演算研究领域近年的热点方向之一是演算模型表达能力的研究,其目的是为了回答一个模型的必要性、及与其它模型的相对关系这样的本质问题。历史上表达能力研究往往没有从进程演算的共性出发,缺少一套合理的和独立的标准,其结论往往不具有可比较性并且可借鉴性差。为了解决上述问题,Fu根据交互理论的共性提出了一套模型独立的比较两个模型表达能力的框架,它的核心概念是:模型内部的绝对等价关系,以及模型之间具有一般性的子互模拟关系。本文基于Fu提出的模型独立框架,对高阶π演算的表达能力进行研究,具体包括以下三方面: 我们证明了在高阶π演算中,绝对等价关系与经典的环境互模拟关系是一致的。这样的一致性结论保证了环境互模拟在模型独立框架中的正确性。我们通过建立从高阶π演算到一阶π演算之间的子互模拟关系,重新证明了这两者之间的相对表达能力:前者能够在一种很强的意义下被编码到后者。为了证明上述的子互模拟关系,我们使用了一种基于扩张的桥接(up to)技术,这是这类技术首次应用在模型独立的框架的研究中。
[Abstract]:One of the hot topics in the field of process calculus research in recent years is the study of computational model expression ability, which aims to answer the necessity of a model. In history, the study of expression ability often does not start from the generality of process calculus, and lacks a set of reasonable and independent standards. In order to solve the above problem, we put forward a set of independent framework to compare the expression ability of two models according to the commonness of interaction theory. Its core concept is the absolute equivalence relation within the model and the general sub-simulation relationship between the models. Based on the model independent framework proposed by Fu, this paper studies the expression ability of higher order 蟺 calculus, including the following three aspects: We prove that the absolute equivalence relation is consistent with the classical environmental mutual simulation relation in higher order 蟺 calculus, and this consistent conclusion ensures the correctness of environmental mutual simulation in the framework of model independence. By establishing the sub-mutual simulation relationship between high-order 蟺 calculus and first-order 蟺 calculus, we reprove the relative expression ability between the two. The former can be encoded to the latter in a very strong sense. In order to prove the above sub-mutual simulation relationship, we use an extended bridging up to technique, which is the first time that this technique has been applied in the study of model-independent frameworks.
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP338.6

【参考文献】