Weak CCP bisimilarity with strong procedures

Luis Pino 1, 2 Andres Aristizabal 3 Filippo Bonchi 4 Frank Valencia 1, 2
1 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : Concurrent constraint programming (CCP) is a well-established model for concurrency that singles out the fundamental aspects of asynchronous systems whose agents (or processes) evolve by posting and querying (partial) information in a global medium. Bisimilarity is a standard behavioral equivalence in concurrency theory. However, only recently a well-behaved notion of bisimilarity for CCP, and a CCP partition refinement algorithm for deciding the strong version of this equivalence have been proposed. Weak bisimilarity is a central behavioral equivalence in process calculi and it is obtained from the strong case by taking into account only the actions that are observable in the system. Typically, the standard partition refinement can also be used for deciding weak bisimilarity simply by using Milner's reduction from weak to strong bisimilarity; a technique referred to as saturation. In this paper we demonstrate that, because of its involved labeled transitions, the above-mentioned saturation technique does not work for CCP. We give an alternative reduction from weak CCP bisimilarity to the strong one that allows us to use the CCP partition refinement algorithm for deciding this equivalence.
Type de document :
Article dans une revue
Science of Computer Programming, Elsevier, 2015, 100, pp.84-104. 〈10.1016/j.scico.2014.09.007〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00976768
Contributeur : Luis Fernando Pino Duque <>
Soumis le : samedi 27 décembre 2014 - 20:20:49
Dernière modification le : samedi 18 février 2017 - 01:13:54
Document(s) archivé(s) le : lundi 30 mars 2015 - 16:06:10

Fichier

scp13-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Luis Pino, Andres Aristizabal, Filippo Bonchi, Frank Valencia. Weak CCP bisimilarity with strong procedures. Science of Computer Programming, Elsevier, 2015, 100, pp.84-104. 〈10.1016/j.scico.2014.09.007〉. 〈hal-00976768v2〉

Partager

Métriques

Consultations de
la notice

273

Téléchargements du document

113