A New Framework for Reasoning about Points, Intervals and Durations

1 Introduction

Several formalisms for expressing and reasoning with temporal constraints have been proposed [18], [17], [3], [7]. Several classes of Temporal Constraint Satisfaction Problems (TCSP) are defined depending on the time entity that the variables can represent, namely time points , time intervals, durations and the class of con­ straints namely qualitative, metric or both . Qualita­ tive approaches such as Allen 's [1] Interval Algebra and Villain and Kautz's [17] Point Algebra have difficulties in representing metric, numerical information. On the other hand, the quantitative approach of Dechter et. al. [3] has shortcomings in representing qualitative infor­ mation. Meiri [11] proposes a combined network-based computational model for temporal reasoning that is ca­ pable of handling both qualitative and quantitative in­ formation . There have been also efforts to combine point and interval objects in a single constraint network [11].

Abdul Sattar

Knowledge Representation & Reasoning Unit , School of Computing & Information Technology, Griffith University, NATHAN, QLD 4111, AUSTRALIA

A .Sattar@cit.gu. edu. au

In order to encode duration information, a separate net­ work is used which is orthogonal to the interval relation­ ship network (e.g., lA [1], PDN [12], APDN [19], metric time-point and duration model [2]) but these two net­ works do not function independent of each other. Bar­ ber [2] presents a duration based temporal model with metric constraint but this model cannot handle disjunc­ tive qualitative constraint. Meiri's attempt [11] to unify the qualitative and quantitative constraint can handle both point and interval variables but cannot handle du­ ration information.

Given a TCSP S, one important reasoning problem is to determine whether S is consistent. Consistency checking is NP-hard problem for the general TCSP [3], [15], while they are polynomial for PA [16] and for some important special cases of lA and TCSP. These include a sub-algebra of Interval Algebra namely, ORD-Horn class [13] and simple TCSP [3] . In a landmark paper [13] Nebel and Biirckert show that ORD-Horn class form the maximal tractable class. It is also known that PDN and APDN admit polynomial algorithms for the consistency checking problem only when the constraints are simple.

We present a new framework for representation and reasoning about points, intervals and durations-Point Interval Duration Network (PIDN). The PIDN ad­ equately handles both qualitative and quantitative tem­ poral information. We show that existing frameworks such as Interval Algebra, Point Algebra, TCSP frame­ work, PDN and APDN become special cases of PIDN. The underlying algebraic structure of PIDN is closed under composition and intersection . Determining con­ sistency of the PIDN is NP-Hard . However, we identify some tractable subclasses of PIDN. In the spirit of ORD­ Horn class of Nebel and Burkert [13], we characterize the maximal tractable subclass of this algebra. Further, we show that path consistency is not sufficient to ensure global consistency for the tractable class of PIDN. We identify a subclass for which enforcing 4-consistency suf­ fices to ensure the global consistency, and prove that this subclass is maximal for qualitative constraints. Our ap­ proach is based on the geometric interpretation of the domain of the temporal objects and hence, provides a better insight to some of the earlier problems . It also gives a simpler analysis of ORD-Horn classes as the max-

2 Geometric Interpretation

We refer here to two types of temporal objects namely, points and intervals . Intervals correspond to time period during which events occur and points represent the be­ ginning and end point of some event as well as the neutral points of time. A useful representation of interval rela­ tions is in terms of regions in the Euclidean plane [9; 14] . Namely, an interval is defined by a pair of real numbers (X, Y) such that X ~ Y. (The special case of X = Y refers to an interval as a time point). Hence, the set of all intervals in that sense can be identified with the half plane H defined by the in-equation X ~ Y in the (X, Y)-plane. Let (a, b) be a fixed interval. If (a, b) imposes a constraint on an interval (X, Y) then the ad­ missible domain of (X, Y) is a region (not necessarily a connected region) in this half plane.

