On the Expressiveness of Intensional Communication
arXiv:1408.1455 · doi:10.4204/EPTCS.160.4
Abstract
The expressiveness of communication primitives has been explored in a common framework based on the pi-calculus by considering four features: synchronism (asynchronous vs synchronous), arity (monadic vs polyadic data), communication medium (shared dataspaces vs channel-based), and pattern-matching (binding to a name vs testing name equality). Here pattern-matching is generalised to account for terms with internal structure such as in recent calculi like Spi calculi, Concurrent Pattern Calculus and Psi calculi. This paper explores intensionality upon terms, in particular communication primitives that can match upon both names and structures. By means of possibility/impossibility of encodings, this paper shows that intensionality alone can encode synchronism, arity, communication-medium, and pattern-matching, yet no combination of these without intensionality can encode any intensional language.
arXiv commentIn Proceedings EXPRESS/SOS 2014, arXiv:1408.1271
References in corpus (8)
- Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculi
- Psi-calculi: a framework for mobile processes with nominal data and logic
- Formalising the pi-calculus using nominal logic
- Musings on Encodings and Expressiveness
- Multiparty Symmetric Sum Types
- A Concurrent Pattern Calculus
- An Intensional Concurrent Faithful Encoding of Turing Machines
- Expressiveness via Intensionality and Concurrency