arXiv:cs/0208008v1 [] 6 Aug 2002

Soft Concurrent Constraint Programming
Stefano Bistarelli
Istituto di Informatica e Telematica, C.N.R., Pisa, Italy
and
Ugo Montanari
Dipartimento di Informatica, Università di Pisa, Italy
and
Francesca Rossi
Dipartimento di Matematica Pura ed Applicata, Università di Padova, Italy.
Soft constraints extend classical constraints to represent multiple consistency levels, and thus
provide a way to express preferences, fuzziness, and uncertainty. While there are many soft
constraint solving formalisms, even distributed ones, by now there seems to be no concurrent
programming framework where soft constraints can be handled. In this paper we show how the
classical concurrent constraint (cc) programming framework can work with soft constraints, and
we also propose an extension of cc languages which can use soft constraints to prune and direct
the search for a solution. We believe that this new programming paradigm, called soft cc (scc),
can be also very useful in many web-related scenarios. In fact, the language level allows web
agents to express their interaction and negotiation protocols, and also to post their requests in
terms of preferences, and the underlying soft constraint solver can find an agreement among the
agents even if their requests are incompatible.
Categories and Subject Descriptors: D.1.3 [Programming Techniques]: Concurrent Programming—Distributed programming; D.3.1 [Programming Languages]: Formal Definitions and
Theory—Semantics; Syntax; D.3.2 [Programming Languages]: Language Classifications—
Concurrent, distributed, and parallel languages; Constraint and logic languages; D.3.3 [Programming Languages]: Language Constructs and Features—Concurrent programming structures; Constraints; F.3.2 [Logics and Meanings of Programs]: Semantics of Programming
Languages—Operational semantics
General Terms: Languages
Additional Key Words and Phrases: constraints, soft constraints, concurrent constraint programming

1. INTRODUCTION
The concurrent constraint (cc) paradigm [Saraswat 1993] is a very interesting computational framework which merges together constraint solving and concurrency.
The main idea is to choose a constraint system and use constraints to model comResearch supported in part by the the the Italian MIUR Projects cometa and napoli and by ASI
project ARISCOM.
Permission to make digital/hard copy of all or part of this material without fee for personal
or classroom use provided that the copies are not made or distributed for profit or commercial
advantage, the ACM copyright/server notice, the title of the publication, and its date appear, and
notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish,
to post on servers, or to redistribute to lists requires prior specific permission and/or a fee.
c 2018 ACM 1529-3785/2018/0700-0001 $5.00
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018, Pages 1–25.

2

·

Stefano Bistarelli et al.

munication and synchronization among concurrent agents.
Until now, constraints in cc were crisp, in the sense that they could only be satisfied or violated. Recently, the classical idea of crisp constraints has been shown
to be too weak to represent real problems and a big effort has been done toward
the use of soft constraints [Freuder and Wallace 1992; Dubois et al. 1993; Ruttkay 1994; Fargier and Lang 1993; Schiex et al. 1995; Bistarelli et al. 1997; 2001;
Bistarelli 2001], which can have more than one level of consistency. Many real-life
situations are, in fact, easily described via constraints able to state the necessary
requirements of the problems. However, usually such requirements are not hard,
and could be more faithfully represented as preferences, which should preferably be
satisfied but not necessarily. Also, in real life, we are often challenged with overconstrained problems, which do not have any solution, and this also leads to the
use of preferences or in general of soft constraints rather than classical constraints.
Generally speaking, a soft constraint is just a classical constraint plus a way to
associate, either to the entire constraint or to each assignment of its variables, a
certain element, which is usually interpreted as a level of preference or importance.
Such levels are usually ordered, and the order reflects the idea that some levels are
better than others. Moreover, one has also to say, via suitable combination operators, how to obtain the level of preference of a global solution from the preferences
in the constraints.
Many formalisms have been developed to describe one or more classes of soft
constraints. For instance consider fuzzy CSPs [Dubois et al. 1993; Ruttkay 1994],
where crisp constraints are extended with a level of preference represented by a
real number between 0 and 1, or probabilistic CSPs [Fargier and Lang 1993], where
the probability to be in the real problem is assigned to each constraint. Some
other examples are partial [Freuder and Wallace 1992] or valued CSPs [Schiex et al.
1995], where a preference is assigned to each constraint, in order to satisfy as many
constraints as possible, and thus handle also overconstrained problems.
We think that many network-related problem could be represented and solved
by using soft constraints. Moreover, the possibility to use a concurrent language
on top of a soft constraint system, could lead to the birth of new protocols with an
embedded constraint satisfaction and optimization framework.
In particular, the constraints could be related to a quantity to be minimized/maximized but they could also satisfy policy requirements given for performance or administrative reasons. This leads to change the idea of QoS in routing
and to speak of constraint-based routing [Awduche et al. 1999; Clark 1989; Jain
and Sun 2000; Calisti and Faltings 2000]. Constraints are in fact able to represent
in a declarative fashion the needs and the requirements of agents interacting over
the web.
The features of soft constraints could also be useful in representing routing problems where an imprecise state information is given [Chen and Nahrstedt 1998].
Moreover, since QoS is only a specific application of a more general notion of Service Level Agreement (SLA), many applications could be enhanced by using such
a framework. As an example consider E-commerce: here we are always looking for
establishing an agreement between a merchant, a client and possibly a bank. Also,
all auction-based transactions need an agreement protocol. Moreover, also secuACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

Soft Concurrent Constraint Programming

·

3

rity protocol analysis have shown to be enhanced by using security levels instead
of a simple notion of secure/insecure level [Bella and Bistarelli 2001]. All these
considerations advocate for the need of a soft constraint framework where optimal
answers are extracted.
In this paper, we use one of the frameworks able to deal with soft constraints
[Bistarelli et al. 1995; 1997]. The framework is based on a semiring structure that
is equipped with the operations needed to combine the constraints present in the
problem and to choose the best solutions. According to the choice of the semiring,
this framework is able to model all the specific soft constraint notions mentioned
above. We compare the semiring-based framework with constraint systems “a la
Saraswat” and then we show how use it inside the cc framework. The next step is
the extension of the syntax and operational semantics of the language to deal with
the semiring levels. Here, the main novelty with respect to cc is that tell and ask
agents are equipped with a preference (or consistency) threshold which is used to
prune the search.
After a short summary of concurrent constraint programming (§2.1) and of
semiring-based SCSPs (§2.2), we show how the concurrent constraint framework
can be used to handle also soft constraints (§3). Then we integrate semirings inside
the syntax of the language and we change its semantics to deal with soft levels (§4).
Some notions of observables able to deal with a notion of optimization and with
success (§6.1), fail (§6.2) and hang computations (§6.3) are then defined. Some
examples (§5) and an application scenario (§7) conclude our presentation showing
the expressivity of the new language. Finally, conclusions (§8) are added to point
out the main results and possible directions for future work.
2. BACKGROUND
2.1 Concurrent Constraint Programming
The concurrent constraint (cc) programming paradigm [Saraswat 1993] concerns
the behaviour of a set of concurrent agents with a shared store, which is a conjunction of constraints. Each computation step possibly adds new constraints to the
store. Thus information is monotonically added to the store until all agents have
evolved. The final store is a refinement of the initial one and it is the result of the
computation. The concurrent agents do not communicate directly with each other,
but only through the shared store, by either checking if it entails a given constraint
(ask operation) or adding a new constraint to it (tell operation).
2.1.1 Constraint Systems. A constraint is a relation among a specified set of
variables. That is, a constraint gives some information on the set of possible values
that these variables may assume. Such information is usually not complete since
a constraint may be satisfied by several assignments of values of the variables (in
contrast to the situation that we have when we consider a valuation, which tells
us the only possible assignment for a variable). Therefore it is natural to describe
constraint systems as systems of partial information [Saraswat 1993].
The basic ingredients of a constraint system (defined following the information
systems idea) are a set D of primitive constraints or tokens, each expressing some
partial information, and an entailment relation ⊢ defined on ℘(D) × D (or its
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

·

4

Stefano Bistarelli et al.

extension defined on ℘(D) × ℘(D))1 satisfying:
—u ⊢ P for all P ∈ u (reflexivity) and
—if u ⊢ v and v ⊢ z, then u ⊢ z (transitivity).
We also define u ≈ v if u ⊢ v and v ⊢ u.
As an example of entailment relation, consider D as the set of equations over
the integers; then ⊢ could include the pair h{x = 3, x = y}, y = 3i, which means
that the constraint y = 3 is entailed by the constraints x = 3 and x = y. Given
X ∈ ℘(D), let X be the set X closed under entailment. Then, a constraint in an
information system h℘(D), ⊢i is simply an element of ℘(D).
As it is well known, h℘(D), ⊆i is a complete algebraic lattice, the compactness
of ⊢ gives the algebraic structure for ℘(D), with least element true = {P | ∅ ⊢ P },
greatest element D (which we will mnemonically denote f alse), glbs (denoted by
⊓) given by the closure of the intersection and lubs (denoted by ⊔) given by the
closure of the union. The lub of chains is, however, just the union of the members
in the chain. We use a, b, c, d and e to stand for elements of ℘(D); c ⊆ d means
c ⊢ d.
2.1.2 The hiding operator: Cylindric Algebras. In order to treat the hiding operator of the language (see later), a general notion of existential quantifier for
variables in constraints is introduced, which is formalized in terms of cylindric algebras. This leads to the concept of cylindric constraint system over an infinite set
of variables V such that for each variable x ∈ V , ∃x : ℘(D) → ℘(D) is an operation
satisfying:
(1)
(2)
(3)
(4)

