The role of commutativity in constraint propagation algorithms.
Constraing propagation algorithms form an important part of most of  the constraint programming systems. We provide here a simple, yet very general framework that allows us to explain several constraint propagation algorithms in a systematic way. In this framework we proceed in two steps. First, we introduce a generic iteration algorithm on partial orderings and prove its correctness in an abstract setting. Then we instantiate this algorithm with specific partial orderings and functions to obtain specific constraint propagation algorithms. In particular, using the notions commutativity and semi-commutativity, we show that the AC-3, PC-2, DAC, and DPC algorithms for achieving (directional) arc consistency and (directional) path consistency are instances of a single generic algorithm. The work reported here extends and simplifies that of Apt [1999a].
Introduction
Constraint programming in a nutshell consists of formulating and solving so-called
constraint satisfaction problems. One of the most important techniques developed in this
area is constraint propagation that aims at reducing the search space while maintaining
equivalence.
Constraint propagation is a very widely used concept. For instance on AltaVista,
http://www.altavista.com/on November 19, 1999 the query "constraint prop-
agation" yielded 2344 hits. In addition, in the literature several other names have been
used for the constraint propagation algorithms: consistency, local consistency, consistency
enforcing, Waltz, filtering or narrowing algorithms. So the total number of hits
may well be larger than 4413, the number of hits for the query "NP-completeness".
Over the last twenty few years several constraint propagation algorithms were proposed
and many of them are built into the existing constraint programming systems.
These algorithms usually aim at reaching some form of "local consistency", a notion
that in a loose sense approximates the notion of "global consistency". In Apt [1] we
introduced a simple framework that allowed us to explain many of these algorithms
in a uniform way. In this framework the notion of chaotic iterations, so fair iterations
of functions, on Cartesian products of specific partial orderings played a crucial role.
In Monfroy and R-ety [14] this framework was modified to study distributed chaotic
iterations. This resulted in a general framework for distributed constraint propagation
algorithms.
We stated in Apt [1] that "the attempts of finding general principles behind the
constraint propagation algorithms repeatedly reoccur in the literature on constraint satisfaction
problems spanning the last twenty years" and devoted three pages to survey
this work. Two references that are perhaps closest to our work are Benhamou [3] and
Telerman and Ushakov [17].
These developments led to an identification of a number of mathematical properties
that are of relevance for the considered functions, namely monotonicity, inflationarity
and idempotence (see, e.g., Saraswat, Rinard and Panangaden [16] and Benhamou and
Older [4]). Here we show that also the notions of commutativity and so-called semi-
commutativity are important.
As in Apt [1], to explain the constraint propagation algorithms, we proceed here
in two steps. First, we introduce a generic iteration algorithm on partial orderings and
prove its correctness in an abstract setting. Then we instantiate this algorithm with specific
partial orderings and functions. The partial orderings will be related to the considered
variable domains and the assumed constraints, while the functions will be the ones
that characterize considered notions of local consistency in terms of fixpoints.
This presentation allows us to clarify which properties of the considered functions
are responsible for specific properties of the corresponding algorithms. The resulting
analysis is simpler than that of Apt [1] because we concentrate here on constraint propagation
algorithms that always terminate. This allows us to dispense with the notion of
fairness. On the other hand, we can now prove stronger results by taking into account
the commutativity and semi-commutativity information.
This article is organized as follows. First, in Section 2, drawing on the approach of
Monfroy and R-ety [14], we introduce a generic algorithm for the case when the partial
ordering is not further analyzed. Next, in Section 3, we refine it for the case when the
partial ordering is a Cartesian product of component partial orderings and in Section
4 explain how the introduced notions should be related to the constraint satisfaction
problems. These last two sections essentially follow Apt [1], but because we started
here with the generic iteration algorithms on arbitrary partial orders we built now a
framework in which we can discuss the role of commutativity.
In the next four sections we instantiate the algorithm of Section 2 or some of its refinements
to obtain specific constraint propagation algorithms. In particular, in Section
5 we derive algorithms for arc consistency and hyper-arc consistency. These algorithms
can be improved by taking into account information on commutativity. This is done in
Section 6 and yields the well-known AC-3 algorithm. Next, in Section 7 we derive an
algorithm for path consistency and in Section 8 we improve it, again by using information
on commutativity. This yields the PC-2 algorithm.
In Section 9 we clarify under what assumptions the generic algorithm of Section
2 can be simplified to a simple for loop statement. Then we instantiate this simplified
algorithm to derive in Section 10 the DAC algorithm for directional arc consistency and
in Section 11 the DPC algorithm for directional path consistency. Finally, in Section 12
we briefly discuss possible future work.
We deal here only with the classical algorithms that establish (directional) arc consistency
and (directional) path consistency and that are more than twenty, respectively
ten, years old. However, several more "modern" constraint propagation algorithms can
also be explained in this framework. In particular, in Apt [1, page 203] we derived from
a generic algorithm a simple algorithm that achieves the notion of relational consistency
of Dechter and van Beek [8]. In turn, by mimicking the development of Sections 10 and
11, we can use the framework of Section 9 to derive the adaptive consistency algorithm
of Dechter and Pearl [7].
Dechter [6] showed that this algorithm can be formulated in a very general
framework of bucket elimination that in turn can be used to explain such well-known
algorithms as directional resolution, Fourier-Motzkin elimination, Gaussian elimina-
tion, and also various algorithms that deal with belief networks.
Algorithms
Our presentation is completely general. Consequently, we delay the discussion of constraint
satisfaction problems till Section 4. In what follows we shall rely on the following
concepts.
Definition 1. Consider a partial ordering (D; v ) with the least element ? and a finite
set of functions F := ff on D.
- By an iteration of F we mean an infinite sequence of values d defined
inductively by
where each i j is an element of [1::k].
We say that an increasing sequence d 0 v d 1 v d of elements from D eventually
stabilizes at d if for some j - 0 we have d
In what follows we shall consider iterations of functions that satisfy some specific
properties.
Definition 2. Consider a partial ordering (D; v ) and a function f on D.
- f is called inflationary if x v f(x) for all x.
- f is called monotonic if x v y implies f(x) v f(y) for all x; y. 2
The following simple observation clarifies the role of monotonicity. The subsequent
result will clarify the role of inflationarity.
Consider a partial ordering (D; v ) with the least element
? and a finite set of monotonic functions F on D.
Suppose that an iteration of F eventually stabilizes at a common fixpoint d of the
functions from F . Then d is the least common fixed point of the functions from F .
Proof. Consider a common fixpoint e of the functions from F . We prove that d v e. Let
be the iteration in question. For some j - 0 we have d
It suffices to prove by induction on i that d i v e. The claim obviously holds for
holds for some i - 0. We have d
By the monotonicity of f j and the induction hypothesis we get f j (d i
since e is a fixpoint of f j . 2
We fix now a partial ordering (D; v ) with the least element ? and a set of functions
on D. We are interested in computing the least common fixpoint of
the functions from F . To this end we study the following algorithm that is inspired by
a similar algorithm of Monfroy and R-ety [14].
GENERIC ITERATION ALGORITHM (GI)
d := ?;
G
while G 6= ; do
choose G;
G
G
d := g(d)
od
where for all G; g; d the set of functions update(G; g; d) from F is such that
A. ff
B. implies that update(G;
C. implies that g 2 update(G;
Intuitively, assumption A states that update(G; g; d) at least contains all the functions
from F \Gamma G for which d is a fixpoint but g(d) is not. So at each loop iteration such
functions are added to the set G. In turn, assumption B states that no functions are added
to G in case the value of d did not change. Note that even though after the assignment
G
holds. So assumption A does not provide any information when g is to be added back
to G. This information is provided in assumption C.
On the whole, the idea is to keep in G at least all functions f for which the current
value of d is not a fixpoint.
An obvious example of an update function that satisfies assumptions A and B is
update(G;
where
However, this choice of the update function is computationally expensive because for
each function f in F \Gamma G we would have to compute the values f(g(d)) and f(d). In
practice, we are interested in some approximations of the above update function. We
shall deal with this matter in the next section.
We now prove correctness of this algorithm in the following sense.
Theorem 1 (GI).
(i) Every terminating execution of the GI algorithm computes in d a common fixpoint
of the functions from F .
(ii) Suppose that all functions in F are monotonic. Then every terminating execution
of the GI algorithm computes in d the least common fixpoint of the functions from
F .
(iii) Suppose that all functions in F are inflationary and that (D; v ) is finite. Then
every execution of the GI algorithm terminates.
Proof.
(i) Consider the predicate I defined by:
I := 8f
Note that I is established by the assignment G := F . Moreover, it is easy to check that
by virtue of assumptions A, B and C I is preserved by each while loop iteration. Thus
I is an invariant of the while loop of the algorithm. (In fact, assumptions A, B and C
are so chosen that I becomes an invariant.) Hence upon its termination
holds, that is
(ii) This is a direct consequence of (i) and the Stabilization Lemma 1.
(iii) Consider the lexicographic ordering of the strict partial orderings (D; =) and
defined on the elements of D \Theta N by
We use here the inverse ordering = defined by: d
Given a finite set G we denote by cardG the number of its elements. By assumption
all functions in F are inflationary so, by virtue of assumption B, with each while loop
iteration of the modified algorithm the pair
(d; card G)
strictly decreases in this ordering ! lex . But by assumption (D; v ) is finite, so (D; =)
is well-founded and consequently so is (D \Theta N ; ! lex ). This implies termination. 2
In particular, we obtain the following conclusion.
Corollary 1 (GI). Suppose that (D; v ) is a finite partial ordering with the least
element ?. Let F be a finite set of monotonic and inflationary functions on D. Then
every execution of the GI algorithm terminates and computes in d the least common
fixpoint of the functions from F . 2
In practice, we are not only interested that the update function is easy to compute
but also that it generates small sets of functions. Therefore we show how the function
update can be made smaller when some additional information about the functions in
F is available. This will yield specialized versions of the GI algorithm. First we need
the following simple concepts.
Definition 3. Consider two functions f; g on a set D.
We say that f and g commute if
- We call f idempotent if
The following result holds.
Theorem 2 (Update).
(i) If update(G; g; d) satisfies assumptions A, B and C, then so does the function
update(G;
where
is idempotent and otherwise
(ii) Suppose that for each g the set of functions Comm(g) from F is such that
- each element of Comm(g) commutes with g.
If update(G; g; d) satisfies assumptions A, B and C, then so does the function
update(G;
Proof. It suffices to establish in each case assumption A and C. Let
A := ff
(i) After introducing the GI algorithm we noted already that g 62 A. So assumption A
implies A ' update(G;
For assumption C it suffices to note that g(g(d)) 6= g(d) implies that g is not idem-
potent, i.e., that
(ii) Consider f 2 A. Suppose that f 2 Comm(g). Then
which is a contradiction. So f 62 Comm(g). Consequently, assumption A implies
A ' update(G;
For assumption C it suffices to use the fact that g 62 Comm(g). 2
We conclude that given an instance of the GI algorithm that employs a specific
update function, we can obtain other instances of it by using update functions modified
as above. Note that both modifications are independent of each other and therefore can
be applied together.
In particular, when each function is idempotent and the function Comm satisfies the
assumptions of (ii), then the following holds: if update(G; g; d) satisfies assumptions
so does the function update(G;
3 Compound Domains
In the applications we study the iterations are carried out on a partial ordering that is
a Cartesian product of the partial orderings. So assume now that the partial ordering
(D; v ) is the Cartesian product of some partial orderings (D
each with the least element ? i . So
Further, we assume that each function from F depends from and affects only certain
components of D. To be more precise we introduce a simple notation and terminology.
Definition 4. Consider a sequence of partial orderings (D
- By a scheme (on n) we mean a growing sequence of different elements from [1::n].
- Given a scheme s := on n we denote by (D s ; v s ) the Cartesian product
of the partial orderings (D
- Given a function f on D s we say that f is with scheme s and say that f depends
on i if i is an element of s.
- Given an n-tuple d := d from D and a scheme s := on n we
denote by d[s] the tuple d
l . In particular, for j 2 [1::n] d[j] is the j-th
element of d. 2
Consider now a function f with scheme s. We extend it to a function f + from D to
D as follows. Take d 2 D. We set
is the scheme obtained
by removing from the elements of s. We call f + the canonic extension of f to
the domain D.
any i not in the scheme s of f .
Informally, we can summarize it by saying that f + does not change the components on
which it does not depend. This is what we meant above by stating that each considered
function affects only certain components of D.
We now say that two functions, f with scheme s and g with scheme t commute if
the functions f
Instead of defining iterations for the case of the functions with schemes, we rather
reduce the situation to the one studied in the previous section and consider, equivalently,
the iterations of the canonic extensions of these functions to the common domain D.
However, because of this specific form of the considered functions, we can use now a
simple definition of the update function. More precisely, we have the following observation

Note 1 (Update). Suppose that each function in F is of the form f . Then the following
function update satisfies assumptions A, B and C:
update(G; depends on some i in s such that d[i] 6=
where g is with scheme s.
Proof. To deal with assumption A take a function f G such that f
e that coincides with d on all components that are in the
scheme of f .
Suppose now additionally that f (d). By the above (d) is not such
an e, i.e., (d) differs from d on some component i in the scheme of f . In other words,
f depends on some i such that d[i] 6= g + (d)[i]. This i is then in the scheme of g and
consequently
The proof for assumption B is immediate.
Finally, to deal with assumption C it suffices to note that
implies d, which in turn implies that
This, together with the GI algorithm, yields the following algorithm in which we
introduced a variable d 0 to hold the value of g + (d), and used F 0 := ff
the functions with schemes instead of their canonic extensions to D.
GENERIC ITERATION ALGORITHM FOR COMPOUND DOMAINS (CD)
while G 6= ; do
choose G; suppose g is with scheme s;
G
G depends on some i in s such that d[i] 6= d 0 [i]g;
od
The following corollary to the GI Theorem 1 and the Update Note 1 summarizes
the correctness of this algorithm. It corresponds to Theorem 11 of Apt [1] where the
iteration algorithms were introduced immediately on compound domains.
Corollary 2 (CD). Suppose that (D; v ) is a finite partial ordering that is a Cartesian
product of n partial orderings, each with the least element ? i with
F be a finite set of functions on D, each of the form f
Suppose that all functions in F are monotonic and inflationary. Then every execution
of the CD algorithm terminates and computes in d the least common fixpoint of the
functions from F . 2
In the subsequent presentation we shall deal with the following two modifications
of the CD algorithm:
- CDI algorithm. This is the version of the CD algorithm in which all the functions
are idempotent and the function update defined in the Update Theorem 2(i) is
used.
algorithm. This is the version of the CD algorithm in which all the functions are
idempotent and the combined effect of the functions update defined in the Update
Theorem 2 is used for some function Comm.
For both algorithms the counterparts of the CD Corollary 2 hold.
4 From Partial Orderings to Constraint Satisfaction Problems
We have been so far completely general in our discussion. Recall that our aim is to
derive various constraint propagation algorithms. To be able to apply the results of
the previous section we need to relate various abstract notions that we used there to
constraint satisfaction problems.
This is perhaps the right place to recall the definition and to fix the notation. Consider
a finite sequence of variables X := x respective
domains D := D associated with them. So each variable x i ranges over the
domain D i . By a constraint C on X we mean a subset of D 1
By a constraint satisfaction problem, in short CSP, we mean a finite sequence of
variables X with respective domains D, together with a finite set C of constraints, each
on a subsequence of X . We write it as hC
Consider now an element d := d Dn and a subsequence
of X . Then we denote by d[Y ] the sequence d i 1
By a solution to we mean an element d 2 D 1 \Theta
Dn such that for each constraint C 2 C on a sequence of variables Y we have
We call a CSP consistent if it has a solution. Two CSP's P 1 and P 2 with the
same sequence of variables are called equivalent if they have the same set of solutions.
This definition extends in an obvious way to the case of two CSP's with the same sets
of variables.
Let us return now to the framework of the previous section. It involved:
(i) Partial orderings with the least elements;
These will correspond to partial orderings on the CSP's. In each of them the original
CSP will be the least element and the partial ordering will be determined by the
local consistency notion we wish to achieve.
(ii) Monotonic and inflationary functions with schemes;
These will correspond to the functions that transform the variable domains or the
constraints. Each function will be associated with one or more constraints.
(iii) Common fixpoints;
These will correspond to the CSP's that satisfy the considered notion of local consistency

Let us be now more specific about items (i) and (ii).
Re: (i)
To deal with the local consistency notions considered in this paper we shall introduce
two specific partial orderings on the CSP's. In each of them the considered CSP's
will be defined on the same sequences of variables.
We begin by fixing for each set D a collection F(D) of the subsets of D that includes
D itself. So F is a function that given a set D yields a set of its subsets to which
belongs.
When dealing with the notion of hyper-arc consistency F(D) will be simply the set
P(D) of all subsets of D but for specific domains only specific subsets of D will be cho-
sen. For example, to deal with the the constraint propagation for the linear constraints
on integer interval domains we need to choose for F(D) the set of all subintervals of
the original interval D.
When dealing with the path consistency, for a constraint C the collection F(C)
will be also the set P(C) of all subsets of C. However, in general other choices may
be needed. For example, to deal with the cutting planes method, we need to limit our
attention to the sets of integer solutions to finite sets of linear inequalities with integer
coefficients (see Apt [1, pages 193-194]).
Next, given two CSP's, OE := hC
n i, we write OE v d / iff
- the constraints in C 0 are the restrictions of the constraints in C to the domains
n .
Next, given two CSP's, OE := hC
In what follows we call v d the domain reduction ordering and v c the constraint
reduction ordering. To deal with the arc consistency, hyper-arc consistency and directional
arc consistency notions we shall use the domain reduction ordering, and to deal
with path consistency and directional path consistency notions we shall use the constraint
reduction ordering.
We consider each ordering with some fixed initial CSP P as the least element. In
other words, each domain reduction ordering is of the form
and each constraint reduction ordering is of the form
Re: (ii)
The domain reduction ordering and the constraint reduction ordering are not directly
amenable to the analysis given in Section 3. Therefore, we shall rather use equivalent
partial orderings defined on compound domains. To this end note that hC
This equivalence means that for
the domain reduction ordering (fP with the Cartesian product of the
partial orderings
Additionally, each CSP in this domain reduction ordering is uniquely determined by
its domains and by the initial P . Indeed, by the definition of this ordering the constraints
of such a CSP are restrictions of the constraints of P to the domains of this CSP.
Similarly,
This allows us for to identify the constraint reduction ordering
with the Cartesian product of the partial orderings
Also, each CSP in this constraint reduction ordering is uniquely
determined by its constraints and by the initial P .
In what follows instead of the domain reduction ordering and the constraint reduction
ordering we shall use the corresponding Cartesian products of the partial orderings.
So in these compound orderings the sequences of the domains (respectively, of the con-
straints) are ordered componentwise by the reversed subset ordering '. Further, in each
component ordering (F(D); ') the set D is the least element.
The reason we use these compound orderings is that we can now employ functions
with schemes, as used in Section 3. Each such function f is defined on a sub-Cartesian
product of the constituent partial orderings. Its canonic extension f introduced in
Section 3, is then defined on the "whole" Cartesian product.
Suppose now that we are dealing with the domain reduction ordering with the least
(initial) CSP P and that
Then the sequence of the domains (D uniquely determine a CSP in
this ordering and the same for (D 0
, and a fortiori f , can be
viewed as a function on the CSP's that are elements of this domain reduction ordering.
In other words, f can be viewed as a function on CSP's.
The same considerations apply to the constraint reduction ordering. We shall use
these observations when arguing about the equivalence between the original and the
final CSP's for various constraint propagation algorithms.
The considered functions with schemes will be now used in presence of the componentwise
ordering '. The following observation will be useful.
Consider a function f on some Cartesian product
that f is inflationary w.r.t. the componentwise ordering ' if for all (X
Also, f is monotonic w.r.t. the componentwise ordering ' if for all (X
i for all i 2 [1::m], the
following holds: if
In other words, f is monotonic w.r.t. ' iff it is monotonic w.r.t. This reversal of
the set inclusion of course does not hold for the inflationarity notion.
5 A Hyper-arc Consistency Algorithm
We begin by considering the notion of hyper-arc consistency of Mohr and Masini [13]
(we use here the terminology of Marriott and Stuckey [11]). The more known notion of
arc consistency of Mackworth [10] is obtained by restricting one's attention to binary
constraints. Let us recall the definition.
Definition 5.
- Consider a constraint C on the variables x with the respective domains
that is C 'D 1 \Theta \Delta \Delta \Delta \Theta Dn . We call C hyper-arc consistent if for every
there exists d 2 C such that a = d[i].
We call a CSP hyper-arc consistent if all its constraints are hyper-arc consistent. 2
Intuitively, a constraint C is hyper-arc consistent if for every involved domain each
element of it participates in a solution to C.
To employ the CDI algorithm of Section 3 we now make specific choices involving
the items (i), (ii) and (iii) of the previous section.
Re: (i) Partial orderings with the least elements.
As already mentioned in the previous section, for the function F we choose the
powerset function P , so for each domain D we put F(D) := P(D).
Given a CSP P with the sequence D of the domains we take the domain
reduction ordering with P as its least element. As already noted we can identify this
ordering with the Cartesian product of the partial orderings (P(D i
[1::n]. The elements of this compound ordering are thus sequences (X
respective subsets of the domains D by the reversed
subset ordering '.
Re: (ii) Monotonic and inflationary functions with schemes.
Given a constraint C on the variables y respective domains
we abbreviate for each j 2 [1::k] the set fd[j] j d 2 Cg to \Pi j (C). Thus \Pi j (C) consists
of all j-th coordinates of the elements of C. Consequently, \Pi j (C) is a subset of
the domain E j of the variable y j .
We now introduce for each i 2 [1::k] the following function - i on
where
That is,
Cg. Each function - i is associated
with a specific constraint C. Note that X 0
so each function - i boils down to a
projection on the i-th component.
Re: (iii) Common fixpoints.
Their use is clarified by the following lemma that also lists the relevant properties
of the functions - i (see Apt [1, pages 197 and 202]).
common fixpoint of all functions -
associated with the constraints from C.
(ii) Each projection function - i associated with a constraint C is
inflationary w.r.t. the componentwise ordering ',
monotonic w.r.t. the componentwise ordering ',
By taking into account only the binary constraints we obtain an analogous characterization
of arc consistency. The functions - 1 and - 2 can then be defined more directly
as follows:
Cg, and
Cg.
Fix now a CSP P . By instantiating the CDI algorithm with
associated with a constraint of Pg
and with each ? i equal to D i we get the HYPER-ARC algorithm that enjoys following
properties.
Theorem 3 (HYPER-ARC Algorithm). Consider a CSP P := hC
each D i is finite.
The HYPER-ARC algorithm always terminates. Let P 0 be the CSP determined by
P and the sequence of the domains D 0
n computed in d. Then
is the v d -least CSP that is hyper-arc consistent,
is equivalent to P . 2
Due to the definition of the v d ordering the item (i) can be rephrased as follows.
Consider all hyper-arc consistent CSP's that are of the form hC
and the constraints in C 0 are the restrictions of the
constraints in C to the domains D 0
n . Then among these CSP's P 0 has the largest
domains.
Proof. The termination and (i) are immediate consequences of the counterpart of the
CD Corollary 2 for the CDI algorithm and of the Hyper-arc Consistency Lemma 2.
To prove (ii) note that the final CSP P 0 can be obtained by means of repeated
applications of the projection functions - i starting with the initial CSP P . (Conforming
to the discussion at the end of Section 4 we view here each such function as a function
on CSP's). As noted in Apt [1, pages 197 and 201]) each of these functions transforms
a CSP into an equivalent one. 2
6 An Improvement: the AC-3 Algorithm
In this section we show how we can exploit an information about the commutativity of
the - i functions. Recall that in Section 3 we modified the notion of commutativity for
the case of functions with schemes. We now need the following lemma.
Lemma 3 (Commutativity). Consider a CSP and two constraints of it, C on the variables
on the variables z
(i) For [1::k] the functions - i and - j of the constraint C commute.
(ii) If the variables y i and z j are identical then the functions - i of C and - j of E
commute.
Proof.
(i) It suffices to notice that for each k-tuple X of subsets of the domains of
the respective variables we have
where
and where we assumed that i ! j.
(ii) Let the considered CSP be of the form hC Assume that
some common variable of y is identical to the variable x h .
Further, let Sol(C; E) denote the set of d 2 D 1 Dn such that d[s] 2 C and
s is the scheme of C and t is the scheme of E.
Finally, let f denote the - i function of C and g the - j function of E. It is easy to
check that for each n-tuple X of subsets of D respectively, we have
where
)):It is worthwhile to note that not all pairs of the - i and - j functions commute.
Example 1.
(i) First, we consider the case of two binary constraints on the same variables. Consider
two variables, x and y with the corresponding domains D x := fa; bg, D y := fc; dg
and two constraints on x; y: C 1 := f(a; c); (b; d)g and C 2 := f(a; d)g.
Next, consider the - 1 function of C 1 and the - 2 function of C 2 . Then applying
these functions in one order, namely - 2 - 1 , to (D x ; D y ) yields D x unchanged, whereas
applying them in the other order, - 1 - 2 , yields D x equal to fbg.
(ii) Next, we show that the commutativity can also be violated due to sharing of a
single variable. As an example take the variables x; z with the corresponding domains
D x := fa; bg, D y := fbg, D z := fc; dg, and the constraint C 1 := f(a; b)g on x; y and
(b; d)g on x; z.
Consider now the - +function of C 1 and the - +function of C 2 . Then applying
these functions in one order, namely -
- +, to (D x ; D y ; D z ) yields D z equal to fcg,
whereas applying them in the other order, -
Fix now a CSP. We derive a modification of the HYPER-ARC algorithm by instantiating
this time the CDC algorithm. As before we use the set of functions F 0 :=
associated with a constraint of Pg and each ? i equal to D i . Additionally
we employ the following function Comm, where - i is associated with a constraint
C:
associated with the constraint Cg
associated with a constraint E and
the i-th variable of C and the j-th variable of E coincideg.
By virtue of the Commutativity Lemma 3 each set Comm(g) satisfies the assumptions
of the Update Theorem 2(ii).
By limiting oneself to the set of functions - 1 and - 2 associated with the binary
constraints, we obtain an analogous modification of the corresponding arc consistency
algorithm.
Using now the counterpart of the CD Corollary 2 for the CDC algorithm we conclude
that the above algorithm enjoys the same properties as the HYPER-ARC algorithm, that
is the counterpart of the HYPER-ARC Algorithm Theorem 3 holds.
Let us clarify now the difference between this algorithm and the HYPER-ARC algorithm
when both of them are limited to the binary constraints.
Assume that the considered CSP is of the form hC ; DEi. We reformulate the above
algorithm as follows. Given a binary relation R, we put
For F 0 we now choose the set of the - 1 functions of the constraints or relations from
the set
is a binary constraint from Cg
is a binary constraint from Cg.
Finally, for each - 1 function of some C 2 S 0 on x; y we define
is the - 1 function of C T g
is the - 1 function of some E 2 S 0 on x; z where z 6j yg.
Assume now that
for each pair of variables x; y at most one constraint exists on x; y. (1)
Consider now the corresponding instance of the CDC algorithm. By incorporating
into it the effect of the functions - 1 on the corresponding domains, we obtain the following
algorithm known as the AC-3 algorithm of Mackworth [10].
We assume here that DE := x
AC-3 ALGORITHM
is a binary constraint from Cg
is a binary constraint from Cg;
while S 6= ; do
choose C 2 suppose C is on x
if D i changed then
S is on the variables
od
It is useful to mention that the corresponding reformulation of the HYPER-ARC
algorithm differs in the second assignment to S which is then
S is on the variables z where y is x i or z is x i g:
So we "capitalized" here on the commutativity of the corresponding projection
functions - 1 as follows. First, no constraint or relation on x i ; z for some z is added
to S. Here we exploited part (ii) of the Commutativity Lemma 3.
Second, no constraint or relation on x added to S. Here we exploited part (i)
of the Commutativity Lemma 3, because by assumption (1) C T is the only constraint
or relation on x coincides with the - 2 function of C.
In case the assumption (1) about the considered CSP is dropped, the resulting algorithm
is somewhat less readable. However, once we use the following modified definition
of Comm(- 1
is the - 1 function of some E 2 S 0 on x; z where z 6j yg
we get an instance of the CDC algorithm which differs from the AC-3 algorithm in
that the qualification "where y 6j x j " is removed from the definition of the second
assignment to the set S.
7 A Path Consistency Algorithm
The notion of path consistency was introduced in Montanari [15]. It is defined for special
type of CSP's. For simplicity we ignore here unary constraints that are usually
present when studying path consistency.
Definition 6. We call a CSP P normalized if for each subsequence X of its variables
there exists at most one constraint on X in P .
Given a normalized CSP and a subsequence X of its variables we denote by CX the
unique constraint on the variables X if it exists and otherwise the "universal" relation
on X that equals the Cartesian product of the domains of the variables in X . 2
Every CSP is trivially equivalent to a normalized CSP. Indeed, for each subsequence
X of the variables of P such that a constraint on X exists, we just need to replace the
set of all constraints on X by its intersection. Note that the universal relations CX are
not constraints of the normalized CSP.
To simplify the notation given two binary relations R and S we define their composition
by
R
Note that if R is a constraint on the variables x; y and S a constraint on the variables
z, then R \Delta S is a constraint on the variables x; z.
Given a subsequence x; y of two variables of a normalized CSP we introduce a
"supplementary" relation C y;x defined by
Recall that the relation C T was introduced in the previous section. The supplementary
relations are not parts of the considered CSP as none of them is defined on a
subsequence of its variables, but they allow us a more compact presentation. We now
introduce the following notion.
Definition 7. We call a normalized CSP path consistent if for each subset fx; y; zg of
its variables we have
:In other words, a normalized CSP is path consistent if for each subset fx; y; zg of
its variables the following holds:
if (a; c) 2 C x;z , then there exists b such that (a; b) 2 C x;y and (b; c) 2 C y;z .
In the above definition we used the relations of the form C u;v for any subset fu; vg
of the considered sequence of variables. If u; v is not a subsequence of the original sequence
of variables, then C u;v is a supplementary relation that is not a constraint of the
original CSP. At the expense of some redundancy we can rewrite the above definition so
that only the constraints of the considered CSP and the universal relations are involved.
This is the contents of the following simple observation that will be useful later in this
section.
(Alternative Path Consistency). A normalized CSP is path consistent iff for each
subsequence z of its variables we have
x z
y
Fig. 1. Three relations on three variables

Figure

1 clarifies this observation. For instance, an indirect path from x to y via z
requires the reversal of the arc (y; z). This translates to the first formula.
Recall that for a subsequence x; z of the variables the relations C x;y ; C x;z and
C y;z denote either constraints of the considered normalized CSP or the universal binary
relations on the domains of the corresponding variables.
Given a subsequence x; z of the variables of P we now introduce three functions
on P(C x;y ) \Theta P(C x;z ) \Theta P(C y;z
f z
x;y
f y
Finally, we introduce common fixpoints of the above defined functions. To this end
we need the following counterpart of the Hyper-arc Consistency Lemma 2.
Lemma 4 (Path Consistency).
(i) A normalized CSP hC
fixpoint of all functions (f z
associated with the sub-sequences
z of its variables.
(ii) The functions f z
x;y , f y
x;z and f x
are
inflationary w.r.t. the componentwise ordering ',
monotonic w.r.t. the componentwise ordering ',
Proof. (i) is a direct consequence of the Alternative Path Consistency Note 2. The
proof of (ii) is straightforward. These properties of the functions f z
x;y , f y
x;z and f x
were already mentioned in Apt [1, page 193].We now instantiate the CDI algorithm with the set of functions
z is a subsequence of the variables of P and f 2 ff z
each ? i equal to C i .
Call the resulting algorithm the PATH algorithm. It enjoys the following properties.
Theorem 4 (PATH Algorithm). Consider a normalized CSP P := hC
Assume that each constraint C i is finite.
The PATH algorithm always terminates. Let P 0 := hC 0
where the
sequence of the constraints C 0
k is computed in d. Then
is the v c -least CSP that is path consistent,
is equivalent to P .
As in the case of the HYPER-ARC Algorithm Theorem 3 the item (i) can be rephrased
as follows. Consider all path consistent CSP's that are of the form hC 0
has the largest constraints.
Proof. The proof is analogous to that of the HYPER-ARC Algorithm Theorem 3.
To prove (ii) we now note that the final CSP P 0 can be obtained by means of
repeated applications of the functions f z
x;y , f y
x;z and f x
y;z starting with the initial CSP P .
(Conforming to the discussion at the end of Section 4 we view here each such function
as a function on CSP's). As noted in Apt [1, pages 193 and 195]) each of these functions
transforms a CSP into an equivalent one. 2
8 An Improvement: the PC-2 Algorithm
As in the case of the hyper-arc consistency we can improve the PATH algorithm by
taking into account the commutativity information.
Fix a normalized CSP P . We abbreviate the statement "x; y is a subsequence of the
variables of P " to x OE y. We now have the following lemma.
Lemma 5 (Commutativity). Suppose that x OE y and let z; u be some variables of P
such that fu; zg " fx; ;. Then the functions f z
x;y and f u
x;y commute.
In other words, two functions with the same pair of variables as a subscript commute

Proof. The following intuitive argument may help to understand the subsequent, more
formal justification. First, both considered functions have three arguments but share
exactly one argument and modify only this shared argument. Second, both functions
are defined in terms of the set-theoretic intersection operation """ applied to two, un-
changed, arguments. This yields commutativity since """ is commutative.
In the more formal argument note first that the "relative" positions of z and of u
w.r.t. x and y are not specified. There are in total three possibilities concerning z and
three possibilities concerning u. For instance, z can be "before" x , "between" x and y
or "after" y. So we have to consider in total nine cases.
In what follows we limit ourselves to an analysis of three representative cases. The
proof for the remaining six cases is completely analogous.
Case 1. y OE z and y OE u.
x y
z
Fig. 2. Four variables connected by directed arcs
It helps to visualize these variables as in Figure 2. Informally, the functions f z
x;y
and f u
x;y correspond, respectively, to the upper and lower triangle in this figure. The
fact that these triangles share an edge corresponds to the fact that the functions f z
x;y and
f u
x;y share precisely one argument, the one from P(C x;y ).
Ignoring the arguments that do not correspond to the schemes of the functions f z
x;y
and f u
x;y we can assume that the functions (f z
are both defined on
Each of these functions changes only the first argument. In fact, for all elements
of, respectively, P(C x;y ); P(C x;z ); P(C y;z ); P(C x;u ) and P(C y;u ), we have
(f z
Case 2. x OE z OE y OE u.
The intuitive explanation is analogous as in Case 1. We confine ourselves to noting
that (f z
are now defined on
but each of them changes only the second argument. In fact, we have
(f z
Case 3. z OE x and y OE u.
In this case the functions (f z
are defined on
but each of them changes only the third argument. In fact, we have
(f z
now instantiate the CDC algorithm with the same set of functions F 0 as in Section
7. Additionally, we use the function Comm defined as follows, where x OE y and
where z 62 fx; yg:
Comm(f z
Thus for each function g the set Comm(g) contains precisely
where m is the number of variables of the considered CSP. This quantifies the maximal
"gain" obtained by using the commutativity information: at each "update" stage of the
corresponding instance of the CDC algorithm we add up to m \Gamma 3 less elements than in
the case of the corresponding instance of the CDI algorithm considered in the previous
section.
By virtue of the Commutativity Lemma 5 each set Comm(g) satisfies the assumptions
of the Update Theorem 2(ii). We conclude that the above instance of the CDC
algorithm enjoys the same properties as the original PATH algorithm, that is the counterpart
of the PATH Algorithm Theorem 4 holds. To make this modification of the PATH
algorithm easier to understand we proceed as follows.
Each function of the form f u
x;y where x OE y and u 62 fx; yg can be identified with
the sequence x; u; y of the variables. (Note that the "relative" position of u w.r.t. x and
y is not fixed, so x; u; y does not have to be a subsequence of the variables of P.) This
allows us to identify the set of functions F 0 with the set
Next, assuming that x OE y, we introduce the following set of triples of different
variables of P :
xg.
Informally, V x;y is the subset of V 0 that consists of the triples that begin or end
with either x; y or x. This corresponds to the set of functions in one of the following
forms: f y
u;y and f y
u;x .
The above instance of the CDC algorithm then becomes the following PC-2 algorithm
of Mackworth [10]. Here initially
while do
choose
apply f u
x;y to its current domains;
od
Here the phrase "apply f u
x;y to its current domains" can be made more precise if the
"relative" position of u w.r.t. x and y is known. Suppose for instance that u is "before"
x and y. Then f u
x;y is defined on P(C u;x ) \Theta P(C u;y ) \Theta P(C x;y ) by
f u
x;y
so the above phrase "apply f u
x;y to its current domains" can be replaced by the assign-
ment
Analogously for the other two possibilities.
The difference between the PC-2 algorithm and the corresponding representation
of the PATH algorithm lies in the way the modification of the set V is carried out. In
the case of the PATH algorithm the second assignment to V is
9 Simple Iteration Algorithms
Let us return now to the framework of Section 2. We analyze here when the while loop
of the GENERIC ITERATION ALGORITHM GI can be replaced by a for loop. First, we
weaken the notion of commutativity as follows.
Definition 8. Consider a partial ordering (D; v ) and functions f and g on D. We say
that f semi-commutes with g (w.r.t. v ) if f(g(x)) v g(f(x)) for all x. 2
The following lemma provides an answer to the question just posed. Here and elsewhere
we omit brackets when writing repeated applications of functions to an argument.
Lemma 6 (Simple Iteration). Consider a partial ordering (D; v ) with the least element
?. Let F := f be a finite sequence of monotonic, inflationary and idempotent
functions on D. Suppose that f i semi-commutes with f j for i ? j, that is,
is the least common fixpoint of the functions from F . 2
Proof. We prove first that for i 2 [1::k] we have
Indeed, by the assumption (2) we have the following string of inclusions, where the last
one is due to the idempotence of the considered functions:
Additionally, by the inflationarity of the considered functions, we also have for
[1::k]
is a common fixpoint of the functions from F . This means that
the iteration of F that starts with ?, f k (?), f eventually
stabilizes at f 1 (?). By the Stabilization Lemma 1 we get the desired conclusion.The above lemma provides us with a simple way of computing the least common
fixpoint of a set of finite functions that satisfy the assumptions of this lemma, in particular
condition (2). Namely, it suffices to order these functions in an appropriate way
and then to apply each of them just once, starting with the argument ?.
To this end we maintain the considered functions not in a set but in a list. Given a
non-empty list L we denote its head by head(L) and its tail by tail(L). Next, given a
sequence of elements an with n - 0, we denote by [a an ] the list formed
by them. If this list is empty and is denoted by [
an an
The following algorithm is a counterpart of the GI algorithm. We assume in it that
condition (2) holds for the functions f
SIMPLE ITERATION ALGORITHM (SI)
d := ?;
for to k do
d := g(d)
od
The following immediate consequence of the Simple Iteration Lemma 6 is a counterpart
of the GI Corollary 1.
Corollary 3 (SI). Suppose that (D; v ) is a partial ordering with the least element
?. Let F := f be a finite sequence of monotonic, inflationary and idempotent
functions on D such that (2) holds. Then the SI algorithm terminates and computes in
d the least common fixpoint of the functions from F . 2
Note that in contrast to the GI Corollary 1 we do not require here that the partial ordering
is finite. Because at each iteration of the for loop exactly one element is removed
from the list L, at the end of this loop the list L is empty. Consequently, this algorithm
is a reformulation of the one in which the line
for to k do
is replaced by
while
So we can view the SI algorithm as a specialization of the GI algorithm of Section
2 in which the elements of the set of functions G (here represented by the list L) are
selected in a specific way and in which the update function always yields the empty
set.
In Section 3 we refined the GI algorithm for the case of compound domains. An
analogous refinement of the SI algorithm is straightforward and omitted. In the next
two sections we show how we can use this refinement of the SI algorithm to derive two
well-known constraint propagation algorithms.
Directional Arc Consistency Algorithm
We consider here the notion of directional arc consistency of Dechter and Pearl [7]. Let
us recall the definition.
Definition 9. Assume a linear ordering OE on the considered variables.
- Consider a binary constraint C on the variables x; y with the domains D x and D y .
We call C directionally arc consistent w.r.t. OE if
y,
So out of these two conditions on C exactly one needs to be checked.
We call a CSP directionally arc consistent w.r.t. OE if all its binary constraints are
directionally arc consistent w.r.t. OE. 2
To derive an algorithm that achieves this local consistency notion we first characterize
it in terms of fixpoints. To this end, given a P and a linear ordering OE on its variables,
we rather reason in terms of the equivalent CSP P OE obtained from P by reordering its
variables along OE so that each constraint in P OE is on a sequence of variables x
such that x 1 OE x
The following simple characterization holds.
Lemma 7 (Directional Arc Consistency). Consider a CSP P with a linear ordering
OE on its variables. Let P OE := hC directionally arc
consistent w.r.t. OE iff (D fixpoint of the functions -
associated
with the binary constraints from P OE . 2
We now instantiate in an appropriate way the SI algorithm for compound domains
with all the - 1 functions associated with the binary constraints from P OE . In this way
we obtain an algorithm that achieves for P directional arc consistency w.r.t. OE. First,
we adjust the definition of semi-commutativity to functions with different schemes. To
this end consider a sequence of partial orderings (D
Cartesian product (D; v ). Take two functions, f with scheme s and g with scheme t.
We say that f semi-commutes with g (w.r.t. v semi-commutes with w.r.t.
v , that is if
for all Q 2 D.
The following lemma is crucial.
Lemma 8 (Semi-commutativity). Consider a CSP and two binary constraints of it,
C 1 on u; z and C 2 on x; y, where y OE z.
Then the - 1 function of C 1 semi-commutes with the - 1 function of C 2 w.r.t. the
componentwise ordering '.
Proof. Denote by f u;z the - 1 function of C 1 and by f x;y the - 1 function of C 2 . The
following cases arise.
Case 1.
Then the functions f u;z and f x;y commute since their schemes are disjoint.
Case 2. fu; zg " fx; yg 6= ;.
Subcase 1.
Then the functions f u;z and f x;y commute by virtue of the Commutativity Lemma
3(ii).
Subcase 2. y.
Let the considered CSP be of the form hC We can
rephrase the claim as follows, where we denote now f u;z by f y;z : For all (X
To prove it note first that for some
. We now have
where
and
whereas
where
By the Hyper-arc Consistency Lemma 2(ii) each function - i is inflationary and
monotonic w.r.t. the componentwise ordering '. By the first property applied to f y;z
we have
so by the second property applied to f x;y we have X 0
This establishes the claim.
Subcase 3. z = x.
This subcase cannot arise since then the variable z precedes the variable y whereas
by assumption the converse is the case.
Subcase 4. z = y.
We can assume by Subcase 1 that u 6= x. Then the functions f u;z and f x;y commute
since each of them changes only its first component.
This concludes the proof. 2
Consider now a CSP P with a linear ordering OE on its variables and the corresponding
CSP P OE . To be able to apply the above lemma we order the - 1 functions of
the binary constraints of P OE in an appropriate way. Namely, given two
associated with a constraint on u; z and g associated with a constraint on x; y, we put f
before g if y OE z.
More precisely, let x xn be the sequence of the variables of P OE . So x 1 OE x 2 OE
the list Lm consist of the - 1 functions of those binary
constraints of P OE that are on x j ; xm for some x j . We order each list Lm arbitrarily.
Consider now the list L resulting from appending Ln ; in that order, so
with the elements of Ln in front. Then by virtue of the Semi-commutativity Lemma 8 if
the function f precedes the function g in the list L, then f semi-commutes with g w.r.t.
the componentwise ordering '.
We instantiate now the refinement of the SI algorithm for the compound domains
by the above-defined list L and each ? i equal to the domain D i of the variable x i . We
assume that L has k elements. We obtain then the following algorithm.
DIRECTIONAL ARC CONSISTENCY ALGORITHM (DARC)
for to k do
suppose g is with scheme s;
od
This algorithm enjoys the following properties.
Theorem 5 (DARC Algorithm). Consider a CSP P with a linear ordering OE on its
variables. Let P OE := hC
The DARC algorithm always terminates. Let P 0 be the CSP determined by P OE and
the sequence of the domains D 0
n computed in d. Then
is the v d -least CSP in fP that is directionally arc consistent
w.r.t. OE,
is equivalent to P . 2
The termination and (i) are immediate consequences of the counterpart of the SI
Corollary 3 for the SI algorithm refined for the compound domains and of the Directional
Arc Consistency Lemma 7.
The proof of (ii) is analogous to that of the HYPER-ARC Algorithm Theorem 3(ii).
Note that in contrast to the HYPER-ARC Algorithm Theorem 3 we do not need to
assume here that each domain is finite.
Assume now that for each pair of variables x; y of the original CSP P there exists
precisely one constraint on x; y. The same holds then for P OE . Suppose that P OE :=
Denote the unique constraint of P OE on x
The above DARC algorithm can then be rewritten as the following algorithm known as
the DAC algorithm of Dechter and Pearl [7]:
for j := n to 2 by \Gamma1 do
for
od
od
11 DPC: a Directional Path Consistency Algorithm
In this section we deal with the notion of directional path consistency defined in Dechter
and Pearl [7]. Let us recall the definition.
Definition 10. Assume a linear ordering OE on the considered variables. We call a normalized
CSP directionally path consistent w.r.t. OE if for each subset fx; y; zg of its
variables we have
This definition relies on the supplementary relations because the ordering OE may
differ from the original ordering of the variables. For example, in the original ordering
z can precede x. In this case C z;x and not C x;z is a constraint of the CSP under
consideration.
But just as in the case of path consistency we can rewrite this definition using the
original constraints only. In fact, we have the following analogue of the Alternative Path
Consistency Note 2.
Note 3 (Alternative Directional Path Consistency). A normalized CSP is directionally
path consistent w.r.t. OE iff for each subsequence x; y; z of its variables we have
x:Thus out of the above three inclusions precisely one needs to be checked.
As before we now characterize this local consistency notion in terms of fixpoints.
To this end, as in the previous section, given a normalized CSP P we rather consider
the equivalent CSP P OE . The variables of P OE are ordered according to OE and on each
pair of its variables there exists a unique constraint.
The following counterpart of the Directional Arc Consistency Lemma 7 is a direct
consequence of the Alternative Directional Path Consistency Note 3.
Lemma 9 (Directional Path Consistency). Consider a normalized CSP P with a linear
ordering OE on its variables. Let P OE := hC directionally
path consistent w.r.t. OE iff (C fixpoint of all functions (f z
associated with the subsequences x; z of the variables of P OE . 2
To obtain an algorithm that achieves directional path consistency we now instantiate
in an appropriate way the SI algorithm. To this end we need the following lemma.
Consider a normalized CSP and two subsequences
of its variables, x Suppose that u OE z.
Then the function f z
semi-commutes with the function f u
x2 ;y2 w.r.t. the componentwise
ordering '.
Proof. The following cases arise.
Case 1.
In this and other cases by an equality between two pairs of variables we mean that
both the first component variables, here x 1 and x 2 , and the second component variables,
here y 1 and y 2 , are identical.
In this case the functions f z
x1 ;y1 and f u
x2 ;y2 commute by virtue of the Commutativity
Lemma 5.
Case 2.
Ignoring the arguments that do not correspond to the schemes of the functions f z
and f u
x2 ;y2 we can assume that the functions (f z
are both defined
on
The following now holds for all elements respectively, P(C x1 ;y1 ),
(f z
Case 3.
Again ignoring the arguments that do not correspond to the schemes of the functions
f z
x1 ;y1 and f u
x2 ;y2 we can assume that the functions (f z
are both
defined on
The following now holds for all elements respectively, P(C x1 ;y1 ),
(f z
Case 4. u)g.
Then in fact
since by assumption of the lemma the variable z differs from each of the variables
u. Thus the functions f z
x;y and f u
x;y commute since their schemes are disjoint.
This concludes the proof. 2
Consider now a normalized CSP P with a linear ordering OE on its variables and the
corresponding CSP P OE . To be able to apply the above lemma we order in an appropriate
way the f t
r;s functions, where the variables s; t are such that r OE s OE t. Namely, we
put f z
x1 ;y1 before f u
More precisely, let x xn be the sequence of the variables of P OE , that is x 1 OE
the list Lm consist of the functions f xm
for
some x i and x j . We order each list Lm arbitrarily and consider the list L resulting from
appending in that order. Then by virtue of the Semi-commutativity
Lemma 9 if the function f precedes the function g in the list L, then f semi-commutes
with g w.r.t. the componentwise ordering '.
We instantiate now the refinement of the SI algorithm for the compound domains
by the above-defined list L and each ? i equal to the constraint C i . We assume that
L has k elements. This yields the DIRECTIONAL PATH CONSISTENCY ALGORITHM
(DPATH) that, apart from of the different choice of the constituent partial orderings,
is identical to the DIRECTIONAL ARC CONSISTENCY ALGORITHM DARC of the previous
section. Consequently, the DPATH algorithm enjoys analogous properties as the
DARC algorithm. They are summarized in the following theorem.
Theorem 6 (DPATH Algorithm). Consider a CSP P with a linear ordering OE on its
variables. Let P OE := hC
The DPATH algorithm always terminates. Let P 0 := hC 0
where the
sequence of the constraints C 0
k is computed in d. Then
is the v c -least CSP in fP that is directionally path consistent
w.r.t. OE,
is equivalent to P . 2
As in the case of the DARC Algorithm Theorem 5 we do not need to assume here
that each domain is finite.
Assume now that that x is the sequence of the variables of P OE . Denote the
unique constraint of P OE on x
The above DPATH algorithm can then be rewritten as the following algorithm known
as the DPC algorithm of Dechter and Pearl [7]:
for m := n to 3 by \Gamma1 do
for
for
od
od
od
Conclusions
In this article we introduced a general framework for constraint propagation. It allowed
us to present and explain various constraint propagation algorithms in a uniform way.
We noted already in Apt [1] that using such a single framework we can easier automatically
derive, verify and compare these algorithms. In the meantime the work of Monfroy
and R-ety [14] showed that this framework also allows us to parallelize constraint propagation
algorithms in a simple and uniform way. Additionally, as already noted to large
extent in Benhamou [3], such a general framework facilitates the combination of these
algorithms, a property often referred to as "solver cooperation".
By starting here the presentation with generic iteration algorithms on arbitrary partial
orders we clarified the role played in the constraint propagation algorithms by the
notions of commutativity and semi-commutativity. This in turn allowed us to provide
rigorous and uniform correctness proofs of the AC-3, PC-2, DAC and DPC algorithms.
In turn, by focusing on constraint propagation algorithms that always terminate we
could dispense with the notion of fairness considered in Apt [1].
The line of research presented here could be extended in a number of ways. First, it
would be interesting to find examples of existing constraint propagation algorithms that
could be improved by using the notions of commutativity and semi-commutativity.
Second, as already stated in Apt [1], it would be useful to explain in a similar way
other constraint propagation algorithms such as the AC-4 algorithm of Mohr and Henderson
[12], the AC-5 algorithm of Van Hentenryck, Deville and Teng [18], the PC-4
algorithm of Han and Lee [9], or the GAC-4 algorithm of Mohr and Masini [13]. The
complication is that these algorithms operate on some extension of the original CSP.
In fact, recently, Rosella Gennari (private communication) used the framework of this
paper to explain the AC-4 and AC-5 algorithms.
Finally, it would be useful to apply the approach of this paper to derive constraint
propagation algorithms for the semiring-based constraint satisfaction framework of
Bistarelli, Montanari and Rossi [5] that provides a unified model for several classes
of "nonstandard" constraints satisfaction problems.

Acknowledgements

Victor Dalmau and Rosella Gennari pointed out to us that in Apt [2] Assumptions A
and B on page 4 are not sufficient to establish Theorem 1. The added now Assumption
C was suggested to us by Rosella Gennari.



--R

The essence of constraint propagation.
the rough guide to constraint propagation.
Heterogeneous constraint solving.
Applying interval arithmetic to real

Bucket elimination: A unifying framework for structure-driven inference

Local and global relational consistency.
Comments on Mohr and Henderson's path consistency algorithm.
Consistency in networks of relations.
Programming with Constraints.
Artificial Intelligence
Good old discrete relaxation.
Chaotic iteration for distributed constraint propagation.
Networks of constraints: Fundamental properties and applications to picture processing.
Semantic foundations of concurrent constraint programming.
Data types in subdefinite models.
A generic arc-consistency algorithm and its specializations
--TR
Arc and path consistence revisited
Network-based heuristics for constraint-satisfaction problems
Comments on Mohr and Henderson''s path consistency algorithm
An optimal <italic>k</>-consistency algorithm
The semantic foundations of concurrent constraint programming
A generic arc-consistency algorithm and its specializations
Local and global relational consistency
Semiring-based constraint satisfaction and optimization
Chaotic iteration for distributed constraint propagation
Using MYAMPERSANDldquo;weakerMYAMPERSANDrdquo; functions for constraint propagation over real numbers
The essence of constraint propagation
Bucket elimination
A coordination-based chaotic iteration algorithm for constraint propagation
The Rough Guide to Constraint Propagation
Constraint Propagation for Soft Constraints
Arc Consistency Algorithms via Iterations of Subsumed Functions
Heterogeneous Constraint Solving
Data Types in Subdefinite Models

--CTR
Laurent Granvilliers , Frdric Benhamou, Algorithm 852: RealPaver: an interval solver using constraint satisfaction techniques, ACM Transactions on Mathematical Software (TOMS), v.32 n.1, p.138-156, March 2006
Monfroy , Carlos Castro, Basic components for constraint solver cooperations, Proceedings of the ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
Zhendong Su , David Wagner, A class of polynomially solvable range constraints for interval analysis without widenings, Theoretical Computer Science, v.345 n.1, p.122-138, 21 November 2005
S. Bistarelli , R. Gennari , F. Rossi, General Properties and Termination Conditions for Soft Constraint Propagation, Constraints, v.8 n.1, p.79-97, January
Krzysztof R. Apt , Sebastian Brand, Schedulers for rule-based constraint programming, Proceedings of the ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
Sebastian Brand , Krzysztof R. Apt, Schedulers and redundancy for a class of constraint propagation rules, Theory and Practice of Logic Programming, v.5 n.4-5, p.441-465, July 2005
Antonio J. Fernndez , Patricia M. Hill, An interval constraint system for lattice domains, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.1, p.1-46, January 2004
constraint propagation;generic algorithms;commutativity