# Truly Concurrent Constraint Programming

### Abstract

We study "causality" relationships in Concurrent Constraint Programming: what is observed is not just the conjunction of constraints deposited in the store, but also the causal dependencies between these constraints. We describe a denotational semantics for cc that is fully-abstract with respect to observing this causality'' relation on constraints. This semantics preserves more fine-grained structure of computation; in particular the Interleaving Law

(c -> A) /\ (d -> B) = (c -> (A /\ (d -> B))) [] (d -> (B /\ (c -> A)))

is not verified ([] is indeterminate choice).

Relationships between such a denotational approach to true concurrency and different powerdomain constructions are explored.

@Article{truecc-tcs,
author =       "V.Gupta and R.Jagadeesan and V.A.Saraswat"
title =        "Truly Concurrent Constraint Programming",
journal =      "Theoretical Computer Science",
volume =       "278",
number =       "1--2",
pages =        "223--255",
month =        may,
year =         "2002",
note="Extended abstract appeared in the {\em Proceedings of
CONCUR 96: The 7th International Conference on Concurrency Theory},
Pisa, August 1996"
}

Postscript File (413K)
Pdf File (315K)