A Behavioral Congruence for Concurrent Constraint Programming with Non-deterministic Choice

Luis Fernando Pino Duque 1, 2 Filippo Bonchi 3 Frank D. 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 of concurrency for reasoning about systems of multiple agents that interact with each other by posting and querying partial information on a shared space. (Weak) bisimilarity is one of the most representative notions of behavioral equivalence for models of concurrency. A notion of weak bisimilarity, called weak saturated bisimilarity (WSB), was recently proposed for CCP. This equivalence improves on previous bisimilarity notions for CCP that were too discriminating and it is a congruence for the choice-free fragment of CCP. In this paper, however, we show that WSB is not a congruence for CCP with nondeterministic choice. We then introduce a new notion of bisimilarity, called weak full bisimilarity (FB), and show that it is a congruence for the full language of ccp. We also show the adequacy of FB by establishing that it coincides with the congruence induced by closing WSB under all contexts. The advantage of the new definition is that, unlike the congruence induced by WSB, it does not require quantifying over infinitely many contexts.
Type de document :
Communication dans un congrès
Gabriel Ciobanu and Dominique Méry. ICTAC 2014 - 11th International Colloquium on Theoretical Aspects of Computing, Sep 2014, Bucarest, Romania. Springer, 8687, pp.351-368, Lecture Notes in Computer Science. 〈10.1007/978-3-319-10882-7_21〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01006382
Contributeur : Luis Fernando Pino Duque <>
Soumis le : samedi 27 décembre 2014 - 20:10:22
Dernière modification le : jeudi 9 février 2017 - 15:11:19
Document(s) archivé(s) le : lundi 30 mars 2015 - 16:05:58

Fichier

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

Identifiants

Collections

Citation

Luis Fernando Pino Duque, Filippo Bonchi, Frank D. Valencia. A Behavioral Congruence for Concurrent Constraint Programming with Non-deterministic Choice. Gabriel Ciobanu and Dominique Méry. ICTAC 2014 - 11th International Colloquium on Theoretical Aspects of Computing, Sep 2014, Bucarest, Romania. Springer, 8687, pp.351-368, Lecture Notes in Computer Science. 〈10.1007/978-3-319-10882-7_21〉. 〈hal-01006382v2〉

Partager

Métriques

Consultations de
la notice

361

Téléchargements du document

97