Tractable disjunctions of linear constraints.
We study the problems of deciding consistency and performing variable elimination for disjunctions of linear inequalities and disequations with at most one inequality per disjunction. This new class of constraints extends the class of generalized linear constraints originally studied by Lassez and McAloon. We show that deciding consistency of a set of constraints in this class can be done in polynomial time. We also present a variable elimination algorithm which is similar to Fourier's algorithm for linear inequalities. Finally, we use these results to provide new temporal reasoning algorithms for the Ord-Horn subclass of Allen's interval formalism. We also show that there is no low level of local consistency that can guarantee global consistency for the Ord-Horn subclass. This property distinguishes the Ord-Horn subclass from the pointizable subclass (for which strong 5-consistency is sufficient to guarantee global consistency), and the continuous endpoint subclass (for which strong 3-consistency is sufficient to guarantee global consistency). Copyright 2001. Elsevier Science B.V.
Introduction
Linear constraints over the reals have recently been studied in depth by researchers in
constraint logic programming (CLP) and constraint databases (CDB) [JM94, KKR95,
Kou94c]. Two very important operations in CLP and CDB systems are deciding consistency
of a set of constraints, and performing variable elimination. Subclasses of linear
constraints over the reals have also been considered in temporal reasoning [DMP91, Kou92,
Kou94a, Kou95, NB95]. Important operations in temporal reasoning applications are the
deciding consistency of a set of binary temporal constraints, (ii) performing
variable elimination, and (iii) computing the strongest feasible constraints between every
pair of variables.
Disjunctions of linear constraints over the reals are important in many applications
[JM94, DMP91, Kou92, Kou94a, Kou94b, Kou95, NB95]. The problem of deciding consistency
for an arbitrary set of disjunctions of linear constraints is NP-complete [Son85]. It is
therefore interesting to discover classes of disjunctions of linear constraints for which consistency
can be decided in PTIME. In [LM89a], Lassez and McAloon have studied the class
of generalized linear constraints which includes linear inequalities (e.g., 2x 1
This is a longer version of a paper with the same title which appears in the Proceedings of the 2nd
International Conference on Principles and Practice of Constraint Programming (CP96), Cambridge, MA,
August 19-22, 1996. Lecture Notes in Computer Science, Vol. 1118, pages 297-307.
and disjunctions of linear inequations 1 (e.g.,
Among other things, they have shown that the consistency problem for this class can be
solved in PTIME.
[Kou92, IvH93, Imb93, Imb94] have studied the problem of variable elimination for
generalized linear constraints. The basic algorithm for variable elimination has been discovered
independently in [Kou92] and [Imb93], but [Kou92] has used the result only in
the context of temporal constraints. The basic algorithm is essentially an extension of
Fourier's elimination algorithm [Sch86] to deal with disjunctions of inequations. If S is a
set of constraints, let jSj denote its cardinality. Let be a set of generalized linear
constraints, where I is a set of inequalities and D n is a set of disjunctions of inequations.
If we eliminate m variables from C using the basic algorithm proposed by Koubarakis and
Imbert then the resulting set contains O(jI
inequalities and O(jD n j jI j 2 m+1
disjunctions
of inequations. A lot of these constraints are redundant. Imbert has studied this
problem in more detail and presented more advanced algorithms that eliminate redundant
constraints [Imb93, Imb94].
In this paper we go beyond the above work on generalized linear constraints. Our
contributions can be summarized as follows:
ffl We extend the class of generalized linear constraints to include disjunctions with an
unlimited number of inequations and at most one inequality per disjunction. For
example:
The resulting class will be called the class of Horn constraints since there seems to
be some analogy with Horn clauses. We show that deciding consistency can still be
done in PTIME for this class (Theorem 3.4). This result has also been obtained
independently by Jonsson and B-ackstr-om [Jon96]. We also extend the basic variable
elimination algorithm of [Kou92, Imb93] for this new class of constraints.
ffl We study a special class of Horn constraints, called Ord-Horn constraints, originally
introduced in [NB95]. This class is important for temporal reasoning based on the
Ord-Horn class of interval relations expressible in Allen's formalism [All83, NB95].
Our results allow us to improve the best known algorithms for consistency checking
and computing the strongest feasible constraints for this class. This answers an open
problem of [NB95].
The paper is organized as follows. Section 2 introduces the basic concepts needed for
the developments of this paper. Section 3 presents the algorithm for deciding consistency.
Section 4 presents the algorithm for variable elimination. Section 5 presents our results
for the class of Ord-Horn constraints. Finally, Section 6 discusses future research.
Preliminaries
We consider the n-dimensional Euclidean space R n . A linear constraint over R n is an
expression a are integers, x are variables
ranging over the real numbers, and - is 6=. Depending on what - is, we will
1 Some people prefer the term disequations [Imb94].
distinguish linear constraints into inequalities (e.g. equations (e.g.,
inequations (e.g.,
Let us now define the class of constraints that we will consider.
Definition 2.1 A Horn constraint is a disjunction d
is a weak linear inequality or a linear inequation, and the number of inequalities
among does not exceed one. If there are no inequalities then a Horn constraint
will be called negative. Otherwise it will be called positive. Horn constraints of the form
will be called disjunctive.
Example 2.1 The following are examples of Horn constraints:
The first and the third constraint are positive while the second and the fourth are negative.
The third and fourth constraint are disjunctive.
According to the above definition weak inequalities are positive Horn constraints.
Sometimes we will find it more convenient to consider inequalities separately from positive
disjunctive Horn constraints. If d is a positive disjunctive Horn constraint then
where E is a conjunction of equations and i is an inequality. We will often use this notation
for positive Horn constraints.
Notice that we do not need to introduce strict inequalities in the above definition. A
strict inequality like x 1 can be equivalently written as follows:
Similarly, the constraint x 1 a disjunction of inequations can
be equivalently written as the conjunction of the following constraints:
A similar observation is made in [NB95].
Negative Horn constraints have been considered before in [LM89a, LM89b, Kou92,
IvH93, Imb93, Imb94, Kou95]. Nebel and B-urckert have studied the class of Ord-Horn
constraints in the context of qualitative interval reasoning [NB95]. Ord-Horn constraints
form a proper subclass of Horn constraints, and will be considered in detail in Section 5.
Horn constraints have also been studied by Jonsson and B-ackstr-om [Jon96] who discovered
independently the result discussed in Section 3.
We will now present some standard definitions.
Definition 2.2 Let C be a set of constraints in variables x . The solution set of
C, denoted by Sol(C), is:
Each member of Sol(C) is called a solution of C. A set of constraints is called consistent
if its solution set is non-empty. We will use the same notation, Sol(\Delta), for the solution set
of a single constraint.
Remark 2.1 In the rest of the paper we will usually consider one or more sets of constraints
e.g., . In this case we will always regard
a subset of R n even though C i might contain less than n variables. For example, if we
happen to deal with
we may write Similarly, we may write
We will also use the alternative notation Sol   (\Delta). If C is a set of constraints, Sol   (C)
will always be regarded a subset of R k where k is the number of variables of C (indepen-
dently of any other constraint set considered at the same time). This notation will come
handy in Section 4 where we study variable elimination.
Definition 2.3 Let C 1 and C 2 be sets of constraints in the same set of variables. C 1 will
be called equivalent to C 2 if logically follows from a set
of constraints C, denoted by C every solution of C satisfies c.
We will now present some concepts of convex geometry [Sch86, Gru67] that will enable
us to study the geometric aspects of the constraints considered. We will take our definitions
from [LM89a]. If V is a subspace of the n-dimensional Euclidean space R n and p a vector
in R n then the translation called an affine space. The intersection of all affine
spaces that contain a set S is an affine space, called the affine closure of S and denoted
by Aff(S). If e is a linear equation then the solutions set of e is called a hyperplane.
In R 3 the hyperplanes are the planes. In R 2 the hyperplanes are the straight lines. A
hyperplane is an affine space and every affine space is the intersection of a finite number
of hyperplanes. If E is a set of equalities then Sol(E) is an affine space. If i is a linear
inequality then the solution set of i is called a half-space. If I is a set of inequalities then
Sol(I) is the intersection of a finite number of half-spaces, and is called a polyhedral set.
A set S ' R n is called convex if the line segment joining any pair of points in S is
included in S. Affine subspaces of R n are convex. Half-spaces are convex. Also, polyhedral
sets are convex.
If d is a negative Horn constraint then the solution set of d is
The constraint :d is a conjunction of equations thus Sol(:d) is an affine space. If :d is
inconsistent then d is equivalent to true (e.g., x In the rest of the paper
we will ignore negative Horn constraints that are equivalent to true.
If d is a positive disjunctive Horn constraint of the form :(E - i) then
R n n Sol(:d). The constraint :d is a conjunction E - i where E is a conjunction of
equations and i is a strict inequality. If E j true then d is essentially a weak inequality
inconsistent then its corresponding Horn
constraint d is equivalent to true (e.g., x
and Sol(i) ' Sol(E) then d j :E, so d is actually a negative Horn constraint (e.g.,
consistent and Sol(i) 6' Sol(E)
then its solution set will be called a half affine space. In R 3 the half affine spaces are
half-lines or half-planes. For example, plane. In the rest of the
paper we will ignore positive disjunctive Horn constraints equivalent to a weak inequality,
a negative Horn constraint or true.
3 Deciding Consistency
[LM89a] showed that negative Horn constraints can be treated independently of one another
for the purposes of deciding consistency. The following is one of their basic results.
Theorem 3.1 Let be a set of constraints where I is a set of linear inequalities
and D n is a set of negative Horn constraints. Then C is consistent if and only if I is
consistent, and for each d 2 D n the set I [ fdg is consistent.
Whether a set of inequalities is consistent or not, can be decided in PTIME using
Kachian's linear programming algorithm [Sch86]. We can also detect in PTIME whether
I [ fdg is consistent by simply running Kachian's algorithm 2n times to decide whether
I implies every equality e in the conjunction of n equalities :d. In other words, deciding
consistency in the presence of negative Horn contraints can be done in PTIME. 2
Is it possible to extend this result to the case of positive disjunctive Horn constraints?
In what follows, we will answer this question affirmatively. Let us start by pointing out
that the independence property of negative Horn constraints does not carry over to positive
ones.
Example 3.1 The constraint sets
I
are consistent. But the set I [ inconsistent.
Fortunately, there is still enough structure available in our problem which we can
exploit to come up with a PTIME consistecy checking algorithm. Let
a set of constraints where I is a set of inequalities, D p is a set of positive disjunctive Horn
constraints, and D n is a set of negative Horn constraints. Intuitively, the solution set of
C is empty only if the polyhedral set defined by I is covered by the affine spaces and half
affine spaces defined by the Horn constraints.
The algorithm Consistency shown in Figure 1 proceeds as follows. Initially, we check
whether I is consistent. If this is the case, then we proceed to examine whether Sol(I)
can be covered by Sol(f:d To verify this, we make successive passes
over In each pass, we carry out two checks. The first check discovers whether
there is any positive Horn constraint d j :(E - i) such that Sol(I) is included in the
affine space defined by E. If this is the case then d is discarded and I is updated to reflect
the part possibly "cut off " by d. The resulting solution set Sol(I) is still a polyhedral set.
An inconsistency can arise if Sol(I) is reduced to ; by successive "cuts". In each pass
we also check whether there is an affine space (represented by the negation of a negative
Horn constraint) which covers Sol(I). In this case there is an inconsistency as well. The
algorithm stops when there are no more affine spaces or half affine spaces that pass the
two checks. In this case C is consistent.
Let us now prove the correctness of algorithm Consistency. First, we will need a few
technical lemmas. The first two lemmas show that the sets resulting from successive "cuts"
inflicted on Sol(I) by positive Horn constraints passing the first check of the algorithm
are indeed polyhedral. The lemmas also give a way to compute the inequalities defining
these sets.
2 The exact algorithm that Lassez and McAloon give in [LM89a] is different but this is not significant
for the purposes of this paper.
Algorithm Consistency
Input: A set of constraints
Output: "consistent" if C is consistent. Otherwise "inconsistent".
If I is inconsistent then return "inconsistent"
Repeat
Done / true
For each d 2 D p [ D n do
I / I - :i
If I is inconsistent then return "inconsistent"
Done / false
Remove d from D p
Else If d 2 D n and Sol(I) ' Sol(:d) then
Return "inconsistent"
End If
End For
Until Done
Return "consistent"

Figure

1: Deciding consistency of a set of Horn constraints
Lemma 3.1 Let I be a set of inequalities and :(E - i) be a positive disjunctive Horn
constraint such that Sol(I) ' Sol(E). Then Sol(I - :(E -
The other direction of the proof is trivial.
Lemma 3.2 Let I be a set of inequalities and d k j be a set of
positive disjunctive Horn constraints such that Sol(I) '
l
Then
Proof: The proof is by induction on m. The base case 3.1.
For the inductive step, let us assume that the lemma holds for
Then
using the inductive hypothesis.
The assumptions of this lemma and Lemma 3.1 imply that
Thus
The following lemmas show that if there are Horn constraints that do not pass the two
checks of algorithm Consistency then the affine spaces or half affine spaces corresponding
to their negations cannot cover the polyhedral set defined by the inequalities.
Lemma 3.3 Let S be a convex set of dimension d and suppose that S are convex
sets of dimension d
Proof: See Lemma 2 of [LM89a].
Lemma 3.4 Let I be a consistent set of inequalities and d k j
be a set of Horn constraints such that Sol(I) 6'
Proof: The proof is very similar to the proof of Theorem 1 of [LM89a].
This means that
Aff(Sol(I)) is an affine space of strictly lower dimension than Aff(Sol(I)). Then
is of strictly lower dimension than Sol(I) since the dimension of Sol(I) is
equal to that of Aff(Sol(I)). Thus from Lemma 3.3, Sol(I) 6' S m
now
that
We can now conclude that Sol(I) 6'
The following theorems demonstrate that the algorithm Consistency is correct and
can be implemented in PTIME.
Theorem 3.2 If algorithm Consistency returns "inconsistent" then its input C is inconsistent

Proof: If the algorithm returns "inconsistent" in its first line then I , and therefore C,
is inconsistent.
If the algorithm returns "inconsistent" in the third if-statement then there are positive
Horn constraints d k j such that the assumptions of
Lemma 3:2 hold for I and d Therefore
Consequently,
If the algorithm returns "inconsistent" in the fourth if-statement then there are positive
Horn constraints d negative constraint dm+1 2 D n such that the
assumptions of Lemma 2 hold for I and d
But then
Theorem 3.3 If algorithm Consistency returns "inconsistent" then its input C is inconsistent

Proof: If the algorithm returns "consistent" then I is consistent. Let d
the positive Horn constraints removed from D p [ D n by the algorithm, and
be the remaining Horn constraints. Then
Notice that Sol(I -
otherwise the algorithm outputs "inconsistent"
in Step 2. Also, Sol(I -
otherwise the
algorithm would have removed d k from D p [ D n .
any loss of generality we can also assume that
for all this does not hold for constraint d k , this constraint can
be discarded without changing Sol(C)). From Lemma 3.4 we can now conclude that
Theorem 3.4 The algorithm Consistency can be implemented in PTIME.
Proof: It is not difficult to see that the algorithm can be implemented in PTIME. The consistency
of I can be checked in PTIME using Kachian's algorithm for linear programming
[Sch86]. The test Sol(I) ' Sol(E) can be verified by checking whether every equation e in
the conjunction E is implied by I . This can be done in PTIME using Kachian's algorithm
2n times where n is the number of equations in E. In a similar way one can implement
the test Sol(I) ' Sol(:d) in PTIME when d is a negative Horn constraint.
We have just showed that the consistency of a set of Horn constraints can be determined
in PTIME. This is an important result with potential applications in any CLP or CDB
system dealing with linear constraints [JM94, KKR95, Kou94c]. We will now turn our
attention to the problem of eliminating one or more variables from a given set of Horn
constraints.
Algorithm VarElimination
Input: A set of Horn constraints C in variables X , and a variable
to be eliminated from C.
Output: A set of Horn constraints C 0 in variables X n fxg such that
Projection Xnfxg (Sol   (C)).
Rewrite each constraint containing x as x - U - OE or L - x - OE or x 6= A - OE
where OE is a disjunction of inequations and x does not appear in OE.
For each pair of positive Horn constraints x - U - OE 1 and L - x - OE 2 do
End For
For each pair of positive Horn constraints x - U - OE 1 and L - x - OE 2 do
For each negative Horn constraint x 6= A - OE do
Add A 6= L - A 6= U - OE - OE 1 - OE 2 to C 0
End For
End For
Add each constraint not containing x to C 0
Return C 0

Figure

2: A variable elimination algorithm
4 Variable Elimination
In this section we study the problem of variable elimination for sets of Horn constraints.
The algorithm VarElimination, shown in Figure 2, eliminates a given variable x from a
set of Horn constraints C. More variables can be eliminated by successive applications of
VarElimination. This algorithm does not consider inequalities separately from positive
disjunctive Horn constraints (as algorithm Consistency did in Section 3).
The algorithm VarElimination is similar to the one studied in [Kou92, Imb93] for
the case of negative Horn constraints.
Theorem 4.1 The algorithm VarElimination is correct.
Proof: Let the variables of C be g. If
is an
element of Sol   (C) then it can be easily seen that it is also an element of Sol   (C 0 ).
Conversely, take
consider the set C(x; x 0
If this set is simplified by removing constraints equivalent to true, disjunctions equivalent
to false, and redundant constraints then
Let us now assume (by contradiction) that there is no value x 0 2 R n such that
(C). This can happen only under the following cases:
1. come from positive Horn constraints
otherwise these constraints would have been discarded from C(x; x 0
during
its simplification. But because l -
then l 0 - u 0 . Contradiction!
2. l
reasoning similar to the above, we can show that this
case is also impossible.
Finally, we can conclude that there exists a value x 0 2 R such that
be a set of Horn constraints. Eliminating m variables from C with
repeated applications of the above algorithm will result in a set with O((jI
positive Horn constraints and O(jD n j (jI negative Horn constraints. Many
of these contraints will be redundant; it is therefore important to extend this work with
efficient redundancy elimination algorithms that can be used together with VarElimina-
tion.
This section concludes our study of the basic reasoning problems concerning Horn
constraints. We will now turn our attention to a suclass of Horn constraints with important
applications to temporal reasoning.
5 Reasoning with Ord-Horn Constraints
This section studies a special class of Horn constraints, called Ord-Horn constraints, originally
introduced in [NB95]. This class is important in interval based temporal reasoning
[All83] as we will immediately show below.
Definition 5.1 An Ord-Horn constraint is a Horn constraint d each
is an inequality x - y or an inequation x 6= y and x and y are variables
ranging over the real numbers.
Example 5.1 The following are examples of Ord-Horn constraints:
The first and the last constraint are positive while the second and the third are negative.
In [All83], Allen introduced a calculus for reasoning about intervals in time. An interval
is an element of the following set I:
If i is an interval variable, will denote the endpoints of i. Allen's calculus is
based on thirteen mutually exclusive binary relations which can capture all the possible
ways two time intervals can be related. These basic relations are
and their inverses (equals is its own inverse). Figure 3 gives a pictorial representation of
these relations. For reasons of brevity, we will use the symbols b; m; o; d; s; f and e to refer
Basic Interval Symbol Pictorial Endpoint
Relation Representation Constraints
during j d iiiiiiiii
includes i di

Figure

3: The thirteen basic relations of Allen
to the basic relations in Allen's formalism. The inverse of each relation will be denoted
by the name of the relation with the suffix i (for example, the inverse of b will be denoted
by bi).
Allen's calculus has received a lot of attention and has been the formalism of choice
for representing qualitative interval information. Whenever the interval information to
be represented is indefinite, a disjunction of some of the thirteen basic relations can be
used to represent what is known. There are 2 13 such disjunctions representing qualitative
relations between two intervals. Each one of these relations will be denoted by the set of
its constituent basic relations e.g., fb; bi; d; mg. The empty relation will be denoted by ;,
and the universal relation will be denoted by ?. The set of all 2 13 relations expressible in
Allen's formalism will be denoted by A [NB95].
The following definition will be useful below.
Definition 5.2 Let S be a subset of A, i and j be variables representing intervals, and
An S-constraint is any expression of the form i R j.
Example 5.2 If interval i denotes the time that John reads his morning newspaper and
denotes the time that he has breakfast, and we know that John never reads a newspaper
while he is eating, then the A-constraint
characterizes i and j according to the information given.
Definition 5.3 Let C be a set of S-constraints. The solution set of C is:
Unfortunately, all interesting reasoning problems associated with Allen's interval calculus
are NP-hard [VKvB89] therefore it is interesting to consider subsets of Allen's for-
malism, in the form of subsets of A, that have better computational properties. 3 Three
such subsets of A have received more attention:
ffl The set C which consists of all relations R 2 A which satisfy the following condition.
If i and j are intervals, i R j can be equivalently expressed as a conjunction of
inequalities are endpoints of i and j.
The set C is called the continuous endpoint subclass of A [VKvB89].
ffl The set P which consists of all interval relations R 2 A which satisfy the following
condition. If i and j are intervals, i R j can be equivalently expressed as a conjunction
of inequalities are endpoints
of i and j.
The set C is called the pointisable subclass of A [VKvB89, vBC90, vB92]. Because
ae P the pointisable subclass is more expressive than the continuous endpoint
subclass.
ffl The set H which consists of all interval relations R 2 A which satisfy the following
condition. If i and j are intervals, i R j can be equivalently expressed as a conjunction
of Ord-Horn constraints on the endpoints of i and j. The disjunctive Ord-Horn
constraints involved in this equivalence are not arbitrary. There are at most three
of them, and each one consists of two disjuncts of the form
The set H was introduced by Nebel and B-urckert and named the Ord-Horn sub-class
[NB95]. Because P ae H the Ord-Horn subclass is more expressive than the
pointisable subclass. It consists of 868 relations i.e., it covers more than 10% of A.
Example 5.3 The following are P-constraints:
Their equivalent endpoint constraints are:
second P-constraint is also a C-constraint while the first one is not. For an enumeration
of C and P , see [vBC90].
Example 5.4 The A-constraint i fb; big j is not an H-constraint. The constraint
is an H-constraint which is not a P-constraint. Its equivalent endpoint constraints are:
enumeration of H together with several related C programs has been provided by
Nebel and Burckert. See [NB95] for details.
3 At the expense of being less
The following reasoning problems have been studied for the above subclasses [VKvB89,
ffl Given a set C of S-constraints, decide whether C is consistent.
ffl Given a set C of S-constraints, determine the strongest feasible relation between
each pair of interval variables i and j. The strongest feasible relation between two
interval variables i and j is the smallest set R such that C j. This is the same
as computing the minimal network corresponding to the given set of constraints. 4
In this section we will show how our results can be used to improve the best known
algorithms for the above reasoning problems in the case of the Ord-Horn subclass. We
start with two theorems from [NB95].
Theorem 5.1 Let C be a set of H-constraints. Deciding whether C is consistent can be
done in O(n 3 is the number of variables in C.
Theorem 5.2 Let C be a set of H-constraints. Computing the feasible relations between
all pairs of variables can be done in O(n 5 is the number of variables in C.
We will now use the results of Section 3 to improve the complexity bounds of the above
theorems.
Theorem 5.3 Let C be a set of H-constraints. Let n be the number of variables in C,
and h be the number of constraints (i R such that R 2 H n C. Deciding whether C
is consistent can be done in O(max(n 2 ; hn)) time.
Proof: First we translate C into a set of Ord-Horn constraints C 0 . Since
this translation can be achieved in O(n 2 ) time. Let C I is a set of
inequalities, D p is a set of positive disjunctive Horn constraints and D n a set of negative
Horn constraints. The translation of Nebel and B-urckert shows that C 0 contains
point variables and jD p [
We will use algorithm Consistency from Figure 1 to decide C 0 . In this case Consistency
can be made to work in O(max(n 1
Checking
the consistency of I can be done in O(n 1
constructing a directed graph G
corresponding to I and examining its strongly connected components [vB92]. Now notice
that the statement If-Else-End-If in algorithm Consistency is executed O(jD p [ D n
times. Each execution of this statement takes O(n 1 ) time. Let us see why. If the examined
constraint d is in D p , the test Sol(I) ' Sol(E) amounts to checking whether the
single inequality E is implied by I . This can be done in O(n 1 examining the
strongly connected components of G. Similarly, if d is in D n , the test Sol(I) ' Sol(:d)
can be done in O(n 1 ) time. Therefore deciding whether C 0 is consistent can be done in
deciding whether C is consistent can be done in
Theorem 5.4 Let C be a set of H-constraints. Let n be the number of variables in C,
and h be the number of constraints (i R such that R 2 H n C. Computing the
feasible relations between all pairs of variables can be done in O(max(n 4 ; hn 3
4 We will not define minimal networks formally here. The interested reader can consult [vB92] (or many
other temporal reasoning papers).
Proof: As in [NB95], we will consider all O(n 2 ) pairs of variables in turn. For each pair we
check whether each of the thirteen basic relations is consistent with the given constraints.
The basic relations that satisfy this criterion form the strongest feasible relation between
the pair. Using the algorithm of Theorem 5.3, each check can be done in O(max(n 2 ; hn))
time. The bound of the theorem follows immediately.
In the worst case the parameter h, as specified in the above theorems, can be O(n 2 ).
However in practical applications, we expect h to be significantly less than O(n 2 ) thus the
above theorems are real improvements over [NB95].
6 Future Research
In future research we would like to study more advanced variable elimination algorithms for
Horn constraints. The results of [Imb93, Imb94] that apply to negative Horn constraints
only, should be a good starting point in this direction.
Another interesting problem, which occupies us currently, is to extend the results of
[Kou95] to the pointizable subclass P and the Ord-Horn subclass H of A. [Kou95] studied
the problem of enforcing global consistency for sets of quantitative temporal constraints
over the real numbers. In a globally consistent constraint set all interesting constraints
are explicitly represented and the projection of the solution set on any subset of the
variables can be computed by simply collecting the constraints involving these variables.
An important consequence of this property is that a solution can be found by backtrack-
Enforcing global consistency can take an exponential amount of time
in the worst case [Fre78, Coo90]. As a result it is very important to identify cases in which
local consistency, which presumably can be enforced in polynomial time, implies global
consistency [Dec92].
The class of temporal constraints considered in [Kou95] includes equalities of the form
inequalities of the form x \Gamma y - r and inequations of the form x \Gamma y 6= r where
x; y are variables ranging over the real numbers and r is a real constant. [Kou95] shows
that strong 5-consistency is necessary and sufficient for achieving global consistency for
this class of constraints. It also gives an algorithm which achieves global consistency in
is the number of variables and H is the number of inequations. The
details of this algorithm demonstrate that there are situations where it is impossible to
enforce global consistency without introducing disjunctions of inequations e.g.,
The results of [Kou95] can provide the basis for efficient global consistency algorithms for
the pointizable subclass P . The open question is whether one can use the results of this
paper and [Kou95] to find efficient algorithms for global consistency for the ORD-Horn
subclass.



--R

Maintaining Knowledge about Temporal Intervals.
An optimal k-consistency algorithm
From local to global consistency.
Temporal Constraint Networks.
Synthesizing Constraint Expressions.
A Sufficient Condition For Backtrack-Free Search
Convex Polytopes.


On the Handling of Disequations in CLP over Linear Rational Arithmetic.
Constraint Logic Programming: A Survey.

Constraint Query Languages.
Dense Time and Temporal Constraints with 6
Complexity Results for First-Order Theories of Temporal Con- straints
Database Models for Infinite and Indefinite Temporal Infor- mation
Foundations of Indefinite Constraint Databases.
From Local to Global Consistency in Temporal Constraint Networks.
A Canonical Form for Generalized Linear Constraints.
A Canonical Form for Generalized Linear Costraints.
On binary constraint problems.
Bernhard Nebel and Hans-J-urgen B-urckert
Theory of Integer and Linear Programming.
Real Addition and the Polynomial Time Hierarchy.
Reasoning About Qualitative Temporal Information.
Exact and Approximate Reasoning about Temporal Relations.
Constraint Propagation Algorithms for Temporal Reasoning: A Revised Report.
--TR
Theory of linear and integer programming
An optimal <italic>k</>-consistency algorithm
Constraint propagation algorithms for temporal reasoning: a revised report
Exact and approximate reasoning about temporal relations
Temporal constraint networks
From local to global consistency
A canonical form for generalized linear constraints
Reasoning about qualitative temporal information
Variable elimination for generalized linear constraints
On the handling of disequations in CLP over linear rational arithmetic
On binary constraint problems
Database models for infinite and indefinite temporal information
Redundancy, variable elimination and linear disequations
Reasoning about temporal relations
Constraint query languages
From local to global consistency in temporal constraint networks
The complexity of query evaluation in indefinite temporal constraint databases
A unifying approach to temporal constraint reasoning
A Sufficient Condition for Backtrack-Free Search
Maintaining knowledge about temporal intervals
Synthesizing constraint expressions
Foundations of Indefinite Constraint Databases
From Local to Global Consistency in Temporal Constraint Networks

--CTR
Mathias Broxvall, A method for metric temporal reasoning, Eighteenth national conference on Artificial intelligence, p.513-518, July 28-August 01, 2002, Edmonton, Alberta, Canada
Peter Jonsson , Andrei Krokhin, Complexity classification in qualitative temporal constraint reasoning, Artificial Intelligence, v.160 n.1, p.35-51, December 2004
Mathias Broxvall , Peter Jonsson, Point algebras for temporal reasoning: algorithms and complexity, Artificial Intelligence, v.149 n.2, p.179-220, October
Andrei Krokhin , Peter Jeavons , Peter Jonsson, Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra, Journal of the ACM (JACM), v.50 n.5, p.591-640, September
Manolis Koubarakis, Querying Temporal Constraint Networks: A Unifying Approach, Applied Intelligence, v.17 n.3, p.297-311, November-December 2002
global consistency;ORD-horn constraints;variable elimination;linear constraints;interval algebra