Constraint programming viewed as rule-based programming.
We study here a natural situation when constraint programming can be entirely reduced to rule-based programming. To this end we explain first how one can compute on constraint satisfaction problems using rules represented by simple first-order formulas. Then we consider constraint satisfaction problems that are based on predefined, explicitly given constraints. To solve them we first derive rules from these explicitly given constraints and limit the computation process to a repeated application of these rules, combined with labeling. We consider two types of rule here. The first type, that we call equality rules, leads to a new notion of local consistency, called rule consistency that turns out to be weaker than arc consistency for constraints of arbitrary arity (called hyper-arc consistency in Marriott & Stuckey (1998)). For Boolean constraints rule consistency coincides with the closure under the well-known propagation rules for Boolean constraints. The second type of rules, that we call membership rules, yields a rule-based characterization of arc consistency. To show feasibility of this rule-based approach to constraint programming, we show how both types of rules can be automatically generated, as CHR rules of Frhwirth (1995). This yields an implementation of this approach to programming by means of constraint logic programming. We illustrate the usefulness of this approach to constraint programming by discussing various examples, including Boolean constraints, two typical examples of many valued logics, constraints dealing with Waltz's language for describing polyhedral scenes, and Allen's qualitative approach to temporal logic.
Introduction
1.1 Background
This paper is concerned with two styles of programming: constraint programming
and rule-based programming.
In constraint programming the programming process is limited to a generation
Krzysztof R. Apt and Eric Monfroy
of constraints and a solution of the so obtained constraint satisfaction problems
(CSP's) by general or domain dependent methods.
In rule-based programming the programming process consists of a repeated application
of rules. A theoretical basis for this programming paradigm consists of
so-called production rules that were introduced in the seventies, see, e.g., (Luger
1998)[pages 171-186], though the idea goes back to the works of
A. Thue and of E. Post in first half of twentieth century. The production rules
are condition-action pairs, where the condition part is used to determine whether
the rule is applicable and the action part defines the action to be taken. The most
known programming language built around this programming paradigm was OPS5
of (Forgy, 1981).
Recently, there has been a revival of interest in rule-based programming in the
context of constraint programming. The earliest example is the CHR language of
(Fr-uhwirth, 1995) that is a part of the ECL i PS e system. (For a more recent and
more complete overview of CHR see (Fr-uhwirth, 1998).) The CHR rules extend the
syntax of constraint logic programming by allowing two atoms in the conclusion and
employing guards. These rules are predominantly used to write constraint solvers.
Another example of a programming language in which rules play an important
role is ELAN. It offers a logical environment for specifying and prototyping deduction
systems by means of conditional rewrite rules controlled by strategies. ELAN
is used to support the design of various rule-based algorithms such as constraints
solvers, decision procedures, theorem provers, and algorithms expressed in logic
programming languages, and to provide a modular framework for studying their
combinations. A general overview of ELAN can be found in (Borovansky et al.,
1998), whereas (Kirchner & Ringeissen, 1998) and (Castro, 1998) (to which we
shall return in Section 8) describe applications of ELAN to constraint programming
and constraint solving.
Also, in the hybrid functional and object-oriented language programming language
CLAIRE of (Caseau & Laburthe, 1996) rules are present. CLAIRE was designed
to apply constraint programming techniques for operations research prob-
lems. The rule-based programming is supported by means of production rules that
can be naturally used to express constraint propagation.
1.2 Overview of Our Approach
The traditional way of solving CSP's consists of combining constraint propagation
techniques with search. Constraint propagation aims at reducing a CSP to an
equivalent one but simpler. In case of finite domains the most basic approach to
search consists of labeling, a repeated enumeration of the domains of the successive
variables.
The aim of this paper is to show that in some natural circumstances constraint
programming can be entirely rendered by means of rule-based programming. In
this approach the constraint propagation is achieved by repeated application of the
rules while search is limited to labeling.
To this end we study CSP's that are built out of predefined, explicitly given
Constraint Programming viewed as Rule-based Programming 3
finite constraints. Such CSP's often arise in practice. Examples include Boolean
constraints, constraints dealing with Waltz's language for describing polyhedral
scenes, Allen's temporal logic, and constraints in any multi-valued logic.
To solve such CSP's we explore the structure of these explicitly given constraints
first. This information is expressed in terms of valid rules. The computation process
for a CSP built out of these constraints is then entirely driven by these rules. So
in this approach the computation process consists of two phases: a generation of
the rules from the explicitly given constraints and a repeated application of these
rules, combined with labeling.
In our approach the rules are simple first-order formulas to which we provide a
computational interpretation. So in our framework rule-based programming is in
fact logic-based. The rules we shall consider are implications built out of simple
atomic formulas. More precisely, we study two types of rules generated from the
given in advance constraints. The first type of rules, that we call equality rules, are
of the form
are variables and s are elements of the respective do-
mains. The computational interpretation of such a rule is:
if for i 2 [1::n] the domain of the variable x i
equals the singleton fs i g, then remove the
element t from the domain of y.
The second type of rules, that we call membership rules, are of the form
are variables and S are subsets of the respective do-
mains. The computational interpretation of such a rule is:
if for i 2 [1::n] the domain of the variable x i
is included in the set S i
, then remove the
element t from the domain of y.
To characterize the effect of these rules we use the notions of local consistency.
These notions approximate in a loose sense the notion of "global consistency", see,
e.g., (Tsang, 1993). We show that the first type of rules leads to a local consistency
notion that turns out to be weaker than arc consistency for constraints of arbitrary
arity. We call it rule consistency.
When the original domains are all unary or binary, rule consistency coincides
with arc consistency. When additionally the predefined constraints are the truth
tables of the Boolean connectives, these rules essentially coincide with the well-known
Boolean propagation rules, (see, e.g., (Codognet & Diaz, 1996)). As a side
effect, this shows that the Boolean propagation rules characterize arc consistency.
Rule consistency is thus a generalization of the Boolean propagation to non-binary
domains.
We also show that the membership rules lead to a notion of local consistency
that coincides with arc consistency. This yields a rule-based implementation of arc
consistency.
To show feasability of this rule-based approach to constraint programming, we
4 Krzysztof R. Apt and Eric Monfroy
automatically generate both types of rules, for an explicitly given finite constraint,
as rules in the CHR language. When combined with a labeling procedure such CHR
programs constitute automatically derived decision procedures for the considered
CSP's, expressed on the constraint programming language level. In particular, we
automatically generate the algorithms that enforce rule consistency and arc consistency

The availability of the algorithms that enforce rule consistency and arc consistency
on the constraint programming language level further contributes to the
automation of the programming process within the constraint programming frame-
work. In fact, in the case of such CSP's built out of predefined, explicitly given finite
constraints, the user does not need to write one's own CHR rules for the considered
constraints and can simply adopt all or some of the rules that are automatically
generated. In the final example of the paper we also show how using the equality
rules and the membership rules, we can implement more powerful notions of local
consistency.
Alternatively, the generated equality rules and membership rules could be fed into
any of the generic Chaotic Iteration algorithms of (Apt, 1999) and made available
in such systems as the ILOG solver. This would yield rule consistency and an
alternative implementation of arc consistency.
The algorithms that for an explicitly given finite constraint generate the appropriate
rules that characterize rule consistency and arc consistency have (unavoid-
ably) a running time that is exponential in the number of constraint variables and
consequently are in general impractical.
To test the usefulness of these algorithms for small finite domains we implemented
them in ECL i PS e and successfully used them on several examples including the ones
mentioned above. The fact that we could handle these examples shows that this
approach is of practical value and in particular can be used to automatically derive
practical decision procedures for constraint satisfaction problems defined over small
finite domains. Also it shows the usefulness of the CHR language for an automatic
generation of constraint solvers and of decision procedures.
1.3 Organization of the Paper
The rest of the paper is organized as follows. In the next section we clarify the
syntax of the rules and explain how one can compute with them. Then, in Section
3 we formalize the concept of a CSP is built out of predefined constraints. Next, in
Section 4 we introduce the notion of rule consistency and discuss an algorithm that
can be used to generate the minimal set of rules that characterize this notion of local
consistency. Then, in Section 5 we compare rule consistency with arc consistency.
In Section 6 we study membership rules and discuss an algorithm analogous to the
one of Section 4. This entails a notion of local consistency that turns out to be
equivalent to arc consistency.
In Section 7 we discuss the implementation of both algorithms. They generate
from an explicit representation of a finite constraint a set of CHR rules that
characterize respectively rule consistency and arc consistency. We also illustrate
Constraint Programming viewed as Rule-based Programming 5
the usefulness of these implementations by means of several examples. Finally, in
Section 8 we discuss other works in which a link was made between constraint programming
and rule-based programming and in Section 9 we assess the merits of
our approach. In the appendix we summarize the tests carried out by means of our
implementation of both algorithms.
Computing with Rules
In what follows we introduce specific type of rules and explain how one can compute
with them on constraint satisfaction problems. First, we introduce constraints.
Consider a sequence of variables X := x respective
domains associated with them. So each variable x i ranges over the domain
. By a constraint C on X we mean a subset of D 1 . Given an
element d := d Dn and a subsequence Y := x
of X
we denote by d[Y ] the sequence d i 1
. In particular, for a variable x i from X ,
Next, we define the rules we are interested in.
Definition 2.1
ffl Let x be a variable, a an element and S a set. By an atomic formula we mean
one of the following formulas:
ffl By a rule we mean an expression of the form A
each A i and B j is an atomic formula. 2
In what follows a rule will be always associated with some constraint. Then every
atomic will be such that a belongs to
the domain of x (respectively, S is a subset of the domain of x).
Subsequently, we explain how to compute using the rules in presence of con-
straints. First, we limit our considerations to the rules of the form A! x 6= a. We
need to explain how to turn the disequality formula into an action. This is done
by identifying the disequality x 6= a with the assignment D x := D x \Gamma fag, where
D x is the current domain of x. In other words, we interpret x 6= a as an action of
removing the value a from the current domain of the variable x.
This leads us to the definition of an application of such a rule. We need some
semantic notions first.
Definition 2.2
Consider a constraint C on a sequence of variables X , a variable x of X , and a
tuple d 2 C.
ffl Given an atomic formula A involving x we define the relation
ffl Given a sequence of atomic formulas A := A
6 Krzysztof R. Apt and Eric Monfroy
Definition 2.3
Consider a constraint C on a finite sequence of variables X and a rule of the form
involving only variables from X .
Suppose that for all d 2 C we have A. Let C 0 be the constraint obtained
from C by removing the element a from the domain D i of the variable x i and by
removing from C all tuples d such that d[x i a. Then we call the constraint C 0
the result of applying the rule A! x i 6= a to C.
If a 2 D i , then we say that this is a relevant application of the rule A! x i 6= a
to C. If C 0 coincides with C, we say that this application of the rule A! x i 6= a
to C maintains equivalence. 2
So the application of the rule A! x i 6= a to a constraint C on the sequence
of variables with respective domains D results in the constraint
C 0 on the variables x respective domains D
where
i \Theta D
We say then that the constraint C is restricted to the domains D
Now that we defined the result of a single application of a rule we proceed to
define computations. To this end we first introduce constraint satisfaction problems.
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
By a solution to we mean an element d 2 D
such that for each constraint C 2 C on a sequence of variables X we have d[X
We call a CSP consistent if it has a solution. Two CSP's with the same sequence
of variables are called equivalent if they have the same set of solutions.
We now modify the definition of an application of a rule to a constraint to an
application of a rule to a CSP. To this end we attach each rule to a constraint
to which it is supposed to be applied. Even though the constraints change during
the computations we consider, it will be always clear from the context to which
constraint a given rule is attached.
Definition 2.4
Consider a CSP P and a rule A! x i 6= a attached to a constraint C of P . Suppose
that for all d 2 C we have A. Define a CSP P 0 on the same variables as P as
follows:
ffl the domain of x i in P 0 equals is the domain of x in P ,
ffl the domains of other variables in P 0 are the same as in P ,
ffl the constraints of P 0 are obtained by restricting the constraints of P to the
new domains.
Constraint Programming viewed as Rule-based Programming 7
We say then that the CSP P 0 is the result of applying the rule A! x i 6= a to P .
If a 2 D i , then we say that this is a relevant application of the rule A! x i 6= a to
Finally, we introduce the crucial notion of a computation.
Definition 2.5
Consider a set of rules R of the form A! x 6= a and an initial CSP P . By a
computation by means of R starting at P we mean a maximal sequence of CSP's
such that each P j+1 is the result of a relevant application of a rule
from R to P j . 2
So the computations can be finite or infinite. When all domains in P are finite,
so are the computations starting at P because we insist that each application is
relevant. If a computation is finite, then no application of a rule from the considered
set of rules R to the final CSP is relevant.
The computations here considered are in general insufficient for solving a CSP
and in the case of CSP's with finite domains they have to be combined with label-
ing. Labeling can be easily incorporated into the above rule-based framework by
introducing a rule that splits a given CSP into two, the union of which is equivalent
to the given CSP. The addition of such a rule to the considered framework leads to
no conceptual difficulties and is omitted.
The above string of definitions allowed us to define computations in which the
actions are limited to the applications of rules of the form A! x 6= a acting on
CSP's.
By limiting our attention to such type of rules we do not lose any expressiveness.
Indeed, consider first a rule of the form A! To compute with it we interpret
the equality x = a as the assignment D x := D x " fag, where D x is the current
domain of x. Then each rule A! x = a is equivalent to the conjunction of the
rules of the form A! x 6= b with b 2 D \Gamma fag, where D is the original domain of
x.
Next, consider a rule of the form A! x 2 S. To compute with it we interpret
the atomic formula x 2 S as the assignment D x := D x " S, where D x is the current
domain of x. Then each rule A! x 2 S is equivalent to the conjunction of the
rules of the form A! x 6= b with b 2 D \Gamma S, where D is the original domain of x.
Finally, each rule of the form A! is equivalent to the conjunction of
the rules of the form A!B i for
Note that the rules of the form x are more expressive
than so-called dependency rules of database systems (see, e.g., (Ullman, 1988)).
These are rules of the form x just explained how
to model them by means of rules of the form x
However, modeling in the other direction is not possible, as can be seen by taking
the variables x; y, each with the domain f0; 1; 2g, and the constraint C on x; y
represented by the following table:
8 Krzysztof R. Apt and Eric Monfroy
x y
Then the rule not equivalent to a conjunction of the dependency
rules.
We now introduce a number of semantic notions concerning rules.
Definition 2.6
Consider a constraint C.
ffl We say that the rule A!B is valid for C if for all tuples d 2 C
implies
ffl We say that the constraint C is closed under the rule A!B if
(j= d A for all tuples d 2 C) implies (j= d B for all tuples d 2 C):
ffl We say that the rule A!B is feasible for C if for some tuple d 2 C we have
A.
ffl We say that the rule A!B for the constraint C extends the rule A 0 !B if
A contains all variables of A 0 and for all tuples d 2 C
implies
ffl Given a set of rules R, we call a rule minimal in R if it is feasible and it does
not properly extend a valid rule in R. 2
Note now that the definition of an application of a rule is so designed that a link
with semantics is kept in the following sense: if a rule r is valid for a constraint C,
then C is closed under r. Rules that are not feasible are trivially valid. Note also
that a rule that extends a valid rule is valid, as well. So validity extends "upwards".
In what follows we confine our attention to computations involving two types of
rules:
ffl equality rules : these are rules of the form x
abbreviate them to
ffl membership rules : these are rules of the form x 1
we abbreviate them to X
By specializing R to the set of equality rules and to the set of membership rules
we obtain the notions of a minimal equality rule and of a minimal membership rule.
To illustrate the introduced notions consider the following example, where we
confine our attention to equality rules.
Constraint Programming viewed as Rule-based Programming 9
Example 2.1
Take as a constraint the ternary relation that represents the conjunction and(x;
It can be viewed as the following table:
x y z
In other words, we assume that each of the variables x; y; z has the domain f0; 1g
and view and(x; as the constraint on x; z that consists of the above four
triples.
It is easy to see that the equality rule
Further, the rule extends the rule and is also
valid for and(x; However, out of these two equality rules only
is minimal.
Finally, both rules are feasible, while the rules
are not feasible. 2
Note the use of the condition "A contains all variables of A 0 " in the definition
of the relation "the rule A!B extends the rule A 0 !B". Without it we would
have the following paradoxical situation. Consider the variables x; y; z, all on the
domains f0; 1g, and the constraint C on x; defined by C := f(0; 0; 0); (1; 0; 1)g.
Then the rules are both valid for C and for all
we have that without the mentioned condition
we would have that the rule extends the rule
would imply that the first rule is not minimal.
In the sequel the following observation will be useful.
Note 2.1
Consider two finite and non-empty constraints C and E such that C 'E and a set
of rules R. Then C is closed under all valid rules from R for E iff it is closed under
all minimal valid rules in R for E.
Proof
Suppose that C is closed under all minimal valid rules in R for E. Take a rule r
from R that is valid for E.
Case 1. r is feasible for E.
Then, because E is finite, r extends some minimal valid rule r 0 in R for E. But
C is closed under r 0 , so it is closed under r, as well.
Case 2. r is not feasible for E.
Then r is not feasible for C either since C 'E. Consequently, since C is non-
empty, C is closed under r.
Krzysztof R. Apt and Eric Monfroy
Given a CSP with finite domains we would like to solve it by considering computations
starting at it. But where do we get the rules from? Note that given a
constraint C and a rule r that is valid for C, the constraint C is trivially closed
under r. Consequently, an application of r to C is not relevant, i.e., it does not
affect C. So to obtain some change we need to use rules that are not valid for the
initial constraints. This brings us to the notion of a CSP based on another one.
3 CSP's Built out of Predefined Constraints
In the introduction we informally referred to the notion of a CSP "being built out
of predefined, explicitly given constraints." Let us make now this concept formal.
We need two auxiliary notions first, where in preparation for the next definition we
already consider constraints together with the domains over which they are defined.
Definition 3.1
ffl Given a constraint C 'D 1 Dn and a permutation - of [1::n] we denote
by C - the relation defined by
an
and call it a permutation of C.
ffl Given two constraints C 'D 1
n we say that
C is based on E if
So the notion of "being based on" involves the domains of both constraints. If C is
based on E, then C is the restriction of E to the domains over which C is defined.
Definition 3.2
We assume that the "predefined constraints" are presented as a given in advance
CSP BASE . Suppose that each constraint C of a CSP P is based on a permutation
of a constraint of BASE . We say then that P is based on BASE . 2
In the above definition the use of permutations of constraints allows us to abstract
from the variable ordering used in BASE . The following example illustrates this
notion.
Example 3.1
Consider the well-known full adder circuit. It is defined by the following formula:
where and; xor and or are defined in the expected way. We can view the original
constraints as the following CSP:
BOOL should be viewed just as an "inventory" of the predefined constraints and
Constraint Programming viewed as Rule-based Programming 11
not as a CSP to be solved. Now, any query concerning the full adder can be viewed
as a CSP based on BOOL. For example, in Section 7 we shall consider the query
It corresponds to the following CSP based on BOOL:
i.In what follows we consider computations that start with a CSP based on some
CSP BASE . In these computations we wish to maintain equivalence between the
successive CSP's. To this end the following simple observation is crucial.
Note 3.1
Consider two constraints C and E such that C is based on E. Let A! x 6= a be a
rule valid for E. Then the application of A! x 6= a to C maintains equivalence.
Proof
Assume that the rule A! x 6= a can be applied to C, i.e., that for all d 2 C we have
A. Suppose now that the rule A! x 6= a to C does not maintain equivalence.
Then for some d 2 C we have a. C is based on E, so d 2 E. By the validity
of the rule for E we get d[x] 6= a. This yields a contradiction.
This observation provides us with a way of maintaining equivalence during a
computation: it suffices to use at each step a rule that is valid for a permutation
C - of a constraint of BASE . Such a rule is then attached (i.e., applied) to the
constraint based on C - . This is what we shall do in the sequel. Depending on the
type of rules used we obtain in this way different notions of local consistency.
4 Rule Consistency
In this section we consider a CSP P based on some finite CSP BASE and study
computations that use exclusively equality rules. The rules are obtained from the
constraints of BASE ; each of them is valid for a permutation C - of a constraint
C of BASE and is applied to the constraint of P based on C - . By Note 3.1 the
successive CSP's are all equivalent to the initial CSP P . The computation ends
when a CSP is obtained that is closed under the rules used. This brings us to a
natural notion of local consistency expressed in terms of equality rules.
Definition 4.1
Consider a CSP P based on a CSP BASE . Let C be a constraint of P . For some
constraint f(C) of BASE and a permutation -, C is based on f(C) - .
ffl We call the constraint C rule consistent (w.r.t. BASE) if it is closed under
all equality rules that are valid for f(C) - .
ffl We call the CSP P rule consistent (w.r.t. BASE) if all its constraints are rule
consistent. 2
In what follows we drop the reference to BASE if it is clear from the context.
12 Krzysztof R. Apt and Eric Monfroy
Example 4.1
Take as the base CSP
and consider the following four CSP's based on it:
1. hand(x;
2. hand(x;
3. hand(x;
4. hand(x;
where D y is a subset of f0; 1g. We noted in Example 2.1 that the equality rule
z). In the first three CSP's its only constraint is
closed under this rule, while in the fourth one not since 1 is present in the domain
of z whereas the domain of x equals f0g. So the fourth CSP is not rule consistent.
One can show that the first two CSP's are rule consistent, while the third one is
not since it is not closed under the valid equality rule
When trying to generate all valid equality rules Note 2.1 allows us to confine our
attention to the minimal valid equality rules. We now introduce an algorithm that
given a finite constraint generates the set of all minimal valid equality rules for it.
We collect the generated rules in a list. We denote below the empty list by empty
and the result of insertion of an element r into a list L by insert(r; L).
By an assignment to a sequence of variables X we mean here an element s from
the Cartesian product of the domains of variables of X such that for some d 2 C
we have d[X Intuitively, if we represent the constraint C as a table with rows
corresponding to the elements (tuples) of C and the columns corresponding to the
variables of C, then an assignment to X is a tuple of elements that appears in some
row in the columns that correspond to the variables of X . This algorithm has the
following form, where we assume that the considered constraint C is defined on a
sequence of variables VAR of cardinality n.
Equality Rules Generation algorithm
FOR each subset X of VAR of cardinality i DO
FOR each assignment s to X DO
FOR each y in VAR-X DO
FOR each element d from the domain of y DO
IF r is valid for C
and it does not extend an element of L
THEN insert(r, L)
END
END
END
END
Constraint Programming viewed as Rule-based Programming 13
END
END
The following result establishes correctness of this algorithm.
Theorem 4.1
Given a constraint C the Equality Rules Generation algorithm produces in L
the set of all minimal valid equality rules for C.
Proof
First note that in the algorithm all possible feasible equality rules are considered
and in the list L only the valid equality rules are retained. Additionally, a valid
equality rule is retained only if it does not extend a rule already present in L.
Because the equality rules are considered in the order according to which those
that use less variables are considered first, this ensures that precisely all minimal
valid equality rules are retained in L.
Note that because of the minimality property no rule in L extends another. It is easy
to see that in this algorithm, given a constraint defined over n variables, O(2 n d n )
rules are considered, where d is the size of the largest variable domain. This shows
that in practice this algorithm is impractical for large domains and for constraints
with many variables. We shall return to this matter in Section 7 and the appendix.
Relating Rule Consistency to Arc Consistency
To clarify the status of rule consistency we compare it now to the notion of arc
consistency. This notion was introduced in (Mackworth, 1977) for binary relations
and was extended to arbitrary relations in (Mohr & Masini, 1988). Let us recall the
definition.
Definition 5.1
ffl We call a constraint C on a sequence of variables X arc consistent if for every
variable x in X and an element a in its domain there exists d 2 C such that
That is, each element in each domain participates in a solution to
C.
ffl We call a CSP arc consistent if all its constraints are arc consistent. 2
The following result relates for constraints of arbitrary arity arc consistency to
rule consistency.
Theorem 5.1
Consider a CSP P based on a CSP BASE . If P is arc consistent, then it is rule
consistent w.r.t. BASE .
Proof
Assume that P is arc consistent. Choose a constraint C of P and consider an
equality rule a that is valid for f(C) - , where f and - are as in
Definition 4.1.
Suppose by contradiction that C is not closed under this rule. So for X :=
14 Krzysztof R. Apt and Eric Monfroy
the domain of each variable x j in P equals fs j g and
moreover a 2 D, where D is the domain of the variable y in P .
By the arc consistency of P there exists d 2 C such that a. Because of
the form of the domains of the variables in X , also d[X holds. Additionally,
because P is based on BASE , we have d 2 f(C) - . But by assumption the equality
rule a is valid for f(C) - , so d[y] 6= a. A contradiction.
The converse implication does not hold in general as the following example shows.
Example 5.1
Take as the base the following CSP
where the constraint C on x; y that equals the set f(0; 1); (1; 0); (2; 2)g. So C can
be viewed as the following table:
x y
Next, take for D 1 the set f0; 1g and D 2 the set f0; 1; 2g. Then the CSP hC "
(D 1 \Theta D 2 based
on BASE but is not arc consistent since the value 2 in the domain of y does not
participate in any solution. Yet, it is easy to show that the only constraint of this
CSP is closed under all equality rules that are valid for C. 2
We now show that if each domain has at most two elements, then the notions of
arc consistency and rule consistency coincide. More precisely, the following result
holds.
Theorem 5.2
Let BASE be a CSP each domain of which is unary or binary. Consider a CSP P
based on BASE . Then P is arc consistent iff it is rule consistent w.r.t. BASE .
Proof
The implication is the contents of Theorem 5.1.
To prove the reverse implication suppose that some constraint C of P is not arc
consistent. We prove that then C is not rule consistent.
The constraint C is on some variables x respective domains D
For some i 2 [1::n] some a 2 D i does not participate in any solution to C.
be the sequence of all domains in D
are singletons. Suppose that D i j
and
Consider now the equality rule a and take f(C) - , where f and
Constraint Programming viewed as Rule-based Programming 15
- are as in Definition 4.1. For appropriate domains D 0
n of BASE we have
n .
Next, take some d 2 f(C) - such that d[X We show that d 2 C. Since
suffices to prove that d 2 D 1 . For each
variable x j lying inside of X we have d[x In turn, for each variable
lying outside of X its domain D j has two elements, so, by the assumption on
BASE , D j is the same as the corresponding domain D 0
j of f(C) - and consequently
n .
indeed d 2 C and hence d[x i ] 6= a by the choice of a. This proves validity of
the equality rule
But C is not closed under this rule since a 2 D i , so C is not rule consistent.
6 Membership Rule Consistency
In this section we consider computations that use exclusively membership rules. In
the previous section we saw that the notion of rule consistency is weaker than that
of arc consistency for constraints of arbitrary arity. Here we show that by using the
membership rules we obtain a notion of local consistency that coincides with arc
consistency.
First, let us clarify the notion of a membership rule by considering the following
example.
Example 6.1
Consider a constraint on variables x; y; z, each with the domain f+; \Gamma; l; rg, that is
defined by the following table:
x y z
This constraint is the so-called fork junction in the language of (Waltz, 1975) for
describing polyhedral scenes. Note that the following three membership rules
and
are all valid. The membership rules r 2 and r 3 extend r 1 while the membership
rule r 1 extends neither r 2 nor r 1 . Further, the membership rules r 2 and r 3 are
incomparable in the sense that none extends the other. 2
Krzysztof R. Apt and Eric Monfroy
Now, in analogy to Definition 4.1, we introduce the following notion.
Definition 6.1
Consider a CSP P is based on a CSP BASE . Let C be a constraint of P . For some
constraint f(C) of BASE and a permutation -, C is based on f(C) - .
ffl We call the constraint C membership rule consistent (w.r.t. BASE) if it is
closed under all membership rules that are valid for f(C) - .
ffl We call a CSP membership rule consistent (w.r.t. BASE) if all its constraints
are membership rule consistent. 2
We now have the following result.
Theorem 6.1
Consider a CSP P based on a CSP BASE . Then P is arc consistent iff it is membership
rule consistent w.r.t. BASE .
Proof
This part of the proof is a simple modification of the proof of Theorem 5.1.
Assume that P is arc consistent. Choose a constraint C of P and consider a
membership rule X a that is valid for f(C) - , where f and - are as in
Definition 3.2.
Suppose by contradiction that C is not closed under this rule. So for X :=
the domain of each variable x j is included in S j and
moreover a 2 D, where D is the domain of the variable y.
By the arc consistency of P there exists d 2 C such that a. Because of
the form of the domains of the variables in X , also d[x i holds.
Additionally, because P is based on BASE we have d 2 f(C) - . But by assumption
the rule X a is valid for f(C) - , so d[y] 6= a. A contradiction.
This part of the proof is a modification of the proof of Theorem 5.2.
Suppose that some constraint C of P is not arc consistent. We prove that then C
is not membership rule consistent. The constraint C is on some variables x
with respective domains D . For some i 2 [1::n] some a 2 D i does not
participate in any solution to C.
Take are as in Definition 6.1. For appropriate domains
n of BASE we have f(C) - 'D 0
n .
be the sequence of domains in D
are respectively different than D 0
Consider now the membership rule X
that d[x i j
We show that d 2 C. Since
suffices to prove that d 2 D 1 . For each variable x j lying
inside of X we have d[x j In turn, for each variable x j lying outside of X
its domain D j is the same as the corresponding domain D 0
j of f(C) - in BASE and
consequently
n .
indeed d 2 C and hence d[x i ] 6= a by the choice of a. This proves validity of
the rule X But C is not closed under this membership
rule since a 2 D i , so C is not membership rule consistent.
Constraint Programming viewed as Rule-based Programming 17
Example 5.1 shows that the notions of rule consistency and membership rule
consistency do not coincide. To see this difference better let us reconsider the CSP
discussed in this example.
We noted there that this CSP is not arc consistent and that it is rule consistent.
From the above theorem we know that this CSP is not membership rule consistent.
In fact, consider the following membership rule:
2:
This membership rule is valid for the base constraint C but the restricted constraint
not closed under this rule. In conclusion, the membership
rules are more powerful than the equality rules.
As in Section 4 we now provide an algorithm that given a constraint generates
the set of all minimal valid membership rules. We assume here that the considered
constraint C is defined on a sequence of variables VAR of cardinality n.
Instead of assignments that are used in the Equality Rules Generation
algorithm we now need a slightly different notion. To define it for each variable x
from VAR we denote the set fd[x] j d 2 Cg by C[x]. By a weak assignment to a
sequence of variables X := x here a sequence S of subsets
of, respectively, C[x 1 such that some d 2 C exists such that d[x i
for each i 2 [1::k].
Intuitively, if we represent the constraint C as a table with rows corresponding
to the elements of C and the columns corresponding to the variables of C and we
view each column as a set of elements, then a weak assignment to X is a tuple
of subsets of the columns that correspond to the variables of X that "shares" an
assignment.
In the algorithm below the weak assignments to a fixed sequence of variables are
considered in decreasing order in the sense that if the weak assignments S
and U are such that for i 2 [1::k] we have U i ' S i , then S
first.
Membership Rules Generation algorithm
FOR each subset X of VAR of cardinality i DO
FOR each weak assignment S to X in decreasing order DO
FOR each y in VAR-X DO
FOR each element d from the domain of y DO
IF r is valid for C
and it does not extend an element of L
THEN insert(r, L)
END
END
END
END
Krzysztof R. Apt and Eric Monfroy
END
END
The following result establishes correctness of this algorithm.
Theorem 6.2
Given a constraint C the Membership Rules Generation algorithm produces
in L the set of all minimal valid membership rules for C.
Proof
The proof is analogous to that of Theorem 4.1. We only need to check that the
membership rules are considered in such an order that if a rule r 2 extends a rule
This follows from the following observation. Suppose that the rule r 2 := Z 2
a subsequence of Z and for
each variable x in X the corresponding element of U is a subset of the corresponding
element of S.
Applications
In this section we discuss the implementation of the Equality Rules Generation
and Membership Rules Generation algorithms and discuss their use on
selected domains.
7.1 Constraint Handling Rules (CHR)
In order to validate our approach we have realized in the Prolog platform ECL i PS e
a prototype implementation of both the Rules Generation algorithm and the
Membership Rules Generation algorithm. We made a compromise between
memory usage and performance so that we could tackle some non-trivial problems
(in terms of size of the domains of variables, and in terms of arity of constraints)
in spite of the exponential complexity of the algorithms. These implementations
generate CHR rules that deal with finite domain variables using an ECL i PS e library.
Constraint Handling Rules (CHR) of (Fr-uhwirth, 1995) is a declarative language
that allows one to write guarded rules for rewriting constraints. These rules are repeatedly
applied until a fixpoint is reached. The rule applications have a precedence
over the usual resolution step of logic programming.
CHR provides two types of rules: simplification rules that replace a constraint by
a simpler one, and propagation rules that add new constraints.
Our equality rules and membership rules can be modelled by means of propagation
rules. To illustrate this point consider some constraint cons on three variables,
each with the domain f0; 1; 2g.
The Rules Generation algorithm generates rules such as
2. This rule is translated into a CHR rule of the form: cons(0,B,1) ==? B#2.
Now, when a constraint in the program query unifies with cons(0,B,1), this rule
is fired and the value 2 is removed from the domain of the variable B.
Constraint Programming viewed as Rule-based Programming 19
In turn, the Membership Rules Generation algorithm generates rules such
as 2. This rule is translated into the CHR rule
where the in predicate is defined by
in(X,L):- dom(X,D), subset(D,L).
holds if the current domain of the variable X (yielded by the built-in
dom of ECL i PS e ) is included in the list L.
Now, when a constraint unifies with cons(0,B,C) and the current domain of the
variable C is included in [1,2], the value 2 is removed from the domain of B. So for
both types of rules we achieve the desired effect.
In the examples below we combine the rules with the same premise into one rule
in an obvious way and present these rules in the CHR syntax.
7.2 Generating the rules
We begin by discussing the generation of equality rules and membership rules for
some selected domains. The times given refer to an implementation ran on a Silicon
Graphics O2 with 64 Mbytes of memory and a 180 MHZ processor.
Boolean constraints As the first example consider the Boolean constraints, for
example the conjunction constraint and(X,Y,Z) of Example 2.1. The Equality
Rules Generation algorithm generated in 0.02 seconds the following six equality
rules:
Because the domains are here binary we can replace the conclusions of the form
These become then the well-known rules
that can be found in (Fr-uhwirth, 1998)[page 113].
In this case, by virtue of Theorem 5.2, the notions of rule and arc consistency
coincide, so the above six equality rules characterize the arc consistency of the and
constraint. Our implementations of the Equality Rules Generation and the
Membership Rules Generation algorithms yield here the same rules.
Three valued logic Next, consider the three valued logic of (Kleene, 1952)[page 334]
that consists of three values, t (true), f (false) and u (unknown). We only consider
here the crucial equivalence relation j defined by the truth table
20 Krzysztof R. Apt and Eric Monfroy
that determines a ternary constraint with nine triples. We obtain for it 20 equality
rules and 26 membership rules. Typical examples are
and
equiv(t,X,Y) ==? in(Y,[f, u]) - X#t.
Six valued logic In (Van Hentenryck et al., 1992) the constraint logic programming
language CHIP is used for the automatic test-pattern generation (ATPG) for the
digital circuits. To this end the authors define a specific six valued logic and provide
some rules (expressed in the form of so-called demons) to carry out the constraint
propagation. The and6 constraint in question is defined by means of the following
table:
d \Gamma\Gamma d \Gamma\Gamma \Gamma\Gamma d \Gamma\Gamma
dnot \Gamma\Gamma dnot \Gamma\Gamma \Gamma\Gamma \Gamma\Gamma dnot
enot 0 enot \Gamma\Gamma dnot 0 enot
The Equality Rules Generation algorithm generated 41 equality rules in
seconds, while the Membership Rules Generation algorithm generated
155 membership rules in 14.35 seconds. It is difficult to compare the outcome of
these two algorithms with the rules given in (Van Hentenryck et al., 1992)[page 133]
because some of the latter ones allow equalities between the variables in the premise.
However, it is clear that our approach is more systematic and fully automatic.
Propagating signs As a next example consider the rules for propagating signs in
arithmetic expressions, see, e.g., (Davis, 1987)[page 303]. We limit ourselves to the
case of multiplication. Consider the following table:
Constraint Programming viewed as Rule-based Programming 21
\Theta neg zero pos unk
neg pos zero neg unk
zero zero zero zero zero
pos neg zero pos unk
unk unk zero unk unk
This table determines a ternary constraint msign that consists of 16 triples, for
instance (neg, neg, pos) that denotes the fact that the multiplication of two negative
numbers yields a positive number. The value "unk" stands for "unknown". The
Equality Rules Generation algorithm generated in 0.08 seconds 34 equality
rules. A typical example is msign(X,zero,Y) ==? Y#pos,Y#neg,Y#unk.
In turn, the Membership Rules Generation algorithm generated in 0.6 seconds
54 membership rules. A typical example is
that corresponds to the following two membership rules for the constraint msign(X,Z,Y):
and
Waltz' language for describing polyhedral scenes Waltz' language consists of four
constraints. One of them, the fork junction was already mentioned in Example 6.1.
The Equality Rules Generation algorithm generated for it 12 equality rules
and the Membership Rules Generation algorithm 24 membership rules.
Another constraint, the so-called T junction, is defined by the following table:
x y z
r l r
r l l
In this case the Equality Rules Generation algorithm and the Membership
Rules Generation algorithm both generate the same output that consists of just
one rule:
So this rule characterizes both rule consistency and arc consistency for the CSP's
based on the T junction.
22 Krzysztof R. Apt and Eric Monfroy
For the other two constraints, the L junction and the arrow junction, the generation
of the equality rules and membership rules is equally straightforward.
7.3 Using the rules
Next, we show by means of some examples how the generated rules can be used to
reduce or to solve specific queries. Also, we show how using compound constraints
we can achieve local consistency notions that are stronger than arc consistency for
constraints of arbitrary arity.
Waltz' language for describing polyhedral scenes The following predicate describes
the impossible scene given in Figure 1 and taken from (Winston, 1992)[page 262]:
F
G
I J
A
Fig. 1. Impossible scene
imp(AF,AI,AB,IJ,IH,JH,GH,GC,GE,EF,ED,CD,CB):-
arrow(AF,AB,AI), l(BC,BA), arrow(CB,CD,CG), l(DE,DC),
arrow(ED,EG,EF), l(FA,FE), fork(GH,GC,GE), arrow(HG,HI,HJ),
line(AF,FA), line(AB,BA), line(AI,IA), line(IJ,JI),
line(IH,HI), line(JH,HJ), line(GH,HG), line(FE,EF),
line(GE,EG), line(GC,CG), line(DC,CD), line(ED,DE),
line(BC,CB).
where the supplementary constraint line is defined by the following table:
Constraint Programming viewed as Rule-based Programming 23
x y
l r
r l
Here and elsewhere we use the ECL i PS e built-in :: to declare variable domains.
When using the equality rules obtained by the Equality Rules Generation
algorithm and associated with the fork, arrow, t, l, and line constraints, the
query
imp(AF,AI,AB,IJ,IH,JH,GH,GC,GE,EF,ED,CD,CB)
reduces in 0.009 seconds the variable domains to AF 2 [+,-, l], AI 2 [+,-], AB
But some constraints remain unsolved, so we need to add a labeling mechanism
to prove the inconsistency of the problem. On the other hand, when using the membership
rules, the inconsistency is detected without any labeling in 0.06 seconds.
In the well-known example of the cube given in Figure 12.15 of (Winston, 1992)[page
260] the membership rules are also more powerful than the equality rules and both
sets of rules reduce the problem but in both cases labeling is needed to produce all
four solutions.
Comparing the constraint solver based on the membership rules to the constraint
solver based on the equality rules is not easy: although propagation is more efficient
with the membership rules, the solver based on the equality rules can sometimes
be faster depending on the structure of the problem and on whether the labeling is
needed.
We also compared the solvers generated by the implementations of the Equality
Rules Generation and Membership Rules Generation algorithms to the
approach described in (By, 1997) and based on meta-programming in Prolog. We
ran the same examples and drew the following conclusions. For small examples
our solvers were less efficient than the ones of By (with factors varying from 2 to
10). However, for more complex examples, our solvers became significantly more
efficient, with factors varying from 10 to 500. This can be attributed to the increased
role of the constraint propagation that reduces backtracking and that is absent in
By's approach.
Temporal reasoning In (Allen, 1983) approach to temporal reasoning the entities
are intervals and the relations are temporal binary relations between them. (Allen,
1983) found that there are 13 possible temporal relations between a pair of events,
Krzysztof R. Apt and Eric Monfroy
namely before, during, overlaps, meets, starts, finishes, the symmetric
relations of these six relations and equal. We denote these 13 relations respectively
by b,d,o,m,s,f,b-,d-,o-,m-,s-,f-,e and their set by TEMP.
Consider now three events, A, B and C and suppose that we know the temporal
relations between the pairs A and B, and B and C. The question is what is the
temporal relation between A and C. To answer it (Allen, 1983) provided a 13 \Theta 13
table. This table determines a ternary constraint between a triple of events, A, B
and C that we denote by allen. For example,
(overlaps; before; before) 2 allen
since A overlaps B and B is before C implies that A is before C.
Using this table, the Equality Rules Generation algorithm produced for the
constraint allen 498 equality rules in 31.16 seconds.
We tried this set of rules to solve the following problem from (Allen, 1983):
"John was not in the room when I touched the switch to turn on the light. We
have here three events: S, the time of touching the switch; L, the time the light was
on; and J, the time that John was in the room. Further, we have two relations:
between L and S, and R2 between S and J. This problem is translated into the CSP
allen is the above
constraint on the variables R1, R2, R3.
To infer the relation R3 between L and J we can use the following query
R1::[o-,m-],
R2::[b,m,b-,m-],
R3::[b,d,o,m,s,f,b-,d-,o-,m-,s-,f-,e],
allen(R1,R2,R3),
labeling([R1,R2,R3]).
We then obtain the following solutions in 0.06 seconds:
(m-,b-,b-), (m-,m,e), (m-,m,s), (m-,m,s-), (m-,m-,b-), (o-,b,b),
(o-,b,d-), (o-,b,f-), (o-,b,m), (o-,b,o), (o-,b-,b-), (o-,m,d-),
(o-,m,f-), (o-,m,o), (o-,m-,b-)g.
To carry on (as in (Allen, 1983)), we now complete the problem
John was in the room later while the light went out. This is translated into: "L
overlaps, starts, or is during J", i.e., R3 2 [o,s,d].
We now run the following query:
R1::[o-,m-],
R2::[b,m,b-,m-],
R3::[o,s,d],
allen(R1,R2,R3),
labeling([R1,R2,R3]).
no variable is instantiated, we need to perform labeling to effectively apply the rules.
Constraint Programming viewed as Rule-based Programming 25
and obtain four solutions in 0.04 seconds: (R1,R2,R3) 2 f(m-,b,o), (m-,m,s),
(o-,b,o), (o-,m,o)g.
Full adder This final example illustrates how we can use the equality rules and the
membership rules to implement more powerful notions of local consistency.
The already discussed in Example 3.1 full adder circuit can be defined by the following
constraint logic program (see, e.g., (Fr-uhwirth, 1998)) that uses the Boolean
constraints and, xor and or:
add(I1,I2,I3,O1,O2):-
xor(I1,I2,X1),
and(I1,I2,A1),
xor(X1,I3,O2),
and(I3,X1,A2),
or(A1,A2,O1).
The query add(I1,I2,I3,O1,O2) followed by a labeling mechanism generates the
explicit definition (truth table) of the full adder constraint with eight entries such
as
full-adder(1,0,1,1,0).
We can now generate the equality rules and the membership rules for the compound
constraint (here the full adder constraint) that is defined by means of some
basic constraints (here the and, or and xor constraints). These rules refer to the
compound constraint and allow us to reason about it directly instead of by using
the rules that deal with the basic constraints.
In the case of the full adder constraint the Equality Rules Generation
algorithm generated 52 equality rules in 0.27 seconds. The constraint propagation
carried out by means of these equality rules is more powerful than the one carried
out by means of the rules generated for the and, or and xor constraints. For exam-
ple, the query [X,Y,Z]::[0,1], full-adder(1,X,Y,Z,0) reduces Z to 1 whereas
the query [X,Y,Z]::[0,1], add(1,X,Y,Z,0) does not reduce Z at all.
This shows that the rule consistency for a compound constraint defined by means
of the basic constraints is in general stronger than the rule consistency for the basic
constraints treated separately. In fact, in the above case the equality rules for the
full adder constraint yield the relational (1,5)-consistency notion of (Dechter &
van Beek, 1997), whereas by virtue of Theorem 5.2, the equality rules for the and,
or and xor constraints yield a weaker notion of arc consistency.
8 Related Work
In a number of papers a link was made between constraint programming and rule-based
programming. To start with, in (Montanari & Rossi, 1991) a general study
of constraint propagation was undertaken by defining the notion of a relaxation
rule and by proposing a general relaxation algorithm that implements constraint
26 Krzysztof R. Apt and Eric Monfroy
propagation by means of a repeated application of the relaxation rules. However,
this abstract view of constraint programming cannot be realized in a simple way
since the application of a relaxation rule is a complex process.
In (Apt, 1998) we showed how constraint programming can be couched in proof
theoretic terms by viewing the programming process as the task of proving the
original CSP. In the proposed framework two types of rules were proposed: deterministic
ones and the splitting ones. Further, the deterministic rules were either
concerned with domain reduction or constraint reduction. In the former case the
rules were called domain reduction rules and in the latter case constraint reduction
rules. Such rules are high-level abstractions and on the implementation level they
can involve complex computations.
It is useful to see that the rule-based approach to constraint programming proposed
in this paper is an instance of this proof theoretic view of constraint pro-
gramming. Namely, the equality rules and the membership rules are examples of
the domain reduction rules while labeling, the formal treatment of which is omitted
here, is an example of a splitting rule.
The important gain is that the implementation of the considered here equality
rules and membership rules boils down to a straightforward translation of them
into the CHR syntax. This leads to an implementation of this approach to constraint
programming by means of constraint logic programming. The important limitation
is that this approach applies only to the CSP's built out of predefined, explicitly
given finite constraints.
A similar approach to constraint programming to that of (Apt, 1998) was proposed
in (Castro, 1998). In his approach the proof rules are represented as rewrite
rules in the already mentioned in the introduction programming language ELAN.
In this work the emphasis was on showing how the general techniques of constraint
programming, in particular various search strategies can be expressed in the form
of rules.
While preparing this revised version of the paper we noted that a similar notion
to our rule consistency notion was introduced in the context of the theory of fuzzy
sets, see (Pedrycz & Gomide, 1998)[pages 252-261]. The notion there considered
deals with rules of the form "if x is A, then y is B", where A and B are fuzzy sets.
In spite of the same name used (namely, rule consistency), the uses of both notions
are different. In our case, we employ it to reduce specific CSP's to smaller ones,
while in the case of fuzzy set theory the corresponding notion is used to detect
conditions for "potential inconsistency".
9 Conclusions
The aim of this paper was to provide a framework in which constraint programming
can be entirely reduced to rule-based programming. It involved constraint
satisfaction problems built out of explicitly given constraints. In the case the latter
constraints are defined over small finite domains these CSP's can be often solved
by means of automatically generated constraint propagation algorithms.
We argued that such CSP's often arise in practice and consequently the methods
Constraint Programming viewed as Rule-based Programming 27
here developed can be of practical use. We believe that the approach of this paper
could be applied to a study of various decision problems concerning specific multi-valued
logics and this in turn could be used for an analysis of digital circuits (see,
e.g., (Muth, 1976) where a nine valued logic is used). Other applications could involve
non-linear constraints over small finite domains and the analysis of polyhedral
scenes in presence of shadows (see (Waltz, 1975)).
The introduced notion of rule consistency is weaker than arc consistency and can
be in some circumstances the more appropriate one to use. For example, for the
case of temporal reasoning considered in the last section we easily generated all
equality rules that enforce rule consistency whereas 24 hours turned out not be
enough to generate the membership rules that enforce arc consistency. (For a more
precise summary of the tests carried out see the appendix.)
Finally, the notions of rule consistency and membership rule consistency could be
parametrized by the desired maximal number of variables used in the rule premises.
Such parametrized versions of these notions could be useful when dealing with constraints
involving a large number of variables. Both the Equality Rules Generation
algorithm and the Membership Rules Generation algorithm and their
implementations can be trivially adapted to such parametrized notions.
The approach proposed in this paper could be easily integrated into constraint
logic programming systems such as ECL i PS e . This could be done by providing an
automatic constraint propagation by means of the equality rules or the membership
rules for flagged predicates that are defined by a list of ground facts, much in the
same way as now constraint propagation for linear constraints over finite systems
is automatically provided.

Acknowledgements

We would like to thank Thom Fr-uhwirth, Andrea Schaerf and the anonymous referees
for useful suggestions concerning the preliminary version of this paper.



--R

Maintaining knowledge about temporal intervals.
A proof theoretic view of constraint programming.
The essence of constraint propagation.
Automatic generation of constraint propagation algorithms for small finite domains.


Introduction to the CLAIRE programming language.
Departement Math'ematiques et Informatique
Building constraint satisfaction problem solvers using rewrite rules and strategies.
A simple and efficient Boolean constraint solver for constraint logic programming.
Constraint propagation with interval labels.
Local and global relational consistency.
The OPS5 user's manual.
Theory and practice of constraint handling rules.
Constraint Handling Rules.


Introduction to metamathematics.
Artificial intelligence.
Consistency in networks of relations.
Programming with constraints.
Good old discrete relaxation.
Constraint relaxation may be perfect.

An introduction to fuzzy sets.
Foundations of constraint satisfaction.
Principles of database and knowledge-base systems
Constraint satisfaction using constraint logic programming.
Generating semantic descriptions from drawings of scenes with shadows.
Artificial intelligence.
--TR

--CTR
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
Abdennadher , Christophe Rigotti, Automatic generation of rule-based constraint solvers over finite domains, ACM Transactions on Computational Logic (TOCL), v.5 n.2, p.177-205, April 2004
constraint programming;rule-based programming;finite domain