Paper: On the Expressiveness of Linearity vs Persistence in the Asynchronous Pi-Calculus (at LICS 2006)

Authors: Catuscia Palamidessi Vijay A. Saraswat Frank D. Valencia Björn Victor

Abstract

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.

BibTeX

  @InProceedings{PalamidessiSaraswat-OntheExpressiveness,
    author = 	 {Catuscia Palamidessi and Vijay A. Saraswat and Frank D. Valencia and Björn Victor},
    title = 	 {On the Expressiveness of Linearity vs Persistence in the Asynchronous Pi-Calculus},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {59--68},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }