文献类型：期刊文献

英文题名：Distinguishing and relating higher-order and first-order processes by expressiveness

作者：Xu, Xian[1]

机构：[1]E China Univ Sci & Technol, Dept Comp Sci & Technol, Shanghai 200237, Peoples R China

年份：2012

卷号：49

期号：7-8

起止页码：445

外文期刊名：ACTA INFORMATICA

收录：;EI(收录号：20131816264201);WOS:【SCI-EXPANDED(收录号:WOS:000310950300002)】；

基金：The work is supported by the National Natural Science Foundation of China (60903020, 60903189, 61173048) and the Doctoral Fund of Ministry of Education of China (20090073120024).

语种：英文

外文关键词：Biomineralization - Calculations - Genes - Computation theory - Pathology

摘要：This is a paper on distinguishing and relating two important kinds of calculi through expressiveness, settling some critical but long unanswered questions. The delimitation of higher-order and first-order process calculi is a basic and pivotal topic in the study of process theory. Particularly, expressiveness studies mutual encodability, which helps decide whether process-passing or name-passing is more fundamental, and the way they ought to be used in both theory and practice. In this paper, we contribute to such demarcation with three major results. Firstly (first-order pi-calculus) can faithfully express (basic higher-order pi-calculus). The calculus has the elementary operators (input, output, composition and restriction). This actually is a corollary of a more general result, that can encode ( enriched with the relabelling operator). Secondly cannot interpret reasonably. This is of more significance since it separates and by drawing a well-defined boundary. Thirdly an encoding from to is revisited and discussed, which not only implies how to make more useful but also stresses the importance of name-passing in .