Thus a more general way of defining a Temporal Con­ straint Satisfaction Problem is to specify the admissi­ ble region that one temporal object imposes on another. The variables are the 2-dimensional points in this half plane representing general temporal objects. A tempo­ ral object can be a time point or a time interval. The domain of the temporal object is H. The constraints can be viewed as admissible regions and a disjunction of constraints is the union of the regions. For a given tem­ poral object, we denote d = Y - X as the duration of the object. The time points correspond to the temporal objects of 0 duration. We can define the dimension of a relation as the dimension of the associated region. Let us consider the well-known example here [11] .

Example 1: John and Fred work for a company that has local and main offices in LA. They usually work at the local office, in which case it takes John less than 20 minutes and Fred 15-20 minutes to get to work. Twice a week John works at the main office, in which case his commute to work takes at least 60 minutes. Today John left home between 7:05-7:10am, and Fred m-rived at work between 7:50-7:55am. We also know that Fred and John met at a traffic light on their way to work.

There are four temporal objects 0 1 (John was going to work), 02 (Fred was going to work), Oa (John left home) and 0 4 (Fred arrived at work). 01 and 02 are time intervals and Oa and 0 4 are time points with the unary constraints (Xa = Ya) and (X4 = Y4). Oa and 04 also have other metric unary constraints which restricts their domains to regions R3 , corresponding to interval [7:05,7:10] and R4 corresponding to [7:50, 7:55], respec­ tively (see Figure 1) . Similarly, any instantiation of Oa imposes a restriction (qualitative) on 01 that both have same abscissa value and 04 imposes a restriction on 02 that they have same ordinate value . There are unary restrictions of the duration on 0 1 and 02. The admissi­ ble regions are R11 U R21, R2 , Ra and R4 . 02 imposes a binary qualitative constraint on 0 1. For every instanti­ ation of 02 in R2 this constraint defines the domain of 0 1. The composition of the two constraints yield ABC D as the admissible region of 0 1. The admissible domain of 0 1 based on admissible instantiation of 03 and the unary constraint on duration is R11 U R21. Taking the intersection of the constraints, the admissible region of 01 is only R21· This illustrates the process of intersec­ tion and composition operations when we represent the domain as regions in the half plane. It may be noted that R3 and R4 are !-dimensional whereas R1 and R2 are 2-dimensional.

3 Point-Interval-Duration Network (PIDN)

This study is inspired by the geometric interpretation of temporal objects, constraints and their operations. There can be different ways of encoding regions. In the present study, we consider only the TCSP's having con­ strained regions as convex hexagon with sides parallel to three fixed lines namely, X-axis, Y-axis , and X= Y line. Such regions can be described in terms of three intervals.

3.1 Definitions

A Point-Interval-Duration Network (PIDN) con­ sists of a set of variables 0 1, 02 , ... , On, having H as the domain, each representing a temporal object (interval or point). An instantiation of 0; means mapping of 0 ; to a point in H. A constraint is a disjunction of the form C = (rl) V (r2 ) V ... V (rt), where each r is an ordered set of three intervals (S, E, D) . The intervals S, E and Dare closed or open and bounded or unbounded in either side. Intuitively, the intervals S, E and D represent the range of the domains of the start point, end point and the du­ ration, respectively of the temporal object. A temporal object 0 = (X, Y) is said to satisfy the constraint C, if it satisfies at least one of the disjuncts r; and it satisfies a 7'; , if XES;, Y E E; and (Y- X) ED;. Following the standard notation, [a,b], (a,b], [a,b),and (a,b) repre­ sent closed, semi-closed, open intervals , respectively. ? represents a unrestricted interval or universal constraint.

A unary constraint C for a temporal object 0 ; = (X;, Y;) specifies a set of rp = (Sp , Ep, Dp) which con­ straints the domain of 0;. We assume that a unary constraint is always a quantitative constraint and the endpoints of S, E and D are real numbers .

A binary constraint is of the form 0; ( C)Oj, where each disjunct rp of C is defined in terms of X;, Y; and d; and it constrains the domain of Oj. The end points of S, E and D are one of the following types:

