On the Expressiveness of Linda-like Concurrent Languages
Antonio Brogi, Jean-Marie Jacquet · Electronic Notes in Theoretical Computer Science · 1998
We compare the expressiveness of a class of concurrent languages that employ asynchronous communication primitives à la Linda. All the languages considered contain sequential, parallel and choice operators, and they differ from one another in the set of communication primitives used. These primitives include tell, get and ask operations for adding, deleting, and checking for the presence of data in a dataspace shared by a number of concurrent processes, as well as a nask (negative ask) operation for checking for the absence of data in the shared dataspace. We use the notion of modular embedding introduced by De Boer and Palamidessi in [3] to compare the relative expressive power of the languages. A first result is the formalisation of the intuitive separation result stating that the language with get and tell is strictly more expressive than the language with ask and tell operations. An interesting result is that the ability to check for the presence of information (ask) does not increase the power of a language containing get and tell operations, whereas the ability to check for the absence of information (nask) does increase the power of such a language. Another interesting result shown is that the language containing all the communication primitives considered is strictly more expressive than each of its sub-languages, except for the redundancy of ask.