Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Luis Fernando Pino Duque Connect in order to contact the contributor
Submitted on : Saturday, December 27, 2014 - 8:10:22 PM
Last modification on : Thursday, January 20, 2022 - 5:31:49 PM
Long-term archiving on: : Monday, March 30, 2015 - 4:05:58 PM


Files produced by the author(s)




Luis Fernando Pino Duque, Filippo Bonchi, Frank D. Valencia. A Behavioral Congruence for Concurrent Constraint Programming with Non-deterministic Choice. ICTAC 2014 - 11th International Colloquium on Theoretical Aspects of Computing, Sep 2014, Bucarest, Romania. pp.351-368, ⟨10.1007/978-3-319-10882-7_21⟩. ⟨hal-01006382v2⟩



Record views


Files downloads