Expressiveness and Complexity of Concurrent Constraint Programming: a Finite Model Theoretic Approach

We study the expressiveness and complexity of concurrent constraint programming languages over finite domains. We establish strong connections between these languages and query languages in finite model theory. The bridge to finite model theory yields new (and sometimes quite surprising) results on the expressiveness and complexity of concurrent constraint languages, including several powerful normal forms. These results provide new insight into the impact of various semantics and features of concurrent constraint programming languages on their expressiveness and complexity. 1 Introduction Concurrent constraint programming (CC) [Sar87] emerged as a combination of concurrent logic programming and constraint logic programming (CLP) [JL87]. The basic idea is the one of a set of agents communicating through a shared store of constraints, that are logical formulas on the unknowns of the problem. Each agent can either write a constraint to the store (tell operation), or synchronize with oth..