On the Expressive Power of Restriction and Priorities in CCS with replication

Jesus Aranda 1, 2 Frank Valencia 2 Cristian Versari 3
2 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : We study the expressive power of restriction and its interplay with replication. We do this by considering several syntactic variants of CCS! (CCS with replication instead of recursion) which differ from each other in the use of restriction with respect to replication. We consider three syntactic variations of CCS! which do not allow the use of an unbounded number of restrictions: C1 is the fragment of CCS! not allowing restrictions under the scope of a replication. C2 is the restriction-free fragment of CCS!. The third variant is C3 which extends C1 with Phillips' priority guards. We show that the use of unboundedly many restrictions in CCS! is necessary for obtaining Turing expressiveness in the sense of Busi et al [8]. We do this by showing that there is no encoding of RAMs into C2 which preserves and reflects convergence. We also prove that up to failures equivalence, there is no encoding from CCS! into C1 nor from C1 into C2. As lemmata for the above results we prove that convergence is decidable for C1 and that language equivalence is decidable for CCS2. As corollary it follows that convergence is decidable for restriction-free CCS. Finally, we show the expressive power of priorities by providing an encoding of RAMs in C3.
Type de document :
Communication dans un congrès
Proceedings of the 12th International Conference on Foundations of Software Science and Computational Structures: Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, Mar 2009, York, UK, United Kingdom. Volume 5504/2009, 2009, LNCS. 〈10.1007/978-3-642-00596-1_18〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00430531
Contributeur : Jesus Aranda <>
Soumis le : dimanche 8 novembre 2009 - 16:40:40
Dernière modification le : jeudi 10 mai 2018 - 02:06:44
Document(s) archivé(s) le : jeudi 17 juin 2010 - 19:45:23

Fichier

fossacs09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jesus Aranda, Frank Valencia, Cristian Versari. On the Expressive Power of Restriction and Priorities in CCS with replication. Proceedings of the 12th International Conference on Foundations of Software Science and Computational Structures: Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, Mar 2009, York, UK, United Kingdom. Volume 5504/2009, 2009, LNCS. 〈10.1007/978-3-642-00596-1_18〉. 〈inria-00430531〉

Partager

Métriques

Consultations de la notice

424

Téléchargements de fichiers

99