Truly Concurrent Constraint Programming

Vineet Gupta, Radha Jagadeesan, Vijay A. Saraswat

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)