1. A nonnegative real number, say o for metric infor­ matiom.
2. A variable X;, Y; and d;, say W; for qualitative in­ formation.

A binary constraint is said to be a qualitative con­ straint if the endpoints of S, E and D are of the restric­ tion that o takes on values only 0 or, oo, A network is called a Qualitative PIDN, if all its constraints are qualitative.

A solution is an instantiation of all 0; 's satisfying all the constraints. The network is consistent iff at least one solution exists.

Example 2

1. While returning from office John took longer than the time he took to reach office.
2. If OJ (going to office) and 02 is (returning from office) then OJ(C)02 with C as ((YJ, oo), ?, (dJ, oo)), where dJ = YJ - XJ. We assume here that John returned from the office after he reached the office.
3. We can encode a qualitative constraint involving point and duration information. Fred and John take same time to reach office but they start at different time. Let Op = (XF, YF) (Fred going to office) and OJ as above and dp = (YF- Xp).

We write Op(C)OJ , where

1. We can encode a disjunction of constraints on point and duration. It may not be possible to encode directly this information in PDN formalism. Bob reaches office in less than 20 minutes if he start before 7.00am but takes at least 40 minutes due to traffic if he starts later.

The unary relation on OB {Bob was going to office) is

3.2 Operations on PIDN

In order to carry out the reasoning task on PIDN, it is necessary to define 3 fundamental operations on PIDN. These are (i) Composition, (ii) Intersection and (iii) Con­ verse .

Intersection of Constraints: Let C 1 = V; (r;) and C 2 = V; ( ri) be two constraints representing two sets of triplets of intervals . C 1 n C 2 is the disjunction of the pairwise intersection of r; 's and rj 's such that if 7'; = (S, E, D) and rj = (S', E ', D') then r; n rj = (SnS', EnE', DnD'). Intuitively, it is the intersection of the admissible regions defined by both the constraints. If the end points of S, (S', resp.) are a and b (c and d, respectively), then SnS' has end points as sup( a, c) and inf(b, d) . In case sup( a, c) > inf(c, d), then S and S' are disjoint. However for all non-disjoint cases, it is not trivial to compute S n S'. If the constraints are unary constraints, the computation of the extremes are straight forward. If the constraints are qualitative constraints then using the fact that for any i, 0 :::; X; :::; Y; :::; oo, it is possible to determine the intersection of S n S'. On the other hand, when the constraints are quantitative bi­ nary constraints, the difficulty arises in computing inter­ section when the extremes of S and S' involve different variables. For example, if a = Y; + 61 and c = X;- 62 then it will be hard to determine sup( a, c). This situ­ ation can be handled in two different ways, (i) the in­ tersection involves two different terms with disjunction or, (ii) approximate the intersection with any one of the term.

Converse: Since every inequality is of the form W; ± 03 :::; Wj :::; W; ± 64 , it can be equivalently written as Wj =f o4 :S W; :S Wj =f 03.

Composition in PIDN: Let C 1 and C 2 be two binary constraints such that O;(C 1 )0j and Oj(C 2 )0k. In other words, C 1 ( C 2 , respectively) defines the admissible do­ main of Oj( Ok ) in terms of 0; (Oj) · The composition of C 1 and C 2 , denoted by C 1 0 C 2 defines the domain of Ok with respect to 0;. C 1 0 C 2 is obtained as the disjunctions of pairwise compositions of the disjuncts r; of C 1 and rj of C 2 . Thus, each interval in a disjunct of C 2 is of the form Wj ± J1 :S Wk :S Wj ± J2 and similarly, that of C 1 is of the form W; ± o3 :::; Wj :::; W; ± J4 . Using the composition of inequalities, we can express wk in terms of W;. Intuitively, composition is the Minkowski addition of sets in two-dimensional plane.

Example 3: Let 01C 1 02 where C 1 = ((Y1,oo), ?,(d1,oo)) and 0 2C 2 0 3 where C 2 = ([0, X2), ?, ?)03 then using compo­ sition we get C 1 @ C 2 = ((0, Yl), ?, ?).

