Towards a Complete Classification of Tractability in Allen's Algebra

1 Introduction

This paper improves on known results about algorithms for the problem of reasoning about temporal constraints. Such reasoning is an important task in many areas of AI and elsewehere, such as planning [Allen, 1991], nat­ ural language processing [Song and Cohen, 1988], time serialization in archeology [Golumbic and Shamir, 1993] and more, and there are several frameworks for formalis­ ing such problems, according to different needs .. Among the most frequently used ones are the point algebra [van Beek and Cohen, 1990], used for expressing qualitative relations between time points, the point-interval alge­ bra [Vilain, 1982] for expressing qualitative relations be­ tween time points and time intervals, and the famous interval algebra of Allen [1983] for expressing qualitative relations between time intervals. There are also com­ binations of these and extensions to handle also metric time, such as Meiri's framework [Meiri, 1991], and the works of Kautz and Ladkin [1991], Gerevini et a/. [1993], Dechter et a/. [1991], Jonsson and Backstrom [1996] and Drakengren and Jonsson [1997]. However, it was early proved that the reasoning problem for these formalisms is very hard; e.g. reasoning in Allen's·interval algebra is NP-complete [Vilain and Kautz, 1986], and NP-hardness carries over to more expressive formalisms.

These computational problems have motivated the search for various tractable fragments of the tempo­ ral formalisms, where reasoning can be guaranteed to be reasonably efficient. In particular, several sub­ classes of Allen's algebra have been reported tractable (we assume P ::f N P) [van Beek and Cohen , 1990; Golumbic and Shamir, 1993; Nebel and Biirckert, 1995; Drakengren and Jonsson, 1996; 1997]. However, in view of the large number of possible subclasses of Allen's al­ gebra (the algebra contains 8192 relations, leading to 2 8192 ~ 10 2466 subclasses), such results are in danger of appearing ad hoc. As a first reaction to this , research has recently focused on identifying maximal tractable subclasses; i.e. classes which cannot be extended with­ out losing tractability. This direction is clearly more systematic, since any tractable subclass is included in a maximal tractable one. The first such algebra was identi­ fied by Nebel and Biirckert [1995], soon to be followed by Drakengren and Jonsson [1996, 1997], resulting in eigh­ teen known maximal algebras, subsuming all algebras previously known to be tractable. Still, however, this is a very small number compared to the total number of possible subclasses.

Due to this apparent lack of systematicity, techniques have recently been developed allowing full classifications of tractability, in particular for the point-interval algebra [Jonsson eta/., 1996], but also for the RCC-5 algebra for spatial reasoning [Jonsson and Drakengren, 1997]. A full classification of tractability for an algebra means that we identify the complete set of tractable subclasses in the algebra. Despite the success for the point-interval alge­ bra and the RCC-5 algebra, the corresponding task for Allen's algebra poses a problem more difficult by several orders of magnitude: the number of subclasses in these algebras is only 2 32 ~ 4.3 · 10 9 . In principle, all these can be enumerated on a computer, but this is certainly not the case with the Allen algebra.

In this context, this paper presents a significant step towards a full classification of tractability in Allen's al­ gebra. We show that any algebra that is yet to be found can contain at most three basic relations: (=:), (b) and (b~) , for b E { d, o, s, f} . This means that in order to specify complete temporal knowledge, we cannot hope to find more expressive algebras than those already known. Furthermore, we show that there are exactly two maxi­ mal tractable algebras which can express the important notion of sequentiality [Sandewall, 1994].

Finally, note that the main results of this paper are proved using exhaustive search by computers. Naturally, such proofs cannot be reproduced in a paper, but we encourage researchers in the field to repeat our proofs. All software used in the paper can be obtained from the authors.

The structure of the paper follows. First we present Allen's algebra in Section 2, after which the classification results follow. A discussion concludes the paper. The more complicated proofs are collected in an appendix.

2 Allen's Algebra

