Fully Abstract Model for Concurrent Constraint Programming

摘要

Recent results have shown that concurrent logic programming has a very simplemodel, based on linear sequences, which is fully abstract with respect to the parallel operator and finite observables. This is intrinsically related to the asynchronous and monotonic nature of the communication mechanism, which consists of asking and telling constraints on a common store. A paradigm for (asynchronous) concurrent programming, based on the above mechanism and provided with the standard operators of choice, parallelism, prefixing, and hiding of local variables, is considered. It comes out that linear sequences still suffice for a compositional description of all the operators. The problem of full abstraction is considered. Since the notion of observables implies the removal of silent steps, the presence of the choice operator induces the same problems (for compositionality) as bisimulation in CCS. It is shown that in the present framework this problem has a simple solution which consists of introducing a semantical distinction between the various ways in which deadlock and failure might occur. The resulting semantics are fully abstract and are still based on linear sequences.