Proposition 1: PIDN is closed under composition, m­ tersection and converse.

4 Reasoning with PIDN

The most important tasks for the any TCSP ( and hence for PIDN) is to decide consistency; and if the network is consistent then to find a consistent instantiation of the temporal objects.

Proposition 2: The problem of deciding consistency of the PIDN is NP-hard.

Proof: (sketch) The qualitative temporal consistency problem based Interval Algebra becomes a special in­ stance of PIDN. We show this in Section 5 and deciding consistency of Interval TCSP is NP-hard [18]. D

4.1 Tractable cases of PIDN

Processing of disjunction: The constraint r1 V r2 where r1 = (S1,E1,D1) and r2 = (S2,E2,D2) can be joined along S to be equivalent to r if (i) E1 = E2, D1 = D2 and (ii) S1 U S2 is a single interval. In this case, r = ( S 1 U S2, E1, Dl). Clearly, r 1 and r2 define two convex polygonal regions such that the union is also convex.

The constraint r 1 V r2 can be loosely joined along S to be equivalent to r if r~ = (closure(Sl), E1, D1) and r~ = (closure(S2) , E2, D2) can be joined along S. If S = (a , b) then closure(S) = [a , b] . It is easy to see that if 51 and 52 are open intervals it is not necessary that 51 U 52 is a single interval. Hence, though r 1 and r 2 define two convex polygonal regions in H , by loose join we only ensure that the union of these regions are connected but for a line or a point .

In the similar line, we can also join along 5 and E if both the disjunct have same D and the union results in single convex region. Thus for a given C, it may be possible to combine a set of disjunctions along 5, E and/or D to get a constraint having less number of disjunctions.

A constraint is said to be a convex constraint if it can be reduced to a disjunction-free constraint by the pro­ cess joining along 5, E and/or D. An PIDN is said to be a convex PIDN if all its constraints are convex constraints.

Example 4: If C 1 ((5, 7), [17, 20), [11, 14]) v ((7, 9), [17, 20), [11 , 14]) it can be loosely joined along S to yield ((5, 7) U (7, 9) , [17, 20) , [11, 14]). The region defined by C 1 in H is a convex polygonal region except for a linear discontinuity of X = 7 as defined by the follwing.

However, on the other hand, if C 2 = ( (5 , 8], [17, 20), [11 , 14])V ((8, 9), [17, 20), [11, 14]) then its loose join along S results in a convex polygonal region defined by ((5, 9), [17, 20), [11, 14]). lfC 3 = ((5, 7) , [17, 20], [11 , 14])v((6, 7.5], (17.5, 20.5], [11, 14]) then also we can join these disjunct along S and E to obtain a single constraint as ((5, 7.5], [17, 20.5], [11, 14]).

A constraint is said to be a preconvex constraint if it can be written as a disjunction-free constraint by the process of loose join. A PIDN is called as pre-convex PIDN if all its constraints are pre-convex. The pre­ convex constraints correspond to the polygonal admissi­ ble regions with finite number of linear discontinuities. Proposition 3: The Pre-convex PIDN is closed under composition, intersection and converse.

Proof: {sketch) The admissible regions defined by a con­ vex constraint is a convex polygonal region in H . The convexity property is preserved during intersection, com­ position and converse operations. It is easy to see that the result holds true for pre-convex constraints too which define admissible regions as convex regions with finite number of linear discontinuities and these do not affect the three basic operations. 0

4.2 k-Consistency in PIDN

The single most important technique of determining con­ sistency of a temporal network is the idea of enforc­ ing some degree of local consistency to eliminate non­ feasible instantiations. The PIDN is 3-consistent if it is arc-consistent and for each triplets ( i, j, k), for any con­ sistent instantiation of 0; and Oj (i.e. , satisfying binary constraint between them) there exists an instantiation of Ok which is consistent with the constraints 0; ( C;k )Ok and Oj(Cjk)Ok. Similarly, we can generalized the notion to define k-consistent.

