On the Expressiveness of Linearity vs Persistence in the Asychronous Pi-Calculus
Catuscia Palamidessi, Vijay Saraswat, Frank Valencia, Björn Victor · 2006
We present an expressiveness study of linearity and persistence of processes. We choose the ð-calculus, one of the main representatives of process calculi, as a framework to conduct our study. We consider four fragments of the ð-calculus. Each one singles out a natural source of linearity/ persistence also present in other frameworks such as Concurrent Constraint Programming (CCP), Linear CCP, and several calculi for security. The study is presented by providing (or proving the non-existence of) encodings among the fragments, a processes-as-formulae interpretation and a reduction from Minsky machines.