Probabilistic Concurrent Constraint Programming

Vineet Gupta, Radha Jagadeesan, Vijay A. Saraswat

Abstract

We extend cc to allow the specification of a discrete probability distribution for random variables. We demonstrate the expressiveness of Probabilistic cc by synthesizing combinators for default reasoning. We extend Probabilistic cc uniformly over time, to get a synchronous reactive probabilistic programming language, Timed Probabilistic cc .

We describe operational and denotational models for Probabilistic cc (and Timed Probabilistic cc ). The key feature of the denotational model(s) is that parallel composition is essentially set intersection. We show that the denotational model of Probabilistic cc (resp. Timed Probabilistic cc ) is conservative over cc (resp. Timed cc ). We also show that the denotational models are fully abstract for an operational semantics that records probability information.

@InProceedings{probcc-concur97,
  title =        "Probabilistic Concurrent Constraint Programming",
  author =       "Vineet Gupta and Radha Jagadeesan and Vijay Saraswat",
  pages =        "243--257",
  booktitle =    "CONCUR~'97: Concurrency Theory, 8th International
                 Conference",
  editor =       "Antoni Mazurkiewicz and J{\'o}zef Winkowski",
  address =      "Warsaw, Poland",
  month =        "1--4~" # jul,
  year =         "1997",
  series =       "Lecture Notes in Computer Science",
  volume =       "1243",
  publisher =    "Springer-Verlag"
}

Postscript file (121K)
Pdf file (173K)