Proposition 4: For a Pre-convex PIDN, enforcing 4consistency is sufficient to ensure consistency of the net­ work.

Proof (sketch} We prove the result initially for the Con­ vex PIDN and then generalize it to Pre-Convex PIDN. Let us assume that the convex PIDN with temporal ob­ jects 0;, 1 < i < n is 4-consistent. Let us also assume that the admissihle regions of On in H, as defined by the consistent instantiation of each of 0;, 1 :s; i :s; ( n - 1) are R;n, 1 :s; i :s; (n -1) .Convex PIDN define the admis­ sible regions which are convex. Since it is 4-consistent , RjnnRknnRtn :f 0. From Helly's Theorem [4], we have n1 ~i~(n- 1 ) R;n :f 0. This property also holds for pre­ convex relations due to the fact that the instantiation can be an interior point of the admissible regions of the pre-convex relations [9 ]. 0

It is well known that 3-consistency is enough to guar­ antee global consistency for all the tractable temporal network problems. The tractable class include Simple TCSP(or , STP) [3], STP;t [5] Simple PDN [12], Sim­ ple APDN [19], Point Algebra [17], SIA subclass of lA and ORD-Horn class of lA. However, in PIDN, for its tractable subclass 3-consistency is not enough to guar­ antee global consistency. The following counterexample justifies the claim.

Example 5: Fred, John, Bob and Mary work for the com­ pany. Today, Mary started before Fred. Bob left his home after Fred left. Mary reached after Bob. Mary takes less time than John to reach office. John started after Fred and reached before Bob.

There are four temporal objects Os,OF,OJ and OM. The binary relations are the following

One can see that there exist consistent instantiations of OM for the consistent instantiations of any pair of Os , OF and 01. The admissible regions C B M, C F M, C 1M have pair­ wise non-empty intersection, but CsM U CFM U C;M = 0. The PIDN is inconsistent.

Determining consistency of PIDN A network can be converted to equivalent path consistent form by ap­ plying any path consistency algorithm to the network. Path consistency algorithm such as PC-2 [10] . This al­ gorithm takes O(n 3 ), when n is the number of nodes in the network. However, each intersection and composi­ tion operation takes 6 times more operations than the TCSP. Nevertheless, the path consistency algorithm re­ quires polynomial time.

The 4-consistency requires O(n 4 ) in terms of the num­ ber of temporal objects . Thus consistency checking of Pre-convex PIDN can be done in polynomial time. We now prove the following result.

Proposition 5: For consistency checking problem of a Qualitative P IDN, the maximal tractable subclass is Pre­ convex PIDN.

Proof (sketch) The proof is based on following observa­ tions . If the PIDN is not pre-convex then some of its constraints define the admissible regions fall into one of the following two cases;

(i) It is the union of pre-convex regions which are sepa­ rated by a 2-dimensional region . or , (ii) it is the union of connected set of pre-convex regions. Another inter­ esting property of the Qualitative PIDN is that the con­ straints which correspond to case(i) above eventually yield case(ii) in the process of transitive closure with composition and intersection. Thus, if the PIDN is not pre-convex then its transitive closure must contain the constraints of type (ii). Since the sides of these polygo­ nal regions are parallel to three fixed lines, there can be only 12 different non-convex corners possible and out of which 6 of them are the converse of the other six. One can make use of Nebel & Biirckert's results here to show that for these 6 cases then consistency finding is NP­ complete. These 6 cases when translated into equivalent Clause algebra form include constraints of the type X; :::; Xi v d; ~ dj or, X; ~ Xi v d; :S di or, X; ::=; Xi V Y; ~ Yj or, X; ~ Xj V Y; ::=; Yj or, Y; ::=; Yj V d; ::=; dj or, Y; ~ Yj· V d; ~ dj D