Allen's interval algebra [Allen, 1983] is based on the no­ tion of relations between pairs of intervals. An inter­ val x is represented as a tuple (x-, x+) of real numbers with x- < x+, denoting the left and right endpoints of the interval, respectively, and relations between intervals are composed as disjunctions of basic interval relations, which are those in Table 1 (denoted B). Such disjunc­ tions are represented as sets of basic relations, but using a notation such that e.g. the disjunction of the basic in­ tervals-<, m and f~ is written (-< m f~). Thus, we have that (-< f~) ~ (-< m f~). Sometimes, the disjunction of all basic relations is written T, and the empty relation is writ ten .l (this also used for relations between interval endpoints, denoting "always satisfiable" and "unsatisfi­ able", respectively). The algebra is provided with the operations of converse, intersection and composition on intervals, but we shall need only the converse operation. The converse operation takes an interval relation i to its converse i~, obtained by inverting each basic relation in i, i.e., exchanging x and y in the endpoint relations of Table 1.

By the fact that there are thirteen basic relations, we get 2 13 = 8192 possible relations between intervals in the full algebra. We denote the set of all interval relations by A. Subclasses of the full algebra are obtained by considering subsets of A. There are 2 8192 ~ 10 2466 such subclasses.

Although there are several computational problems as­ sociated with Allen's interval algebra, this paper focuses on the problem of satisfiability of a set of interval vari­ ables with relations between them, i.e. deciding whether there exists an assignment of intervals on the real line for the interval variables, such that all of the relations between the intervals are satisfied. We define this as follows.

Definition 2.1 (A-SAT(I)) Let I be a set of interval relations. An instance of A-SAT(I) is a labelled directed graph S = (V, E), where the nodes in V are interval variables and E is a subset of V x I x V. A labelled edge (u, r, v) E E means that u and v are related by r.

A function M taking an interval variable v to its in­ terval representation M(v) = (x-,x+) with x- < x+, x-, x+ E R, is said to be an interpretation of S.

An instance (V, E) is said to be satisfiable iff there ex­ ists an interpretation M such that for each (u, r, v) E E, M ( u )r M ( v) holds, i.e. the endpoint relations required by r (see Table 1) are satisfied by the assignments of u and v. Then M is said to be a model of (V, E) .

We refer to the size of an instance (V, E) as lVI +lEI. 0

For A, we have the following result.

Proposition 2.2 A-SAT(A) is NP-complete.

Proof: See Vilain and Kautz [1986]. 0

Next , we introduce Nebel and Biirckert's [1995] closure operation, here denoted CA(-), which transforms a given subclass of A to one that is polynomially equivalent to the original subclass wrt . satisfiability.

Definition 2.3 (Closure) Let S ~ A. Then we de­ note by CA(S) the A-closure of S, defined as the least subalgebra containing S and which is closed under con­ verse, intersection and composition. 0

Closures can be computed using Nebel and Biirckert's software [1993] .

The key result for extrapolating complexity results is the following.

Proposition 2.4 Let S ~ A. Then A-SAT(S) is polynomial iff A-SAT(CA(S)) is, and A-SAT(S) is NP­ complete iff A-SAT(CA(S)) is.

Proof: See Nebel and Biirckert [1995] . O

A-SAT is sometimes defined such that for each pair of objects (e.g. time intervals), we have exactly one rela­ tion ( cf. Golumbic and Shamir [1993]). In this way, the reduction needed for Proposition 2.4 would fail, since intervals which are added are not always related.

3 Classification of A

This section contains the parts of the classification.

3.1 Intractable Subclasses

In order to provide the classification, we need to find more NP-complete subclasses of A than those previously known. Our main tools for proving intractability are the following NP-complete subclasses of A.

Definition 3.1 (Subclasses N;, relation R, sets A0 , A4 and AN p} First define the auxiliary set A by A = {(-< d~ o m f~), (-< d o m s)} . Define the following sets.

Define the relations Rand R' by R = (d d~ o o~) and R' = (:::: m m ~ s s~ f f~), and set ANP to be the union of the following sets:

Proposition 3.2 A-SAT(S) is NP-complete for all S E ANP·

