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


	BibTex \| RIS \| RefWorks Download

, , ,

Higher-order process calculi are calculi in which processes can be communicated. We study the expressiveness of strictly higher-order process cal- culi, 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, syn- chronous 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.

Conference: International Colloquium on Automata, Languages and Programming - ICALP , pp. 442-453, 2010

DOI: 10.1007/978-3-642-14162-1_37

Cumulative Annual

View Publication