On the Computation Power of Name Parameterization in Higher-order Processes

Xian Xu
(East China University of Science and Technology)
Qiang Yin
(Shanghai Jiao Tong University)
Huan Long
(Shanghai Jiao Tong University)

Parameterization extends higher-order processes with the capability of abstraction (akin to that in lambda-calculus), and is known to be able to enhance the expressiveness. This paper focuses on the parameterization of names, i.e. a construct that maps a name to a process, in the higher-order setting. We provide two results concerning its computation capacity. First, name parameterization brings up a complete model, in the sense that it can express an elementary interactive model with built-in recursive functions. Second, we compare name parameterization with the well-known pi-calculus, and provide two encodings between them.

In Sophia Knight, Ivan Lanese, Alberto Lluch Lafuente and Hugo Torres Vieira: Proceedings 8th Interaction and Concurrency Experience (ICE 2015), Grenoble, France, 4-5th June 2015, Electronic Proceedings in Theoretical Computer Science 189, pp. 114–127.
Published: 19th August 2015.

ArXived at: http://dx.doi.org/10.4204/EPTCS.189.10 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org