Proof: For Nt and N2, see Nebel and Biirckert [1995]. The remaining cases are proved in Theorem A.9 (Ao U A4) and Theorem A.12 (N3, N4 and N5 ) in the appendix. 0

3.2 Tractable Algebras

Next we define what are the polynomial algebras in­ volved in the classification.

Definition 3.3 (bas( A), polynomial algebras) Let bas(A) for A~ A be the set of basic relations contained in A. Also let 1l denote the ORD-Horn algebra by Nebel and Biirckert [1995] and S-<, Sd , So, £-<, £d and &o the maximal tractable algebras of Drakengren and Jons­ son [1997], where Sr denotes the unique starting point al­ gebra containing the basic relation (r) , and &r the unique ending point algebra containing the basic relation ( r) . 0

The following facts about the algebras shall be needed in the classification.

Proposition 3.4 Jl, Sr and &r are maximal tractable subclasses of A, i.e. it is impossible to extend them without losing tractability. Furthermore, any tractable subclass A ~ A with B ~ A satisfies A ~ 1i. Also, bas(Jl) = B , bas(Sr) = {=:,r,r~,s,s~}, and bas(E:r) = {=:,r,r~,f,f~} for all r E {-<,d,o} .

Proof: The proofs for 1l can be found in [Nebel and Biirckert, 1995], and those for Sr and E:r in [Drakengren and Jonsson, 1997]. 0

In order to define the subject of our classification, define T to be the set of maximal tractable subalgebras of A not included in 1i, Sr or E:r, for any r E {-<,d,o}. Note that it is sufficient to restrict the attention to maximal tractable algebras, since any tractable subset can be ex­ tended to such an algebra. Also note that some of the algebras known from the literature (those of Drakengren and Jonsson [1996, 1997]) are included in T, but this will not affect the classification, since these all contain three basic relations or less.

3.3 The Classification

We start by stating the main theorem of the paper, from which the classification results will follow. Since this kind of result has already been needed at least twice in the literature [Jonsson et al., 1996; Jonsson and Drak­ engren, 1997], we take the opportunity to abstract it in order to make future classification results easier to state.

Theorem 3.5 Let n be a set equipped with an opera­ tion Cn(R} on sets R ~ n, and for each set R ~ n a problem R-SAT(R), satisfying the following:

• If R-SAT(Cn(R)) is NP-complete, then R-SAT(R) is NP-complete
• If R-SAT(R) is NP-complete, then R-SAT(S) is NP-complete for all S 2 R
• IfR-SAT(R) is polynomial, then R-SAT(S) is polynomial for all S ~ R.

Let Rp, RNP ~ 2n and B ~ n, such that R-SAT(X) is polynomial for each X E Rp, each X E Rp satisfies B ~ X, and R-SAT(D) is NP-complete for each DE RNP·

Then if each set T ~ n with ITI ~ IRPI satisfies either that T is a subset of some set in Rp, or that D ~ Cn(TUB) for some DE nNP, then for any S with B ~ S, n-SAT(S) is polynomial iff Sis a subset of some set in Rp . Otherwise n-SAT(S) is NP-complete.

Proof:

~)For each R E Rp, R-SAT(R) is polynomial by defi­ nition, and so are subsets of R.

=>) Consider a set S ~ A with B ~ S, S not being a subset of any set in Rp . For each set C in Rp, choose an element x such that x E Sand x fl. C. This can always be done since S ~ C. Let X be the set of these elements. By the construction of X, lXI ~ IRPI · But then, by the condition of the theorem, either X is a subset of some set in Rp, or D ~ Cn(X U B) for some DE nNP· But the former case cannot hold by the construction of X; thus R-SAT(Cn(X U B)) is NP-complete. It follows that R-SAT(X U B) is NP-complete, and since X u B ~ S, that R-SAT(S) is NP-complete. The result follows. o

We now proceed gradually with the classification by ex­ cluding certain combinations of basic relations. Note that the three conditions making Theorem 3.5 applica­ ble always hold for Allen's algebra. Also note that any algebra has to contain an odd number of basic relations, since algebras are closed under the converse operation, and (::::) is always included.

The following result is similar to one of Drakengren and Jonsson [1997].

