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

https://hal.inria.fr/inria-00514912
Contributor : Alan Schmitt <>
Submitted on : Friday, September 3, 2010 - 4:41:27 PM
Last modification on : Thursday, February 21, 2019 - 1:31:23 AM
Long-term archiving on : Tuesday, October 23, 2012 - 3:31:22 PM

File

Lanese2010On-the-Expressivenes...
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00514912, version 1

Collections

INRIA | UGA | LIG

Citation

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⟩

Share

Metrics

Record views

917

Files downloads

187