It is interesting to note that this result need not be true for Pre-convex PIDN which is not qualitative. The major difference is that the transitive closure need not always contain case (ii). Since, in general PIDN is intractable, any complete algorithm must perform some sort of search over all possible combinations of disjunction-free labeling.

5 Expressive power of PIDN

We show that all the major temporal constraint satis­ faction problems are special cases of PIDN.

lA as a special case of PIDN: Interesting to note that Interval algebra is a spec1al case of Qualitative PIDN where there is no constraint on the duration and we have only one type of temporal objects namely, time intervals. Hence, without loss of generality we rep­ resent a constraint as a pair of intervals rather than a triplets of intervals. For example, Oi p Oj Oi ( (Y;, oo), [ Xj, oo)) 0 j . We call such constraints as Rectangular Constraint as the admissible regions are rectangles. The 13 basic relations can be equivalently written as Rectangular constraints.

The intuitive notion of convex and pre-convex rela­ tions can be interpreted in this context too and these are similar to the terms introduced in [9). It is inter­ esting to note that the relations of lA which are equiva­ lent to single rectangular relations are convex relations. For example, relation like {p, m, o} can be combined to yield a single rectangular constraint and is a convex re­ lation . For the lA relation {p, o} the equivalent PIDN constraints is ([O,Xi),[O,Xi)) V ([O,Xi),(Xi,Y;)). The disjunction here can be loosely joined along E and hence is a pre-convex relation. The preconvex relations cor­ respond to the Nebel and Biirckert's ORD-Horn clause class [9) . The following observation justifies that for lA 3-consistency is sufficient for global consistency of the tractable subclasses.

Proposition 6: For a PIDN with rectangular con­ straint, 3-consistency implies global consistency.

Proof (sketch) The argument of proof follows the same line and is due to the fact that if the polygonal regions have sides parallel to two fixed lines then their pairwise non-empty intersection ensures that they have a common non-empty intersection. D

TCSP as a special case of PIDN: The TCSP pro­ posed by Dechter et al [3) can be viewed as a special case of PIDN. The temporal objects are time points. A con­ straint is a disjunction of r's where each r is a (S, ?, ?). The Simple TCSP correspond to the convex subclass and the STP;ts [8), [5), class correspond to pre-convex class. However, PIDN is more expressive than these TCSP's including extensions suggested by Meiri [11).

PDN and PIDN: Navarrete and Marin [12) propose a temporal reasoning system, PDN that takes both points and durations as primitive objects and allow relative and indefinite information. PDN consists of two PA net­ works separately and are connected by a set of ternary constraints. One PA network represents the set of time points and the other represents duration between pairs of time points. One can visualise both networks as special cases of the PIDN, the first having just the r = S and the second one as a PIDN with r = D. However, in the proposed formalism it is possible to club the information into one network avoiding the ternary constraints linking these two networks. Since the PIDN also handles quan­ titative information like APDN which is an extension of the concept of PDN. On the other hand, PIDN can han­ dle disjunctions between point and duration which is not easily possible in PDN. (see Table 1)

Other Related Work: Recently Jonsson and Backstrom [6) have proposed a unifying framework called Disjunctive Linear Relations (DLRs). The DLRs is based on the linear programming paradigm. Jonsson and Briickstrom use Karmarker's and Khachiyan's algo­ rithm to prove that Horn DLRSat (a tractable subclass of DLRs) can be solved in polynomial time.l Though these algorithms are polynomial in time, their optimal solutions are not exact as they are numerical methods . They generate solutions which have the limiting point that is optimal. Therefore, the numerical stability of these methods may be questionable while applying them to the satisfiability problem. On the other hand, Sim­ plex method may be suitable in this context, but may not be polynomial. On the whole, linear programming approach, though expressive, does not take advantage of the underlying structures (e.g., domain constraints) of temporal constraints.