Proposition 3.6 Let A ~A. If A~ A and (m) E A,

then either A~ 1l or A-SAT(A) is NP-complete.

Proof: It can easily be verified that B ~ CA( {( m )J) (use the aclose utility by Nebel and Biirckert [1993}), and the result follows by Proposition 3.4. 0

Thus, A E T => bas(A) ~ 11.

Now for the first application of the quite abstract The­ orem 3.5.

Proposition 3. 7 Let A ~ A. If ( -<) E bas(A), then either A~ 1l, A~ S-<, A~£-<, or A-SAT(A) is NP­ complete.

Proof: First chooseR.= A, R.p = {1-l,S-<,£-<}, nNP = ANP and B = {( -<)}. Then enumerate each set T ~A with ITI ~ IR.PI = 3 and test iffor each T, either T ~ 1l, T ~ S-<, T ~£-<,or D ~ C.A(TUB) for some DE ANP·

There are L~=O ( 81 i 92 ) ~ 9.2 ·10 10 such subsets. The

test succeeds for all T, and the result follows. 0

The subsets were enumerated on several Sun SPARC 10 stations in parallel, taking approximately 40 CPU weeks.

By this result, A E T => bas(A) ~ 9. The ba­ sic relations . remaining to check are those in Z = { d, d~ , o, o~, s, s~, f, f~}. If we can show that for any r1, r2 E Z with r1 f. r2 and r1 ~ f. r2, if for some A E T, {r1, r2} ~ bas(A), then A ~ 1l, A ~ Sr or A ~ Er for some r, then we could conclude that A E T => bas(A) ~ 3, which is the goal of the paper. The following results will prove this.

Proposition 3.8 Let A ~ A. For W = {(d), (o)} or W = {(s), (f)}, .if W ~ bas(A), then either A ~ 1i, or A-SAT(A) is NP-complete.

Proof: First choose n =A, R.p = {'H}, nNP = ANP and B = W. Then enumerate each set T C A with ITI ~ IR.PI = 1 and test if for each T, eith~ T ~ 1i or D ~ C.A(T U B) for some D .E ANP· There are 8193 such subsets, regardless of W. The test succeeds for all T, and the result follows from Theorem 3.5. 0

Proposition 3.9 Let A~ A. If {(s), (r)} ~ bas(A) for r E {d,o}, then either A~ 1l, A~ Sr, or A-SAT(A) is NP-complete.

Proof: First choose R. = A, R.p = {1l, Sr}, R.N p = ANP and B = {(s), (r)}. Then enumerate each set T ~ A with ITI ~ IR.PI = 2 and test if for each T, either T ~ 1l, T ~ Sr, or D ~ C.A(T U B) for some DE ANP· There are ~ 3.4 · 10 7 such subsets. The test succeeds for all T, and the result follows from Theorem 3.5. 0

The cases with {(f), (d)} and {(f), (o)} follow by symme­ try from Proposition 3.9, using Er instead of Sr. We can thus conclude that A E T => bas(A) ~ 3, and that alge­ bras in T can only contain basic relations in { ::::, d, o, s, f} which is the main result of the paper.

We conclude by a classification of all algebras contain­ ing the relation (-< ~), needed for expressing the notion of sequentiality. This notion is important in many AI

contexts, such as planning and reasoning about action [Sandewall, 1994], where actions are often assumed to come m sequence.

Proposition 3.10 Let A ~ A . If (-< ~) E A, then either A ~ S-<, A ~ £-<,or A-SAT( A) is NP-complete. Proof: First choose n =A, R.p = {S-<,£-<}, nNP = AN p and B = { (-< ~)}. Then enumerate each set T ~ A with ITI ~ IR.p I = 2 and test if for each T, either T ~ S-<, T ~£-<,or D ~ C.A(TUB) for some DE ANP· There are~ 3.4 · 10 7 such subsets. The test succeeds for all T, and the result follows from Theorem 3.5. 0

Since both of these algebras also contain the relations (:=), ( -<), (H, (:= -<), (:= ~ ), these are the only tractable algebras capable of expressing sequentiality.

In fact, when enumerating subsets in Proposition 3.7, Proposition 3.9 and Proposition 3.10, it is possible to op­ timise by stopping at subsets known to be NP-complete (those in AN p); sometimes with a factor thirty.

4 Discussion

It is appropriate to indicate the applicability of this method to further classify tractability in A. Therefore, consider the task of classifying all tractable algebras con­ taining the basic relation (s). There are nine known max­ imal tractable algebras containing this relation. Thus, we have to enumerate all subsets of an 8192-element set having nine or fewer elements. This amounts to 4.6 ·10 29 subsets, making this task more difficult by a factor of 10 19 , which is clearly impossible using today's comput­ ers.

For the full classification, we certainly need meth­ ods that combine theoretical studies of the structure of A with brute-force computer methods, similar to how the four-colour theorem was proved [Appel and Haken, 1976].

5 Conclusion

We have partially classified tractability of reasoning in Allen's interval algebra, with the result that any yet un­ known tractable subclass can contain at most the ba­ sic relations(:=), (b), (b~), where bE {d,o,s,f}. This means that for specifying complete knowledge about temporal relations, there is no hope of finding more ex­ pressive and yet tractable subclasses than those known today. Furthermore, we completely characterise the set of tractable subclasses which can express the notion of sequentiality, which is useful in many AI contexts.

Appendix

Here the intractability proofs needed for the proof of Proposition 3.2 are coll~cted.

A.l Model Transformations

Definition A.l (Subsets ~0 and ~4 ) Let R = (d d~ o o~) as in Definition 3.1, and define ~o = {(-< ~ ), R U (:= m m~ s s~ f f~)}, and ~4 = { (-< ~), R U ( = -< m m ~ s s ~ f f~)}. 0

Proposition A.2 A-SAT(Llo) and A-SAT(Ll4 ) are NP­ complete.

Proof: See Golumbic and Shamir [1993] . 0

The NP-completeness results of Proposition A.2 can be exteded considerably by techniques introduced next .

Our main vehicle for showing intractability of differ­ ent subclasses is that of model transformations. It is a method for transforming a solution of one problem to a solution of a related problem. The concept of model transformation and related results were introduced in the context of temporal reasoning in Jonsson et a/. [1996].

Definition A.3 (Model transformation) A model transformation is a mapping on A-interpretations. 0 Next , a way to describe such transformations.

Definition A.4 (Model transformation descrip­ tion) Let T be a model transformation. A function fr : B --+ 2B is a description of T iff for arbitrary A­ interpretations~' the following holds: if bE Band I(b )J under~ then I(fr(b))J under T(~) . A description h can be extended to handle disjunctions in the obvious way: fr(R) = UreR fr(r) . 0

We can now provide a result on how model transforma­ tions can be used.

Lemma A.5 Let R = {rt, ... , rn} ~ A and R' = {r~, .. . , r~} ~ A be such that r~ ~ rk for all 1 :::; k :::; n, and A-SAT(R) is NP-complete. If there exists a model transformation T with a description fr such that fr(rk) ~ r~ for every 1 :::; k :::; n then A-SAT(R') is NP-complete.

Proof: Almost identical to one of Jonsson et a/. [1996] . 0

Before we define a model transformation that we will use later on, we need an auxiliary definition (also from Jonsson et a/. [1996]) .

Definition A.6 (Minimal distance) Let S ~ R be finite . The minimal distance in S, MD(S) , is defined as min{x-ylx,yESt\x>y} . 0

Observe that lSI ;?: 2 in order to make MD(S) defined. This is no problem, since we are working with inter­ vals. For all such S, MD(S) > 0. The definition of minimal distance can be extended to A-interpretations in the following way: Let ~ be an A-interpretation that assigns values to a set of interval variables I , and set MD(~)= MD( {~(I-), ~(J+)II E I}) .

A concrete model transformation follows .

Definition A. 7 (Transformation T, description f) Define the model transformation Ton A-interpretations assigning values to interval variables It , .. . , In as fol­ lows. T(~) = ~', where ~' is obtained from ~ by first setting f = MD(~)/(n + 1) and defining ~'(!;) = (~un- if, ~un +if) .

Then define f(b) for rEB as/(=.)= {d , d~,o , o~ }, !(-<) = {-<} , /(>-) = {>-} , f(d) = {d} , f(d~ ) = {d~} , f(o) = {o}, /(m) = {o} , /(m~) = {o~ } , f(s) = {d,o}, f(s~) = {d~,o~}, /(f)= {d,o~}, f(f~ ) = {d~,o} . 0

Thus T decreases starting points and increases ending points of intervals, and does this differently for every interval. Now f( b) represents what can happen with the basic relation b when the transformation T is applied.

Proposition A.S f is a description ofT. Proof: Obvious from the definitions. 0

We can now extend the results of Proposition A.2.

Theorem A.9 For any A E Ao U A4 of Definition 3.1, A-SAT(A) is NP-complete.

Proof: Let r1 (-< >-) and r2 R U (=: m m~ s s~ f f~), where R = (d d~ o o~ ) . Thus R = {r1, r2} =do and is NP-complete. Take A E Ao. Now A= {r~,r2} for r~ = (-<>-)and R ~ r2 ~ RU (:::: m m~ s s~ f f~) , and it is obvious that the conditions of Lemma A.5 are satisfied. NP-completeness follows .

Similarly, let r1 = (-< >-) and r2 = R U ( = -< m m~ s s~ f f~), where R = (d d~ o o~ ) . Thus R = { r 1, r 2} = Ll4 and is NP-complete. Take A E A4. Now A= {r~ , r2} for r~ =(-<>-)and R ~ r2 ~ RU(=.-< m m~ s s~ f f~), and it is obvious that the conditions of Lemma A.5 are satisfied. NP-completeness follows . 0

A.2 5-Composition

In order to find the last necessary NP-completeness re­ sults, we introduce a new operation to the Allen algebra.

Definition A.lO ( 5-composition) Let r1 , ... , rs E A . Define the 5-composition of r 1, . .. , rs, denoted 5comp(r1 , · . . ,rs), by I5comp(rt, . .. , rs)J {::} 3K, L . Ir1K , Kr2J, IraL, Lr4J, KrsL . o

The 5-composition of relations r 1, .. . , r 5 can easily be computed by using Nebel's software for computing sat­ isfiability of networks of Allen relations1, by construct­ ing a network of four interval variables with relations according to the definition, and computing the entailed relation between two of the variables by choosing the basic relations which are consistent there.

NP-completeness results can be obtained as follows.

Proposition A.ll Let A ~ A, and suppose A-SAT( AU{ 5comp(r1 , ... , rn)}) can be shown to be NP­ complete, for r; EA. Then A-SAT( A) is NP-complete.

Proof: Any network expressed using the extended set of relations can be converted to an equivalent one using only relations from A, by the definition of 5-composition. The transformation is obviously polynomial. 0

Theorem A.12 A-SAT for the subclasses Na , N4 and Ns are NP-complete.

Proof: Recall the definitions:

Na = {(-< >- ), (o o~)}, N4 = {(-< >-), (o o~ m m~)} and N5 = {(m m~) , (-< >- s s~ f f~)} . Define c(r1,r2) = 5comp(rt , rt,rt , r1 , r2)· First , we verify that r3 = c((o o~) , (-< >-)) = (=. d d~ o o~ s s~ f f~) , and we see that A ~ N3 U {r3 } for some A E

1 This software was developed for obtaining the results of Nebel's paper [1996], and can be obtained from Bernhard Nebel.

• Ao, and NP-completeness follows. Next, r4 c((o o~ m m~),(-< >-)) = (=: d d~ o o~ s s~ f f~), and we see that A ~ N4 U {r4 } for some A E Ao, and NP-completeness follows. Last, r 5 c((m m~),(-< >- ss~ ff~)) = (=: ss~ ff~), and it can be verified using Nebel and Biirckert's soft­ ware [1993] that ~o ~ CA(N5 U {r5}), implying NP­ completeness. 0