u ⊢ ∃x u;
u ⊢ v implies (∃x u) ⊢ (∃x v);
∃x (u ⊔ ∃x v) ≈ (∃x u) ⊔ (∃x v);
∃x ∃y u ≈ ∃y ∃x u.

2.1.3 Procedure calls. In order to model parameter passing, diagonal elements
are added to the primitive constraints. We assume that, for x, y ranging in V , ℘(D)
contains a constraint dxy which satisfies the following axioms:
(1) dxx = true,
(2) if z 6= x, y then dxy = ∃z (dxz ⊔ dzy ),
(3) if x =
6 y then dxy ⊔ ∃x (c ⊔ dxy ) ⊢ c.
Note that the in the previous definition we assume the cardinality of the domain
for x, y and z greater than 1. Note also that, if ⊢ models the equality theory, then
the elements dxy can be thought of as the formulas x = y.
2.1.4 The language. The syntax of a cc program is show in Table I: P is the
class of programs, F is the class of sequences of procedure declarations (or clauses),
A is the class of agents, c ranges over constraints, and x is a tuple of variables.
Each procedure is defined (at most) once, thus nondeterminism is expressed via the
+ combinator only. We also assume that, in p(x) :: A, we have vars(A) ⊆ x, where
1 The

extension is s.t. u ⊢ v iff u ⊢ P for every P ∈ v.

ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

Soft Concurrent Constraint Programming
Table I.

·

5

cc syntax

P ::= F.A
F ::= p(x) :: A | F.F
A ::= success | f ail | tell(c) → A | E | AkA | ∃x A | p(x)
E ::= ask(c) → A | E + E

vars(A) is the set of all variables occurring free in agent A. In a program P = F.A,
A is the initial agent, to be executed in the context of the set of declarations F .
This corresponds to the language considered in [Saraswat 1993], which allows only
guarded nondeterminism.
In order to better understand the extension of the language that we will introduce
later, let us remind here the operational semantics of the agents.
—agent “success” succeeds in one step,
—agent “f ail” fails in one step,
—agent “ask(c) → A” checks whether constraint c is entailed by the current store
and then, if so, behaves like agent A. If c is inconsistent with the current store,
it fails, and otherwise it suspends, until c is either entailed by the current store
or is inconsistent with it;
—agent “ask(c1 ) → A1 + ask(c2 ) → A2 ” may behave either like A1 or like A2 if
both c1 and c2 are entailed by the current store, it behaves like Ai if ci only is
entailed, it suspends if both c1 and c2 are consistent with but not entailed by
the current store, and it behaves like “ask(c1 ) → A1 ” whenever “ask(c2 ) → A2 ”
fails (and vice versa);
—agent “tell(c) → A” adds constraint c to the current store and then, if the
resulting store is consistent, behaves like A, otherwise it fails.
—agent A1 kA2 behaves like A1 and A2 executing in parallel;
—agent ∃x A behaves like agent A, except that the variables in x are local to A;
—p(x) is a call of procedure p.
A formal treatment of the cc semantics can be found in [Saraswat 1993; de Boer and
Palamidessi 1991]. Also, a denotational semantics of deterministic cc programs,
based on closure operators, can be found in [Saraswat 1993]. A more complete
survey on several concurrent paradigms is given also in [de Boer and Palamidessi
1994].
2.2 Soft Constraints
Several formalization of the concept of soft constraints are currently available.
In the following, we refer to the one based on c-semirings [Bistarelli et al. 1997;
Bistarelli 2001], which can be shown to generalize and express many of the others.
A soft constraint may be seen as a constraint where each instantiations of its
variables has an associated value from a partially ordered set which can be interpreted as a set of preference values. Combining constraints will then have to take
into account such additional values, and thus the formalism has also to provide
suitable operations for combination (×) and comparison (+) of tuples of values and
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

6

·

Stefano Bistarelli et al.

constraints. This is why this formalization is based on the concept of c-semiring,
which is just a set plus two operations.
2.2.1

C-semirings. A semiring is a tuple hA, +, ×, 0, 1i such that:

(1) A is a set and 0, 1 ∈ A;
(2) + is commutative, associative and 0 is its unit element;
(3) × is associative, distributes over +, 1 is its unit element and 0 is its absorbing
element.
A c-semiring is a semiring hA, +, ×, 0, 1i such that + is idempotent, 1 is its
absorbing element and × is commutative. Let us consider the relation ≤S over A
such that a ≤S b iff a + b = b. Then it is possible to prove that (see [Bistarelli et al.
1997]):
(1) ≤S is a partial order;
(2) + and × are monotone on ≤S ;
(3) 0 is its minimum and 1 its maximum;
(4) hA, ≤S i is a complete lattice and, for all a, b ∈ A, a + b = lub(a, b).
Moreover, if × is idempotent, then: + distribute over ×; hA, ≤S i is a complete
distributive lattice and × its glb. Informally, the relation ≤S gives us a way to
compare semiring values and constraints. In fact, when we have a ≤S b, we will
say that b is better than a. In the following, when the semiring will be clear from
the context, a ≤S b will be often indicated by a ≤ b.
2.2.2 Soft Constraints and Problems. Given a semiring S = hA, +, ×, 0, 1i, a
finite set D (the domain of the variables) and an ordered set of variables V , a
constraint is a pair hdef , coni where con ⊆ V and def : D|con| → A. Therefore, a
constraint specifies a set of variables (the ones in con), and assigns to each tuple
of values of these variables an element of the semiring. Consider two constraints
c1 = hdef1 , coni and c2 = hdef2 , coni, with |con| = k. Then c1 ⊑S c2 if for all
k-tuples t, def1 (t) ≤S def2 (t). The relation ⊑S is a partial order.
A soft constraint problem is a pair hC, coni where con ⊆ V and C is a set of
constraints: con is the set of variables of interest for the constraint set C, which
however may concern also variables not in con. Note that a classical CSP is a SCSP
where the chosen c-semiring is: SCSP = h{f alse, true}, ∨, ∧, f alse, truei. Fuzzy
CSPs [Schiex 1992] can instead be modeled in the SCSP framework by choosing the
c-semiring SF CSP = h[0, 1], max, min, 0, 1i. Many other “soft” CSPs (Probabilistic,
weighted, . . . ) can be modeled by using a suitable semiring structure (for example,
Sprob = h[0, 1], max, ×, 0, 1i, Sweight = hR, min, +, 0, +∞i, . . . ).
Figure 1 shows the graph representation of a fuzzy CSP. Variables and constraints
are represented respectively by nodes and by undirected arcs (unary for c1 and c3
and binary for c2 ), and semiring values are written to the right of the corresponding
tuples. The variables of interest (that is the set con) are represented with a double
circle. Here we assume that the domain D of the variables contains only elements
a and b.
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

Soft Concurrent Constraint Programming
<a> --> 0.9
<b> --> 0.1
c1
X

<a, a> --> 0.8
<a, b> --> 0.2
<b, a> --> 0
<b, b> --> 0

Fig. 1.

·

7

<a> --> 0.9
<b> --> 0.5
c3
Y
c2

A fuzzy CSP

2.2.3 Combining and projecting soft constraints. Given two constraints c1 =
hdef 1 , con1 i and c2 = hdef 2 , con2 i, their combination c1 ⊗ c2 is the constraint
con
hdef , coni defined by con = con1 ∪ con2 and def (t) = def 1 (t ↓con
con1 ) × def 2 (t ↓con2 ),
X
where t ↓Y denotes the tuple of values over the variables in Y , obtained by projecting tuple t from X to Y . In words, combining two constraints means building
a new constraint involving all the variables of the original ones, and which associates to each tuple of domain values for such variables a semiring element which is
obtained by multiplying the elements associated by the original constraints to the
appropriate subtuples.
Given a constraint c = hdef , coni and a subset I of V , the projection of c over
′
′ ′
′
′
I,
P written c ⇓I is the constraint hdef , con i where con = con ∩ I and def (t ) =
′ def (t). Informally, projecting means eliminating some variables. This
t/t↓con
I∩con =t
is done by associating to each tuple over the remaining variables a semiring element
which is the sum of the elements associated by the original constraint to all the
extensions of this tuple over the eliminated variables. In short, combination is
performed via the multiplicative operation of the semiring, and projection via the
additive one.
2.2.4 Solutions.
The solution of an SCSP problem P = hC, coni is the constraint
N
Sol(P ) = ( C) ⇓con . That is, we combine all constraints, and then project over
the variables in con. In this way we get the constraint over con which is “induced”
by the entire SCSP.
For example, the solution of the fuzzy CSP of Figure 1 associates a semiring
element to every domain value of variable x. Such an element is obtained by first
combining all the constraints together. For instance, for the tuple ha, ai (that
is, x = y = a), we have to compute the minimum between 0.9 (which is the value
assigned to x = a in constraint c1 ), 0.8 (which is the value assigned to hx = a, y = ai
in c2 ) and 0.9 (which is the value for y = a in c3 ). Hence, the resulting value for
this tuple is 0.3. We can do the same work for tuple ha, bi → 0.2, hb, ai → 0 and
hb, bi → 0. The obtained tuples are then projected over variable x, obtaining the
solution hai → 0.8 and hbi → 0.
Sometimes it may be useful to find only a semiring value representing the least
upper bound among the values yielded by the solutions. This is called the best level
of consistency of an SCSP problem P and it is defined by blevel(P ) = Sol(P ) ⇓∅
(for instance, the fuzzy CSP of Figure 1 has best level of consistency 0.8). We also
say that: P is α-consistent if blevel(P ) = α; P is consistent iff there exists α > 0
such that P is α-consistent; P is inconsistent if it is not consistent.
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

8

·

Stefano Bistarelli et al.

3. CONCURRENT CONSTRAINT PROGRAMMING OVER SOFT CONSTRAINTS
Given a semiring S = hA, +, ×, 0, 1i and an ordered set of variables V over a finite
domain D, we will now show how soft constraints over S with a suitable pair of
operators form a semiring, and then, we highlight the properties needed to map
soft constraints over constraint systems “a la Saraswat” (as recalled in Section 2.1.
We start by giving the definition of the carrier set of the semiring.
Definition 3.1 (functional constraints). We define C = (V → D) → A as the set
of all possible constraints that can be built starting from S = hA, +, ×, 0, 1i, D and
V.
A generic function describing the assignment of domain elements to variables will
be denoted in the following by η : V → D. Thus a constraint is a function which,
given an assignment η of the variables, returns a value of the semiring.
Note that in this functional formulation, each constraint is a function and not a
pair representing the variable involved and its definition. Such a function involves
all the variables in V , but it depends on the assignment of only a finite subset of
them. We call this subset the support of the constraint. For computational reasons
we require each support to be finite.
Definition 3.2 (constraint support). Consider a constraint c ∈ C. We define his
support as supp(c) = {v ∈ V | ∃η, d1 , d2 .cη[v := d1 ] 6= cη[v := d2 ]}, where
(
d
if v = v ′ ,
′
η[v := d]v =
ηv ′ otherwise.
Note that cη[v := d1 ] means cη ′ where η ′ is η modified with the association v := d1
(that is the operator [ ] has precedence over application).
Definition 3.3 (functional mapping). Given
any
soft
constraint
hdef, {v1 , . . . , vn }i ∈ C, we can define its corresponding function c ∈ C s.t.
cη[v1 := d1 ] . . . [vn := dn ] = def (d1 , . . . , dn ). Clearly supp(c) ⊆ {v1 , . . . , vn }.
Definition 3.4 (Combination and Sum). Given the set C, we can define the combination and sum functions ⊗, ⊕ : C × C → C as follows:
(c1 ⊗ c2 )η = c1 η ×S c2 η

and

(c1 ⊕ c2 )η = c1 η +S c2 η.

Notice that function ⊗ has the same meaning of the already defined ⊗ operator
(see Section 2.2) while function ⊕ models a sort of disjunction.
By using the ⊕S operator we can easily extend the partial order ≤S over C by
defining c1 ⊑S c2 ⇐⇒ c1 ⊕S c2 = c2 . In the following, when the semiring will be
clear from the context, we will use ⊑.
We can also define a unary operator that will be useful to represent the unit
elements of the two operations ⊕ and ⊗. To do that, we need the definition of
constant functions over a given set of variables.
Definition 3.5 (constant function). We define function ā as the function that
returns the semiring value a for all assignments η, that is, āη = a. We will usually
write ā simply as a.
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

Soft Concurrent Constraint Programming

·

9

An example of constants that will be useful later are 0̄ and 1̄ that represent respectively the constraint associating 0 and 1 to all the assignment of domain values.
It is easy to verify that each constant has an empty support. More generally we
can prove the following:
Proposition 3.6. The support of a constraint c ⇓I is always a subset of I(that
is supp(c ⇓I ) ⊆ I).
Proof. By definition of ⇓I , for any variable x 6∈ I we have c ⇓I η[x = a] = c ⇓I
η[x = b] for any a and b. So, by definition of support x 6∈ supp(c ⇓I ).
Theorem 3.7 (Higher order semiring). The structure SC = hC, ⊕, ⊗, 0, 1i
where
—C : (V → D) → A is the set of all the possible constraints that can be built
starting from S, D and V as defined in Definition 3.1,
—⊗ and ⊕ are the functions defined in Definition 3.4, and
—0 and 1 are constant functions defined following Definition 3.5,
is a c-semiring.
Proof. To prove the theorem it is enough to check all the properties with the
fact that the same properties hold for semiring S. We give here only a hint, by
showing the commutativity of the ⊗ operator:
c1 ⊗ c2 η = (by definition of ⊗)
c1 η × c2 η = (by commutativity of ×)
c2 η × c1 η = (by definition of ⊗)
c2 ⊗ c1 η.
All the other properties can be proved similarly.
The next step is to look for a notion of token and of entailment relation. We define
as tokens the functional constraints in C and we introduce a relation ⊢ that is an
entailment relation when the multiplicative operator of the semiring is idempotent.
Definition 3.8 (⊢ relation). Consider the high order semiring carrier set C and
the partial order ⊑. We define
N the relation ⊢⊆ ℘(C) × C s.t. for each C ∈ ℘(C) and
c ∈ C, we have C ⊢ c ⇐⇒
C ⊑ c.

The next theorem shows that, when the multiplicative operator of the semiring
is idempotent, the ⊢ relation satisfies all the properties needed by an entailment.
Theorem 3.9 (⊢ with idempotent × is an entailment relation).
Consider the higher order semiring carrier set C and the partial order ⊑. Consider
also the relation ⊢ of Definition 3.8. Then, if the multiplicative operation of the
semiring is idempotent, ⊢ is an entailment relation.
Proof. Is enough to check that for any c ∈ C, and for any C1 , C2 and C3 subsets
of C we have
N
(1) C ⊢ c when c ∈ C: We need to show that
C ⊑ c when c ∈ C. This follows
from the extensivity of ×.
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

10

·

Stefano Bistarelli et al.

(2) if C1 ⊢ C2 and C2 ⊢ C3 then C1 ⊢ C3 : To prove this we use the extended
version of the relationN⊢ able to deal with subsets of C : ℘(C) × ℘(C) s.t.
C1 ⊢ C2 ⇐⇒ C1 ⊢
C2 . Note
N that when × is idempotent we have that,
∀c2 ∈ C2 , C1 ⊢ N
c2 ⇐⇒ N
C1 ⊢
CN
2 . In this
Ncase to prove
N the item
N we have
to prove that if
C1 ⊑
C2 and
C2 ⊑
C3 , then
C1 ⊑
C3 . This
comes from the transitivity of ⊑.
Note that in this setting the notion of token (constraint) and of set of tokens (set
of constraints) closed under entailment is used indifferently. In fact, given a set
of constraint functions C1 , its closure
w.r.t. entailment is a set C¯1 that contains
N
all the constraints greater
than
C
.
1 This set is univocally representable by the
N
constraint function
C1 .
The definition of the entailment operator ⊢ on top of the higher order semiring
SC = hC, ⊕, ⊗, 0, 1i and of the ⊑ relation leads to the notion of soft constraint
system. It is also important to notice that in [Saraswat 1993] it is claimed that a
constraint system is a complete algebraic lattice. Here we do not ask for this, since
the algebraic nature of the structure C strictly depends on the properties of the
semiring.
3.1 Non-idempotent ×
If the constraint system is defined on top of a non-idempotent multiplicative operator, we cannot obtain a ⊢ relation satisfying all the properties of an entailment.
Nevertheless, we can give a denotational semantics to the constraint store, as described in Section 4, using the operations of the higher order semiring.
To treat the hiding operator of the language, a general notion of existential
quantifier has to be introduced by using notions similar to those used in cylindric
algebras. Note however that cylindric algebras are first of all boolean algebras.
This could be possible in our framework only when the × operator is idempotent.
Definition 3.10 (hiding). Consider a set of variables V with domain D and the
corresponding softPconstraint system C. We define for each x ∈ V the hiding
function (∃x c)η = di ∈D cη[x := di ].

Notice that x does not belong to the support of ∃x c.
By using the hiding function we can represent the ⇓ operator defined in Section 2.2.
Proposition 3.11. Consider a semiring S = hA, +, ×, 0, 1i, a domain of the
variables D, an ordered set of variables V , the corresponding structure C and the
class of hiding functions ∃x : C → C as defined in Definition 3.10. Then, for any
constraint c and any variable x ⊆ V , c ⇓V −x = ∃x c.
Proof. IsP
enough to apply the definition of ⇓V −x and ∃x and check that both
are equal to di ∈D cη[x := di ].

We now show how the hiding function so defined satisfies the properties of cylindric algebras.
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

Soft Concurrent Constraint Programming

·

11

Theorem 3.12. Consider a semiring S = hA, +, ×, 0, 1i, a domain of the variables D, an ordered set of variables V , the corresponding structure C and the class
of hiding functions ∃x : C → C as defined in Definition 3.10. Then C is a cylindric
algebra satisfying:
(1 ) c ⊢ ∃x c
(2 ) c1 ⊢ c2 implies ∃x c1 ⊢ ∃x c2
(3 ) ∃x (c1 ⊗ ∃x c2 ) ≈ ∃x c1 ⊗ ∃x c2 ,
(4 ) ∃x ∃y c ≈ ∃y ∃x c
Proof. Let us consider all the items:
(1) It follows from the intensivity of +;
(2) It follows from the monotonicity of +;
(3) It follows from theorems about distributivity and idempotence, proven in
[Bistarelli et al. 1997];
(4) It follows from commutativity and associativity of +.

To model parameter passing we need also to define what diagonal elements are.
Definition 3.13 (diagonal elements). Consider an ordered set of variables V and
the corresponding soft constraint system C. Let us define for each x, y ∈ V a
constraint dxy ∈ C s.t., dxy η[x := a, y := b] = 1 if a = b and dxy η[x := a, y := b] = 0
if a 6= b. Notice that supp(dxy ) = {x, y}.
We can prove that the constraints just defined are diagonal elements.
Theorem 3.14. Consider a semiring S = hA, +, ×, 0, 1i, a domain of the variables D, an ordered set of variables V , and the corresponding structure C. The
constraints dxy defined in Definition 3.13 represent diagonal elements, that is
(1 ) dxx = 1,
(2 ) if z 6= x, y then dxy = ∃z (dxz ⊗ dzy ),
(3 ) if x 6= y then dxy ⊗ ∃x (c ⊗ dxy ) ⊢ c.
Proof. (1) It follows from the definition of the 1 constant and of the diagonal
constraint;
(2) The constraint dxz ⊗ dzy is equal to 1 when x = y = z, and is equal to 0 in all
the other cases. If we project this constraint over z, we obtain the constraint
∃z (dxz ⊗ dzy ) that is equal to 1 only when x = y;
(3) The constraint (c ⊗ dxy )η has value 0 whenever η(x) 6= η(y) and cη elsewhere.
Now, (∃x (c⊗dxy ))η is by definition equal to cη[x := y]. Thus (dxy ⊗∃x (c⊗dxy ))η
is equal to cη when η(x) = η(y) and 0 elsewhere. By the last assumption, we
have the relation of entailment with c.

ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

12

·

Stefano Bistarelli et al.
Table II.

scc syntax

P :: = F.A
F :: = p(X) :: A | F.F
A :: = stop | tell(c) →φ A | tell(c) →a A | E | AkA | ∃X.A | p(X)
E :: = ask(c) →φ A | ask(c) →a A | E + E

3.2 Using cc on top of a soft constraint system
The only problem in using a soft constraint system in a cc language is the interpretation of the consistency notion necessary to deal with the ask and tell operations.
Usually SCSPs with best level of consistency equal to 0 are interpreted as inconsistent, and those with level greater than 0 as consistent, but we can be more
general. In fact, we can define a suitable function α that, given the best level
of the actual store, will map such a level over the classical notion of consistency/inconsistency. More precisely, given a semiring S = hA, +, ×, 0, 1i, we can
define a function α : A → {f alse, true}. Function α has to be at least monotone,
but functions with a richer set of properties could be used. It is worth to notice
that in a different environment some of the authors use a similar function to map
elements from a semiring to another, by using abstract interpretation techniques
[Bistarelli et al. 2000a; 2000b]
Whenever we need to check the consistency of the store, we will first compute
the best level and then we will map such a value by using function α over true or
f alse.
It is important to notice that changing the α function (that is, by mapping in
a different way the set of values A over the boolean elements true and f alse), the
same cc agent yields different results: by using a high cut level, the cc agent will
either finish with a failure or succeed with a high final best level of consistency of
the store. On the other hand, by using a low level, more programs will end in a
success state.
4. SOFT CONCURRENT CONSTRAINT PROGRAMMING
The next step in our work is now to extend the syntax of the language in order to
directly handle the cut level. This means that the syntax and semantics of the tell
and ask agents have to be enriched with a threshold to specify when tell/ask agents
have to fail, succeed or suspend.
Given a soft constraint system hS, D, V i and the corresponding structure C, and
any constraint φ ∈ C, the syntax of agents in soft concurrent constraint programming is given in Table II.
The main difference w.r.t. the original cc syntax is
the presence of a semiring element a and of a constraint φ to be checked whenever
an ask or tell operation is performed. More precisely, the level a (resp., φ) will be
used as a cut level to prune computations that are not good enough.
We present here a structured operational semantics for scc programs, in the SOS
style, which consists of defining the semantic of the programming language by specifying a set of configurations Γ, which define the states during execution, a relation
→ ⊆ Γ×Γ which describes the transition relation between the configurations, and a
set T of terminal configurations. To give an operational semantics to our language,
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

Soft Concurrent Constraint Programming
Table III.

·

13

Transition rules for scc

hstop, σi −→ hsuccess, σi

(Stop)

(σ ⊗ c) ⇓∅ 6< a

(Valued-tell)

htell(c) →a A, σi −→ hA, σ ⊗ ci
σ ⊗ c 6⊏ φ
htell(c) →φ A, σi −→ hA, σ ⊗ ci
σ ⊢ c, σ ⇓∅ 6< a
hask(c) →a A, σi −→ hA, σi
σ ⊢ c, σ 6⊏ φ
hask(c) →φ A, σi −→ hA, σi
hA1 , σi −→ hA′1 , σ′ i

(Ask)

hA1 kA2 , σi −→ hA2 , σ′ i
hA2 kA1 , σi −→ hA2 , σ′ i
(Parallelism)

hE1 , σi −→ hA1 , σ′ i
hE1 + E2 , σi −→ hA1 , σ′ i
hE2 + E1 , σi −→ hA1 , σ′ i
h∃x A, σi −→ hA′ , σ′ i

(Valued-ask)

hA1 , σi −→ hsuccess, σ′ i

hA1 kA2 , σi −→ hA′1 kA2 , σ′ i
hA2 kA1 , σi −→ hA2 kA′1 , σ′ i

hA[y/x], σi −→ hA′ , σ′ i

(Tell)

with y fresh

hp(y), σi −→ hA[y/x], σi when p(x) :: A

(Nondeterminism)

(Hidden variables)
(Procedure call)

we need to describe an appropriate transition system.
Definition 4.1 (transition system). A transition system is a triple hΓ, T, →i
where Γ is a set of possible configurations, T ⊆ Γ is the set of terminal configurations and →⊆ Γ × Γ is a binary relation between configurations.
The set of configurations represent the evolutions of the agents and the modifications in the constraint store. We define the transition system of soft cc as
follows:
Definition 4.2 (configurations). The set of configurations for a soft cc system is
the set Γ = {hA, σi} ∪ {hsuccess, σi}, where σ ∈ C. The set of terminal configurations is the set T = {hsuccess, σi} and the transition rule for the scc language are
defined in Table III.
Here is a brief description of the transition rules:
Stop. The stop agent succeeds in one step by transforming itself into terminal
configuration success.
Valued-tell. The valued-tell rule checks for the α-consistency of the SCSP defined
by the store σ ⊗c. The rule can be applied only if the store σ ⊗c is b-consistent with
b 6< a. In this case the agent evolves to the new agent A over the store σ ⊗ c. Note
that different choices of the cut level a could possibly lead to different computations.
Tell. The tell action is a finer check of the store. In this case, a pointwise comparison between the store σ ⊗ c and the constraint φ is performed. The idea is to
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

14

·

Stefano Bistarelli et al.

perform an overall check of the store and to continue the computation only if there
is the possibility to compute a solution not worse than φ.
Valued-ask. The semantics of the valued-ask is extended in a way similar to what
we have done for the valued-tell action. This means that, to apply the rule, we need
to check if the store σ entails the constraint c and also if the store is “consistent
enough” w.r.t. the threshold a set by the programmer.
Ask. Similar to the tell rule, here a finer (pointwise) threshold φ is compared to
the store σ.
Nondeterminism and parallelism. The composition operators + and k are not
modified w.r.t. the classical ones: a parallel agent will succeed if all the agents
succeeds; a nondeterministic rule chooses any agent whose guard succeeds.
Hidden variables. The semantics of the existential quantifier is similar to that
described in [Saraswat 1993] by using the notion of freshness of the new variable
added to the store.
Procedure calls. The semantics of the procedure call is not modified w.r.t. the
classical one. The only difference is the different use of the diagonal constraint to
represent parameter passing.
4.1 Eventual Tell/Ask
We recall that both ask and tell operations in cc could be either atomic (that is,
if the corresponding check is not satisfied, the agent does not evolve) or eventual
(that is, the agent evolves regardless of the result of the check). It is interesting to
notice that the transition rules defined in Table III could be used to provide both
interpretations of the ask and tell operations. In fact, while the generic tell/ask
rule represents an atomic behaviour, by setting φ = 0 or a = 0 we obtain their
eventual version:
htell(c) → A, σi −→ hA, σ ⊗ ci
σ⊢c
hask(c) → A, σi −→ hA, σi

(Eventual tell)
(Eventual ask)

Notice that, by using an eventual interpretation, the transition rules of the scc
become the same as those of cc (with an eventual interpretation too). This happens
since, in the eventual version, the tell/ask agent never checks for consistency and
so the soft notion of α-consistency does not play any role.
5. A SIMPLE EXAMPLE
In this section we will show the behaviour of some of the rules of our transition system. We consider in this example a soft constraint system over the fuzzy semiring.
Consider the fuzzy constraints
c : {x, y} → R2 → [0, 1]
c′ : {x} → R → [0, 1]

1
s.t. c(x, y) =
1 + |x − y|
(
1 if x ≤ 10,
s.t. c′ (x) =
0 otherwise.

ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

and

Soft Concurrent Constraint Programming

·

15

Notice that the domain of both variables x and y is in this example any integer (or
real) number. As any fuzzy CSP, the definition of the constraints is instead in the
interval [0, 1].
Let’s now evaluate the agent
htell(c) →0.4 ask(c′ ) →0.8 stop, 1i
in the empty starting store 1.
By applying the Valued-tell rule we need to check (1 ⊗ c) ⇓∅ 6< 0.4. Since 1 ⊗ c = c
and c ⇓∅ = 1, the agent can perform the step, and it reaches the state
hask(c′ ) →0.8 stop, ci.
Now we need to check (by following the rule of Valued-ask) if c ⊢ c′ and c ⇓∅ 6< 0.8.
While the second relation easily holds, the first one does not hold (in fact, for x = 11
and y = 10 we have c′ (x) = 0 and c(x, y) = 0.5).
1
in place of c′ , then we
If instead we consider the constraint c′′ (x, y) = 1+2×|x−y|
have
hask(c′′ ) →0.8 stop, ci.
Here the condition c ⊢ c” easily holds and the agent ask(c′′ ) →0.8 stop can perform
its last step, reaching the stop and success states:
hstop, c ⊗ c′′ i → hsuccess, c ⊗ c′′ i.
6. OBSERVABLES AND CUTS
Sometimes one could desire to see an agent, and a corresponding program, execute
with a cut level which is different from the one originally given. We will therefore
define cutψ (A) the agent A where all the occurrences of any cut level, say φ, in any
subagent of A or in any clause of the program, are replaced by ψ if φ ⊑ ψ. This
means that the cut level of each subagent and clause becomes at least ψ, or is left
to the original level.
In this paper, for simplicity and generality reasons, this cut level change applies
only to those programs with cut levels which are constraints (φ), and not single
semiring levels (a).
Definition 6.1 (cut function). Consider an scc agent A; we define the function
cutψ : A → A that transforms ask and tell subagents as follows:
(
ask/tell(c) →ψ if φ ⊏ ψ,
cutψ (ask/tell(c) →φ ) =
ask/tell(c) →φ otherwise.
By definition of cutψ , it is easy to see that cut0 (A) = A.
We can then prove the following Lemma (that will be useful later):
Lemma 6.2 (tell and ask cut). Consider the Tell and Ask rules of Table III,
and the constraints σ and c as defined in such rules. Then:
—If the Tell rule can be applied to agent A, then the rule can be applied also to
cutψ (A) when when ψ ⊑ σ ⊗ c.
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

16

·

Stefano Bistarelli et al.

—If the Ask rule can be applied to agent A, then the rule can be applied also to
cutψ (A) when ψ ⊑ σ.
Proof. We will prove only the first item; the second can be easily proved by
using the same ideas. By the definition of the tell transition rules of Table III, if
we can apply the rule it means that A ::= tell(c) →φ A′ and if σ is the store we
have σ ⊗ c 6⊏ φ. Now, by definition of cutψ , we can have
—cutψ (A) ::= tell(c) →ψ cutψ (A′ ) when φ ⊏ ψ.
—cutψ (A) ::= tell(c) →φ cutψ (A′ ) when φ 6⊏ ψ,
In the first case, the statement holds by initial hypothesis over A. In the second
case, since by hypothesis we have σ ⊗ c 6⊏ ψ, again the statement holds by the
definition of the tell transition rules of Table III.
It is now interesting to notice that the thresholds appearing in the program are
related to the final computed stores:
Theorem 6.3 (thresholds). Consider an scc computation
hA, 1i → hA1 , σ1 i → . . . hAn , σn i → hsuccess, σi
for a program P . Then, also
hcutσ (A), 1i → hcutσ (A1 ), σ1 i → . . . hcutσ (An ), σn i → hsuccess, σi
is an scc computation for program P .
Proof. First of all, notice that during the computation an agent can only add
constraints to the store. So, since × is extensive, the store can only monotonically
decrease starting from the initial store 1 and ending in the final store σ. So we
have
1 ⊒ σ1 . . . ⊒ σn ⊒ σ.
Now, the statement follows by applying at each step the results of Lemma 6.2. In
fact, at each step the hypothesis of the lemma hold:
—the cut σ is always lower than the current store (σ ⊑ σi ⊗ c);
—the ask and tell operations can be applied (moving from agent Ai to agent Ai +1).

6.1 Capturing Success Computations.
Given the transition system as defined in the previous section, we now define what
we want to observe of the program behaviour as described by the transitions. To
do this, we define for each agent A the set of constraints
SA = {σ ⇓var(A) | hA, 1i →∗ hsuccess, σi}
that collects the results of the successful computations that the agent can perform.
Notice that the computed store σ is projected over the variables of the agent A to
discard any fresh variable introduced in the store by the ∃ operator.
The observable SA could be refined by considering, instead of the set of successful computations starting from hA, 1i, only a subset of them. For example,
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

Soft Concurrent Constraint Programming

·

17

one could be interested in considering only the best computations: in this case,
all the computations leading to a store worse than one already collected are disregarded. With a pessimistic view, the representative subset could instead collect
all the worst computations (that is, all the computations better than others are
disregarded). Finally, also a set containing both the best and the worst computations could be considered. These options are reminiscent of Hoare, Smith and
Egli-Milner powerdomains respectively [Plotkin 1981].
At this stage, the difference between don’t know and don’t care nondeterminism
arises only in the way the observables are interpreted: in a don’t care approach,
agent A can commit to one of the final stores σ ⇓var(A) , while, in a don’t know
approach, in classical cc programming it is enough that one of the final stores is
consistent. Since existential quantification corresponds to the sum in our semiringbased approach, for us a don’t know approach leads to the sum (that is, the lub)
of all final stores:
M
σ.
Sdk
A =
σ∈SA

It is now interesting to notice that the thresholds appearing in the program are
related also to the observable sets:
Proposition 6.4 (Thresholds and SA (1)). For each ψ, we have SA ⊇
Scutψ (A) .
Proof. By definition of cuts (Definition 6.1), we can modify the agents only by
changing the thresholds with a new level, greater than the previous one. So, easily,
we can only cut away some computations.
dk
Corollary 6.5 (Thresholds and Sdk
⊇
A (1)). For each ψ, we have SA

Sdk
cutψ (A) .

Proof. It follows from the definition of Sdk
A and from Proposition 6.4.
Theorem 6.6 (Thresholds and SA (2)). Let ψ ⊑ glb{σ ∈ SA }. Then SA =
Scutψ (A) .
Proof. By Proposition 6.4, we have SA ⊆ Scutψ (A) . Moreover, since ψ is lower
than all σ in SA , by Theorem 6.3 we have that all the computations are also in
Scutψ (A) . So, the statement follows.
Notice that, thanks to Theorem 6.6 and to Proposition 6.4, whenever we have
a lower bound ψ of the glb of the final solutions, we can use ψ as a threshold to
eliminate some computations. Moreover, we can prove the following theorem:
Theorem 6.7. Let σ ∈ SA and σ 6∈ Scutψ (A) . Then we have σ ⊏ ψ.
Proof. If σ ∈ SA and σ 6∈ Scutψ (A) , it means that the cut eliminates some
computations. So, at some step we have changed the threshold of some tell or ask
agent. In particular, since we know by Theorem 6.3 that when ψ ⊑ σ we do not
modify the computation, we need ψ 6⊑ σ. Moreover, since the tell and ask rules fail
only if σ ⊏ ψ, we easily have the statement of the theorem.
The following theorem relates thresholds and Sdk
A .
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

18

·

Stefano Bistarelli et al.

′
Theorem 6.8 (Thresholds and Sdk
∈
A (2)). Let ΨA = {σ ∈ SA |6 ∃σ
SA with σ ′ ⊒ σ} (that is, ΨA is the set of “greatest” elements of SA ). Let also
dk
ψ ⊑ glb{σ ∈ ΨA }. Then Sdk
A = Scutψ (A) .
L
σ∈SA σ =
LProof. Since we have a + b = b ⇐⇒ a ≤ b, we easily have
σ.
Now,
by
following
a
reasoning
similar
to
Theorem
6.6,
by
applying
a
σ∈ΨA
cut with a threshold
ψ
⊑
glb{σ
∈
Ψ
}
we
do
not
eliminate
any
computation.
So
A
L
L
dk
we obtain Sdk
A =
σ∈ΨA σ = Scutψ (A)
σ∈SA σ =

Lemma 6.9. Given any constraint ψ, we have:

dk
Sdk
A ⊑ ψ + Scutψ (A) .
dk
Proof. Let S be the set of all solutions; then Sdk
A = lub(S) and Scutψ (A) =
lub(S1 ) where S1 ⊆ S. The solutions that have been eliminated by the cut ψ (that
is all the σ ∈ S − S1 ) are all lower than ψ by Theorem 6.7. So, it easily follows that
dk
Sdk
A ⊑ ψ + Scutψ (A) .

Theorem 6.10. Given any constraint ψ, we have:
dk
dk
Sdk
cutψ (A) ⊑ SA ⊑ ψ + Scutψ (A) .
dk
Proof. From Corollary 6.5, we have Sdk
cutψ (A) ⊑ SA . From Lemma 6.9 we have
dk
dk
instead SA ⊑ ψ + Scutψ (A) .

This theorem suggests a way to cut useless computations while generating the
observable Sdk
A of an scc program P starting from agent A. A very naive way to
obtain such an observable would be to first generate all final states, of the form
hsuccess, σi i, and then compute their lub. An alternative, smarter way to compute
this same observable would be to do the following. First we start executing the
program as it is, and find a first solution, say σ1 . Then we restart the execution
applying the cut level σ1 .
By Theorem 6.8, this new cut level cannot eliminate solutions which influence
the computation of the observable: the only solutions it will cut are those that are
lower than the one we already found, thus useless in terms of the computation of
Sdk
A .
In general, after having found solutions σ1 , . . . , σk , we restart execution with cut
level ψ = σ1 + . . .+ σk . Again, this will not cut crucial solutions but only some that
are lower than the sum of those already found. When the execution of the program
terminates with no solution we can be sure that the cut level just used (which is
the sum of all solutions found) is the desired observable (in fact, by Theorem 6.10
dk
dk
when Sdk
cutψ (A) = ψ we necessarily have Scutψ (A) = SA = ψ).
In a way, such an execution method resembles a branch & bound strategy, where
the cut levels have the role of the bounds.
The following corollary is important to show the correctness of this approach.
Corollary 6.11. Given any constraint ψ ⊑ Sdk
A , we have:
dk
Sdk
A = ψ + Scutψ (A) .

Proof. It easily comes from Theorem 6.10.
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

Soft Concurrent Constraint Programming
Table IV.

·

19

Failure in the scc language
σ⊗c ⊏φ

(Tell1 )

htell(c) →φ A, σi −→ f ail
(σ ⊗ c) ⇓∅ < a
htell(c) →a A, σi −→ f ail
σ ⊏φ

(Valued-tell1 )
(Ask1 )

hask(c) →φ A, σi −→ f ail
σ ⇓∅ < a
hask(c) →a A, σi −→ f ail
hE1 , σi −→ f ail, hE2 , σi −→ f ail
hE1 + E2 , σi −→ f ail
hE2 + E1 , σi −→ f ail
hA1 , σi −→ f ail
hA1 kA2 , σi −→ f ail
hA2 kA1 , σi −→ f ail

(Valued-ask1 )
(Nondeterminism1 )

(Parallelism1 )

Let us now use this corollary to prove the correctness of the whole procedure
above.
Let σ1 be the first final state reached by agent A. By stopping the algorithm
dk
after one step, what we have to prove is Sdk
A = σ1 + Scutσ (A) . Since σ1 is for sure
1

lower than Sdk
A , this is true by Corollary 6.11.
By applying this procedure iteratively, we will collect a superset Ψ′A of ΨA =
{σ ∈ SA |6 ∃σ ′ ∈ SA with σ ′ ⊒ σ} (Ψ′A is a superset of ΨA because we could collect
a final state σi before computing a final state σj ⊒ σi ; in this
L will be in
L case both
Ψ′A ). Even if Ψ′A contains more elements then ΨA , we have σ∈Ψ′ = σ∈ΨA (for
A
the extensivity and idempotence properties of +).
The only difference with the procedure we have tested correct w.r.t. the algorithm
is that, at each step, it performs a cut by using the sum of all the previously
computed final state. This means that the algorithm can at each step eliminate
more computations, but by the results of Theorem 6.7 the eliminated computations
does not change the final result.
6.2 Failure
The transition system we have defined considers only successful computations. If
this could be a reasonable choice in a don’t know interpretation of the language it
will lead to an insufficient analysis of the behaviour in a pessimistic interpretation
of the indeterminism. To capture agents’ failure, we add the terminal fail to the
configurations and the transition rules of Table IV to those of Table III.
(Valued)tell1 /ask1 . The failing rule for ask and tell simply checks if the
added/checked constraint c is inconsistent with the store σ and in this case stops
the computation and gives fail as a result. Note that since we use soft constraints
we enriched this operator with a threshold (a or φ). This is used also to compute
failure. If the level of consistency of the resulting store is lower than the threshold
level, then this is considered a failure.
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

20

·

Stefano Bistarelli et al.
Table V.

Hanging computations in the scc language
σ 6⊢ c, σ 6⊏ φ

(Ask2 )

hask(c) →φ A, σi −→ hang
σ 6⊢ c, σ ⇓∅ 6< a

(Valued-ask2 )

hask(c) →a A, σi −→ hang
hE1 , σi −→ f ail/hang, hE2 , σi −→ hang
hE1 + E2 , σi −→ hang
hE2 + E1 , σi −→ hang

(Nondeterminism2 )

Nondeterminism1 . Since the failure of a branch arises only from the failure of
a guard, and since we use angelic non-determinism (that is, we check the guards
before choosing one path), we fail only when all the branches fail.
Parallelism1 . In this case the computation fails as soon as one of the branches
ails.
The observables of each agent can now be enlarged by using the function
FA = {f ail | hA, 1V i →∗ f ail}
that computes a failure if at least a computation of agent A fails.
By considering also the failing computations, the difference between don’t know
and don’t care becomes finer. In fact, in situations where we have SA = Sdk
A ,
the failing computations could make the difference: in the don’t care approach the
notion of failure is existential and in the don’t know one becomes universal [de Boer
and Palamidessi 1994]:
dk
FA
= {f ail | all computations for A which lead to f ail}.

This means that in the don’t know nondeterminism we are interested in observing
a failure only if all the branches fail. In this way, given an agent A with an empty
dk
Sdk
A and a non-empty FA , we cannot say for sure that the semantic of this agent is
f ail. In fact, the transition rules we have defined do not consider hang and infinite
computations. Similar semidecibility results for soft constraint logic programming
are proven in [Bistarelli et al. 2001].
6.3 Hanging and infinite computations
To complete the possible observables of a goal, we need also to observe the hanged
states or those representing infinite computation. To this extent, we extend the
configurations with the terminals hang and ⊥, and we add some transition rules
(those in Table V) to handle hanging computations.
Nondeterminism. The only case that can lead the system to a hanging state is
when all the branches are stuck. In this case, we can assume no future change of
the state will happen that give the possibility to the agents to evolve.
To deal with hang states and infinite computations, we enlarged the observables
with the functions
HA = {hang | hA, 1i →∗ hang}
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

Soft Concurrent Constraint Programming

·

21

that collects all the hang computations of the agent A and
DA = {⊥ | hA, 1i diverges}
to represent infinite computations.
7. AN EXAMPLE FROM THE NETWORK SCENARIO
We consider in this section a simple network problem, involving a set of processes
running on distinct locations and sharing some variables, over which they need to
synchronize, and we show how to model and solve such a problem in scc.
Each process is connected to a set of variables, shared with other processes, and
it can perform several moves. Each of such moves involves performing an action
over some or all the variables connected to the process. An action over a variable
consists of giving a certain value to that variable. A special value “idle” models the
fact that a process does not perfom any action over a variable. Each process has
also the possibility of not moving at all: in this case, all its variables are given the
idle value.
The desired behavior of a network of such processes is that, at each move of the
entire network:
(1) processes sharing a variable perform the same action over it;
(2) as few processes as possible remain idle.
To describe a network of processes with these features, we use an SCSP where
each variable models a shared variable, and each constraint models a process and
connects the variables corresponding to the shared variables of that process. The
domain of each variable in this SCSP is the set of all possible actions, including the
idle one. Each way of satisfying a constraint is therefore a tuple of actions that a
process can perform on the corresponding shared variables.
In this scenario, softness can be introduced both in the domains and in the
constraints. In particular, since we prefer to have as many moving processes as
possible, we can associate a penalty to both the idle element in the domains, and
to tuples containing the idle action in the constraints. As for the other domain
elements and constraint tuples, we can assign them suitable preference values to
model how much we like that action or that process move.
For example, we can use the semiring S = h[−∞, 0], max, +, −∞, 0i, where 0 is
the best preference level (or, said dually, the weakest penalty), −∞ is the worst
level, and preferences (or penalties) are combined by summing them. According
to this semiring, we can assign value −∞ to the idle action or move, and suitable
other preference levels to the other values and moves. Figure 2 gives the details
of a part of a network and it shows eight processes (that is, c1 , . . . , c8 ) sharing a
total of six variables. In this example, we assume that processes c1 , c2 and c3 are
located on site a, processes c5 and c6 are located on site b, and c4 is located on
site c. Processes c7 and c8 are located on site d. Site e connects this part of the
network to the rest. Therefore, for example, variables xd , yd and zd are shared
between processes located in distinct locations.
As desired, finding the best solution for the SCSP representing the current state
of the process network means finding a move for all the processes such that they
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

22

·

Stefano Bistarelli et al.
u_a

e
x_d

c_1 c_3

a

c_2

c_7
y_d

c

d
c_8

c_4

c_6

w_c
c_5
z_d

v_b

b

Fig. 2.

The SCSP describing part of a process network

perform the same action on the shared variables and there is a minimum number
of idle processes. However, since the problem is inherently distributed, it does not
make sense, and it might not even be possible, to centralize all the information and
give it to a single soft constraint solver.
On the contrary, it may be more reasonable to use several soft constraint solvers,
one for each network location, which will take care of handling only the constraints
present in that location. Then, the interaction between processes in different locations, and the necessary agreement to solve the entire problem, will be modelled via
the scc framework, where each agent will represent the behaviour of the processes
in one location.
More precisely, each scc agent (and underlying soft constraint solver) will be in
charge of receiving the necessary information from the other agents (via suitable
asks) and using it to achieve the synchronization of the processes in its location.
For this protocol to work, that is, for obtaining a global optimal solution without
a centralization of the work, the SCSP describing the network of processes has
to have a tree-like shape, where each node of the tree contains all the processes
in a location, and the agents have to communicate from the bottom of the tree
to its root. In fact, the proposed protocol uses a sort of Dynamic Programming
technique to distribute the computation between the locations. In this case the
use of a tree shape allows us to work, at each step of the algorithm, only locally
to one of the locations. In fact, a non tree shape would lead to the construction
of non-local constraints and thus require computations which involve more than
one location at a time. In our example, the tree structure we will use is the one
shown in Figure 3(a), which also shows the direction of the child-parent relation
links (via arrows). Figure 3(b) describes instead the partition of the SCSP over the
four involved locations. The gray connections represent the synchronization to be
assured between distinct locations. Notice that, w.r.t. Figure 2, we have duplicated
the variables representing variables shared between distinct locations, because of
our desire to first perform a local work and then to communicate the results to the
other locations.
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

·

Soft Concurrent Constraint Programming

23

5
u_a

a

4
c_1

1

1

x_a

x_e

c_2

c_3

y_a

3
a
1

x_d

2

d
1

x_c
d

y_b

c_8

1
c_6

c_4

c

c

z_d

w_c

b

(a) A possible tree structure for our network.

Fig. 3.

c_7
y_d

1

b
z_c

z_b

c_5

v_b

(b) The SCSP partitioned over the four locations.

The ordered process network

The scc agents (one for each location plus the parallel composition of all of them)
are therefore defined as follows:

Aa : ∃ua (tell(c1 (xa , ua ) ∧ c2 (ua , ya ) ∧ c3 (xa , ya )) → tell(enda = true) → stop)
Ab : ∃vb (tell(c5 (yb , vb ) ∧ c6 (zb , vb )) → tell(endb = true) → stop)
Ac : ∃wc (tell(c4 (xc , wc , zc )) → tell(endc = true) → stop)
Ad : ask(enda = true ∧ endb = true ∧ endc = true ∧ endd = true) →
tell(c7 (xd , yd ) ∧ c8 (xd , yd , zd ) ∧ xa = xd = xc ∧ ya = yd = yb ∧ zb = zd = zc )
→ tell(endd = true) → stop
A : Aa | Ab | Ac | Ad

Agents Aa ,Ab ,Ac and Ad represent the processes running respectively in the
location a, b, c and d. Note that, at each ask or tell, the underlying soft constraint
solver will only check (for consistency or entailment) a part of the current set of
constraints: those local to one location. Due to the tree structure chosen for this
example, where agents Aa , Ab , and Ac correspond to leaf locations, only agent
Ad shows all the actions of a generic process: first it needs to collect the results
computed separately by the other agents (via the ask); then it performs its own
constraint solving (via a tell), and finally it can set its end flag, that will be used by
a parent agent (in this case the agent corresponding to location e, which we have
not modelled here).
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

24

·

Stefano Bistarelli et al.

8. CONCLUSIONS AND FUTURE WORK
We have shown that cc languages can deal with soft constraints. Moreover, we have
extended their syntax to use soft constraints also to direct and prune the search
process at the language level. We believe that such a new programming paradigm
could be very useful for web and internet programming.
In fact, in several network-related areas, constraints are already being used [Bella
and Bistarelli 2001; Awduche et al. 1999; Clark 1989; Jain and Sun 2000; Calisti
and Faltings 2000]. The soft constraint framework has the advantage over the classical one of selecting a “best” solution also in overconstrained or underconstrained
systems. Moreover, the need to express preferences and to search for optimal solutions shows that soft constraints can improve the modelling of web interaction
scenarios.
ACKNOWLEDGMENTS

We are indebted to Paolo Baldan for valuable suggestions.
REFERENCES
Awduche, D., Malcolm, J., Agogbua, J., O’Dell, M., and McManus, J. 1999. RFC2702:
Requirements for traffic engineering over mpls. Tech. rep., Network Working Group. Sept.
Bella, G. and Bistarelli, S. 2001. Soft constraints for security protocol analysis: Confidentiality. In Proceedings of the 3rd International Symposium on Practical Aspects of Declarative
Languages (PADL ’01), I. Ramakrishnan, Ed. LNCS, vol. 1990. Springer-Verlag, Heidelberg,
Germany, 108–122.
Bistarelli, S. 2001. Soft constraint solving and programming: a general framework. Ph.D. thesis,
Dipartimento di Informatica, Università di Pisa, Italy. TD-2/01.
Bistarelli, S., Codognet, P., and Rossi, F. 2000b. Abstracting soft constraints. In Proceedings
of the 1999 ERCIM/Compulog Net workshop on Constraints, K. Apt, E. Monfroy, T. Kakas,
and F. Rossi, Eds. LNCS, vol. 1865. Springer, Heidelberg, Germany.
Bistarelli, S., Codognet, P., and Rossi, F. 2000a. An abstraction framework for soft constraints and its relationship with constraint propagation. In Proceedings of the Symposium on
Abstraction, Reformulation and Approximation (SARA2000), B. Y. Chouery and T. Walsh,
Eds. LNAI, vol. 1864. Springer, Heidelberg, Germany.
Bistarelli, S., Montanari, U., and Rossi, F. 1995. Constraint Solving over Semirings. In
Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI’95).
Morgan Kaufman, San Francisco, CA, USA.
Bistarelli, S., Montanari, U., and Rossi, F. 1997. Semiring-based Constraint Solving and
Optimization. Journal of the ACM 44, 2 (Mar), 201–236.
Bistarelli, S., Montanari, U., and Rossi, F. 2001. Semiring-based Constraint Logic Programming: Syntax and Semantics. ACM Trans. Program. Lang. Syst. 23, 1–29.
Calisti, M. and Faltings, B. 2000. Distributed constrained agents for allocating service demands
in multi-provider networks,. Journal of the Italian Operational Research Society XXIX, 91.
Special Issue on Constraint-Based Problem Solving.
Chen, S. and Nahrstedt, K. 1998. Distributed QoS routing with imprecise state information.
In ICCCCN98.
Clark, D. 1989. RFC1102: Policy routing in internet protocols. Tech. rep., Network Working
Group. May.
de Boer, F. and Palamidessi, C. 1991. A fully abstract model for concurrent constraint
programming. In Proceeding of the 16th Colloquium on Trees in Algebra and Programming
(CAAP1991), S. Abramsky and T. Maibaum, Eds. Vol. 493. Springer-Verlag, Heidelberg, Germany.
ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

Soft Concurrent Constraint Programming

·

25

de Boer, F. and Palamidessi, C. 1994. From Concurrent Logic Programming to Concurrent
Constraint Programming. In Advances in Logic Programming Theory, G. Levi, Ed. Oxford
University Press, 55–113.
Dubois, D., Fargier, H., and Prade, H. 1993. The calculus of fuzzy restrictions as a basis for
flexible constraint satisfaction. In Proceedings of the 2nd IEEE International Conference on
Fuzzy Systems (FUZZ-IEEE 1993). IEEE, Piscataway, NJ, U.S.A., 1131–1136.
Fargier, H. and Lang, J. 1993. Uncertainty in constraint satisfaction problems: a probabilistic
approach. In Proceeding of the 2nd European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU1993). LNCS, vol. 747. Springer-Verlag,
Heidelberg, Germany, 97–104.
Freuder, E. and Wallace, R. 1992. Partial constraint satisfaction. Artificial Intelligence
Journal 58.
Jain, R. and Sun, W. 2000. QoS/Policy/Constraint-based routing. In Carrier IP Telephony 2000
Comprehensive Report. International Engineering Consortium, Heidelberg, Germany. ISBN: 0933217-75-7.
Plotkin, G. 1981. Post-graduate lecture notes in advanced domain theory (incorporating the
pisa lecture notes). Technical report, Dept. of Computer Science, Univ. of Edinburgh.
Ruttkay, Z. 1994. Fuzzy constraint satisfaction. In Proceedings of the 3rd IEEE International
Conference on Fuzzy Systems (FUZZ-IEEE 1994). 1263–1268.
Saraswat, V. 1993. Concurrent Constraint Programming. MIT Press.
Schiex, T. 1992. Possibilistic constraint satisfaction problems, or “how to handle soft constraints?”. In Proceeding of the 8th Conference on Uncertainty in Artificial Intelligence
(UAI1992). 269–275.
Schiex, T., Fargier, H., and Verfaille, G. 1995. Valued Constraint Satisfaction Problems: Hard
and Easy Problems. In Proceedings of the 14th International Joint Conference on Artificial
Intelligence (IJCAI’95). Morgan Kaufmann, San Francisco, CA, USA, 631–637.
...

ACM Transactions on Computational Logic, Vol. V, No. N, March 2018.

