Skip to Main content Skip to Navigation
Conference papers

On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi

Ivan Lanese 1, 2 Jorge Peréz 1 Davide Sangiorgi 2, 1 Alan Schmitt 3
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
3 SARDES - System architecture for reflective distributed computing environments
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Higher-order process calculi are calculi in which processes can be communicated. We study the expressiveness of strictly higher-order process calculi, and focus on two issues well-understood for first-order calculi but not in the higher-order setting: synchronous vs. asynchronous communication and polyadic vs. monadic communication. First, and similarly to the first-order setting, synchronous process-passing is shown to be encodable into asynchronous process- passing. Then, the absence of name-passing is shown to induce a hierarchy of higher-order process calculi based on the arity of polyadic communication, thus revealing a striking point of contrast with respect to first-order calculi. Finally, the passing of abstractions (i.e., functions from processes to processes) is shown to be more expressive than process-passing alone.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download
Contributor : Alan Schmitt <>
Submitted on : Friday, September 3, 2010 - 4:41:27 PM
Last modification on : Thursday, November 19, 2020 - 1:00:23 PM
Long-term archiving on: : Tuesday, October 23, 2012 - 3:31:22 PM


Files produced by the author(s)


  • HAL Id : inria-00514912, version 1




Ivan Lanese, Jorge Peréz, Davide Sangiorgi, Alan Schmitt. On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi. 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), Jul 2010, Bordeaux, France. pp.442--453. ⟨inria-00514912⟩



Record views


Files downloads