Technical Reports

A List by Author: David Gilbert


A Fully Abstract Semantics for a Version of Synchronous Concurrent Constraint Programming

by Jean-Marie Jacquet, Lubo¹ Brim, David Gilbert, Mojmír Køetínský, December 1999, 62 pages.

FIMU-RS-99-08. Available as Postscript, PDF.


Concurrent constraint programming is classically based on asynchronous communication via a shared store. In previous work, we presented a new version of the ask and tell primitives which features synchronicity, our approach being based on the idea of telling new information just in the case that a concurrently running process is asking for it. We turn in this paper to a semantic study of this new framework, called Scc.

It is first shown to be different in nature from classical concurrent constraint programming and from CCS, a classical reference in traditional concurrency theory. This suggests the interest of new semantics for Scc. To that end, an operational semantics reporting the steps of the computations is presented. A denotational semantics is then proposed. It uses monotonic sequences of labelled pairs of input-output states, possibly containing gaps, and ending - according to the logic programming tradition - with marks reporting success or failure. This denotational semantics is proved to be correct with respect to the operational semantics as well as fully abstract.

Responsible contact: unix(atsign)fi(dot)muni(dot)cz