PARAMETERIZING HIGHER-ORDER PROCESSES ON NAMES AND PROCESSES

摘要

Parameterization extends higher-order processes with the capability of abstraction and application (like those in lambda-calculus). As is well-known, this extension is strict, meaning that higher-order processes equipped with parameterization are strictly more expressive than those without parameterization. This paper studies strictly higher-order processes (i.e., no name-passing) with two kinds of parameterization: one on names and the other on processes themselves. We present two main results. One is that in presence of parameterization, higher-order processes can interpret first-order (name-passing) processes in a quite elegant fashion, in contrast to the fact that higher-order processes without parameterization cannot encode first-order processes at all. We present two such encodings and analyze their properties in depth, particularly full abstraction. In the other result, we provide a simpler characterization of the standard context bisimilarity for higher-order processes with parameterization, in terms of the normal bisimilarity that stems from the well-known normal characterization for higher-order calculus. As a spinoff, we show that the bisimulation up-to context technique is sound in the higher-order setting with parameterization.