In comparison to DLRs, the PIDN is committed to the standard approach based on a temporal constraint network having binary constraints among time objects. Hence, PIDN has computational advantage over DLRs. For example, if there are 100 time intervals, DLR forms the constraints of 200 variables. At any given iteration it solves a LP of 200 variables. However, if we handle Binary constraint network of 100 nodes then the path consistency algorithm will carry out the composition and intersection of 4 nodes at time in one iteration . Hence PIDN handles only 12 variables. It does this for a polynomial time in 100. But in any iteration it handles 12 variables. DLR also does polynomial number of iteration in 100 and in each iteration it handles 200 variables.

1 However, it is not clear whether it is the maximal tractable subclass of DLRs.

6 Summary and Future Scope

In the present work we propose an unified formalism which treats points, intervals and durations as tempo­ ral objects and handles qualititative and quantitative constraints (Table 1). In general, checking consistency of PIDN is NP-Hard and the maximal tractable class for qualitative case is identified. Unlike the other for­ malisms, for the tractable classes, the level of local con­ sistency for guaranteeing global consistency is 4. It is shown that the all other major temporal constraint for­ malisms are special cases of the proposed network.

The aim of the present study is to establish the fact that a specific geometrical interpretation of the time domain helps in unifying the earlier diverse concepts. There are many unresolved questions remain to be an­ swered. We outline some of the possible future work: (i) To devise a specialized algorithm to compute inter­ section, composition for qualitative or for the general network; (ii) Determining the maximal tractable class for the general PIDN. It may be noted that the the fact that non-convex disconnected admissible regions yield connected regions by the process of composition do not hold true for the quantitative constraints. It may be possible to identify the class for which this is true; (iii) Developing an efficient search algorithm for the general network, and comparing empirical performance of PIDN and DLRs

1. F. Barber . A metric time-point and duration-based temporal model. SIGART Bulletine, 4(3):30-49, 1993.
2. R. Dechter, I. Meiri, and J. Pearl. Temporal con­ straint networks. Artificial Intelligence, 49:61-95, 1991.
3. H. Edelsbrunner . Algorithms in Combinatorial Ge­ ometry. Springer, Berlin, 1987.
4. A. Gerevini and M. Cristani. On finding a solution in temporal constraint satisfaction problem. Proc. of IJCAI'97, pages 1460-1465, 1997.
5. P. Jonsson and C. Backstrom. A unifying approach to temporal constraint reasoning. Artificial Intelli­ gence, 102(1) :143- 155, 1998.
6. H. Kautz and P. Ladkin. Integrating metric and qualitative temporal reasoning. Proc. of AAAI-91, pages 241- 246, 1991.
7. M. Koubarakis. Dense time and temporal con­ straints with =f.. Proceedings of the KR '92, pages 24- 35, 1992.
8. G. Ligozat . "corner" relations in allen's algebra. Constraints, 3(2 and 3):165-177, 1998.
9. A. K. Mackworth. Consistency in network relations. Artificial Intelligence, 8·:99- 118, 1977.
10. I. Meiri. Combining qualitative and quantitative constraints in temporal reasoning. Artificial Intelli­ gence, 87:343-385, 1996.
11. I. Navarrette and R. Marin. Qualitative tempo­ ral reasoning with points and durations. Proc. IJ­ CAI'97, pages 1454-1459, 1997.
12. 13] B. Nebel and H. Biirckert . Reasoning about tem­ poral relations: A maximal tractable subclass of allen's interval algebra. Journal of ACM, 42(1):4366 , 1995.
13. 14] Arun K Pujari. Neighbourhood logic and inter­ val algebra. Technical Report No. 116, United Na­ tions University, International Institute of Software Technology, Macau, 1997.
14. 15] E. Schwalb and L. Vila. Temporal constraints: A survey. Constraints, 3(2 and 3):129-150, 1998.
15. 16] P. van Beek. Reasoning about qualitative tempo­ ral information. The 8th AAAI-90, pages 728-734, 1990.

Acknowledgement

The authors thank Peter van Beek for his valuable com­ ments on an early draft of this paper . Also, the first author gratefully acknowledges CSIR, India (Research Project No.25/96/81/EMR-II) and Griffith University for supporting the research.