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

https://hal.inria.fr/hal-01006382
Contributor : Luis Fernando Pino Duque <>
Submitted on : Saturday, December 27, 2014 - 8:10:22 PM
Last modification on : Monday, December 14, 2020 - 5:03:05 PM
Long-term archiving on: : Monday, March 30, 2015 - 4:05:58 PM

File

ictac14-final.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

796

Files downloads

597