Qualitative Temporal Reasoning about Vague Events

1 Introduction

A substantial part of the work on temporal reasoning is concerned with qualitative time information. In many application domains - typically in the realm of natural language processing (NLP) and understanding - we may not know when events took place, while interesting conclusions could still be drawn from the available qualitative information. Other applications use qualitative temporal information to constrain possible scenarios, specifying for example that some task should only start after another task has been completed.

In [Allen, 1983], Allen introduced a framework for representing qualitative relations between intervals, which has been adopted in the majority of the work on qualitative temporal reasoning ever since. Unfortunately, most interesting reasoning tasks in this framework are NP-complete [Vilain et al., 1989]. Therefore, a lot of work has been done to identify maximal subsets of the 213 interval relations introduced by Allen, for which reasoning is tractable [Drakengren and Jonsson, 1997a; 1997b; Krokhin et al., 2003; Nebel and B¨urckert, 1995]. Another highly relevant line of research is the characterization of tractable problem instances for constraint satisfaction problems [Gottlob et al., 2000], and in particular the design of efficient solution techniques for disjunctive temporal reasoning problems [Bosch et al., 2002; Stergiou and Koubarakis, 2000; Tsamardinos and Pollack, 2003].

One assumption that is implicitly made in all but a few approaches to qualitative temporal reasoning is that the temporal boundaries of events are always well-defined, i.e., that for every event there exist precise time instants corresponding to its beginning and ending. On the other hand, it is well-known that real-world events often have vague temporal boundaries [Varzi, 2002]. This is particularly true for historical events, e.g., the Cold War, the Great Depression, the Russian Revolution, the Dotcom Bubble, . . .This observation is significant for qualitative temporal reasoning, because qualitative relations between events with vague temporal boundaries, are vague as well.

A popular technique to address the vagueness of events is to represent their time span as a fuzzy set [Zadeh, 1965] in R, i.e., as a mapping A from the real line R to the unit interval [0, 1]. In this approach, time instants are represented as real numbers; for every d in R, A(d) is called the membership degree of d in A, and represents the degree to which the event corresponding with A was happening at instant d. For example, in Figure 1, a possible representation of the time span of the Dotcom Bubble is shown. According to this representation, the Dotcom Bubble definitely encompasses the time instants between 1999 and 2001, hence their membership degree is 1. Similarly, time instants before 1996 and after 2002 are definitely not during the Dotcom Bubble, hence their membership degree is 0. The remaining time instants can be seen as borderline cases, which neither belong fully to the temporal extension nor to the temporal anti-extension of the Dotcom Bubble.

In this paper we show how the problem of reasoning with qualitative relations between fuzzy time intervals can be reduced to reasoning in a point algebra with disjunctions [Broxvall and Jonsson, 2003]. In this way, efficient techniques that have been developed in the context of disjunctive temporal reasoning, can be used to decide, for example, the satisfiability of a set of qualitative relations between fuzzy time intervals. Furthermore, we show how entailment checking and calculating the best truth value bound can be reduced to satisfiability checking. To the best of our knowledge, this is the first paper in which complete procedures for qualitative temporal reasoning about vague events are provided. Finally, we show that deciding satisfiability is NP-complete, and provide a maximal tractable subset of qualitative relations 1 .

2 Related work

Vagueness has many faces, requiring different techniques in different contexts. Most work on vague temporal knowledge deals with situations where events have precise boundaries, but where our knowledge about them is vague, e.g., "A started in the early summer of 2004", or "A happened about 3 hours after B". This kind of vagueness, which is purely epistemic, is usually modelled in the framework of possibility theory [Dubois and Prade, 1989; Godo and Vila, 1995]. In [Dubois et al., 2003], an extension of Allen's interval algebra is introduced to cope with statements like "A happened long before B". To support reasoning, a composition table is introduced, but, unfortunately, reasoning with this composition table is not shown to be complete. In [Badaloni and Giacomin, 2006], fuzzy sets of basic Allen relations, i.e. mappings from the 13 basic interval relations to the unit interval [0,1], are considered to represent preferences. Interestingly, all main reasoning tasks are shown to be NP-complete, and a maximal tractable subalgebra is identified. Fuzzy sets of basic Allen relations have also been considered in [Guesgen et al., 1994].

However, in all these approaches, it is assumed that events have precise, albeit unknown, temporal boundaries. As explained in the introduction, even in the face of complete knowledge, our temporal knowledge about events may be affected by vagueness. Several generalizations of Allen's interval relations to represent qualitative relations between fuzzy time intervals have already been proposed [Nagyp´al and Motik, 2003; Ohlbach, 2004; Schockaert et al., 2006b], similar in spirit to measures for comparing and ranking fuzzy numbers [Dubois and Prade, 1983; Bodenhofer, 1999]. Moreover, the necessity of dealing with vague events and time periods has been pointed out in various contexts, including semantic web reasoning [Bry et al., 2003], representing historical information in ontologies [Nagyp´al and Motik, 2003], interpreting temporal expressions in business news documents [Kalczynski and Chou, 2005], and temporal question answering [Schockaert et al., 2006a]. The issue of reasoning with qualitative relations between fuzzy time intervals has only been addressed in [Schockaert et al., 2006a], where a sound but incomplete algorithm is introduced to find consequences of a given, limited set of assertions. In this paper, we provide a general framework for qualitative temporal reasoning about vague events, provide complete reasoning procedures, and identify a maximal tractable subset of qualitative temporal relations.

1 Throughout this paper, we assume P ̸= NP.

3 Preliminaries

3.1 Fuzzy temporal constraints

We will represent the time span of an event as a fuzzy set in R, i.e., as a mapping A fromR to [0, 1]. For clarity, traditional sets are sometimes called crisp sets in the context of fuzzy set theory. For every α in ]0, 1], we let Aα denote the subset of R defined by

Aα is called the α-level set of the fuzzy set A. In particular, A1 is the set of instants (real numbers) that fully belong to the time span of the event under consideration. To adequately generalize the notion of a time interval, some natural restrictions on the the α-level sets are typically imposed.

Definition 1 (Fuzzy time interval) [Schockaert et al., 2006b] A fuzzy (time) interval is a mapping A from R to [0, 1], such that for every α in ]0, 1], Aα is a (non-degenerate) closed interval.

For a fuzzy interval A and α ∈]0, 1], we let A-α and A+α denote the beginning and ending of the interval Aα.

When the time spans of events are vague, then also the qualitative temporal relations between them are a matter of degree. Traditionally, qualitative relations between time intervals are defined by means of constraints on the boundary points of these intervals. For fuzzy time intervals, a different approach must be adopted. However, note that for crisp intervals [a-, a+] and [b-, b+], we have that a- < b- is equivalent to:

Let A and B be fuzzy time intervals. The degree bb≪(A, B) to which the beginning of A is before the beginning of B can be expressed as [Schockaert et al., 2006b]:

where TW and IW are defined for every a and b in [0, 1] by

and L≪ is the characteristic mapping of <, i.e., L≪(x, y) = 1 if x < y and L≪(x, y) = 0 otherwise. Note that the definition of bb≪ is a generalization of (1), where ∀ and ∃ have been generalized by the infimum and supremum. To generalize logical conjunction and implication, large classes of [0, 1]2-[0, 1] mappings, called t-norms and implicators resp., may be used. However, it has been shown in [Schockaert et al., 2006b] that the particular choice of TW and IW leads to many interesting properties. In the same way, we can express the degree ee≪(A, B) to which the end of A is before the end of B, the degree be≪(A,B) to which the beginning of A is before the end of B and the degree eb≪(A,B) to which the end of A is before the beginning of B as:

Finally, the degree bb≼(A, B) to which the beginning of A is before or at the same time as the beginning of B is defined by

and analogously for ee≼(A, B), be≼(A, B) and eb≼(A, B).

3.2 A point algebra with disjunctions

In [Broxvall and Jonsson, 2003], a point algebra extended with disjunctions is introduced, in which formulas like

can be expressed. Formulas such as (2) are used to express constraints on (unknown) time instants. In general, we define a P-formula over a set of variables X as an expression of the form (r1 ∨ r2 ∨ · · · ∨ rn)(x1, x2, . . . , x2n) where ri (i ∈ {1, 2, . . . , n}) is either <,≤,= or ̸=, and x1, x2, . . . , xn ∈ X. We will call an expression of the form r1 ∨ r2 ∨ · · · ∨ rn a P-relation. Furthermore, we will refer to a P-interpretation over X as a mapping from X to R. A P-interpretation I over X satisfies (<)(x, y) iff I(x) < I(y), satisfies (≤)(x, y) iff I(x) ≤ I(y), etc. Furthermore, I satisfies a P-formula like (2) iff I satisfies (<)(x1, x2), or I satisfies (≤)(x3, x4), or I satisfies (=)(x5, x6). A set Ψ of P-formulas over a set of variables X is said to be P-satisfiable if there exists a Pinterpretation over X that satisfies every P-formula in Ψ. A P-interpretation meeting this requirement is called a P-model of Ψ.

4 Amotivating example

In many NLP tasks, an ordering of events occurring in documents has to be identified. Such an ordering is useful, for example, for automatic text summarization, or to support question answering. As a motivating example, we consider the task of summarizing a set of documents related to recent trends in economy, in particular the Dotcom Bubble 2 and the British Property Bubble 3 (a recent real estate bubble in Great Britain). From these documents, we learn that the British Property Bubble has existed since 1998 and that the Dotcom Bubble ended around 2001. Let [x-dc , x+dc ] denote the time span of the Dotcom Bubble, and [x-bpb , x+bpb ] the time span of the British Property Bubble, then we can establish from these facts the following P-formula:

On the other hand, the document about the British Property Bubble also states as one of its reasons:

A falling stock market, especially after the dot-com bubble, feeding into a general lack of confidence in the stock market.

Let [x-fsm, x+fsm] be the time span of the fall of the stock market, then we can represent this as

2 http://en.wikipedia.org/wiki/Dotcom bubble, accessed June 16, 2006

3 http://en.wikipedia.org/wiki/British property bubble, accessed June 16, 2006

However, this set of P-formulas is inconsistent, because it allows to deduce the following cycle:

In the traditional framework, where the temporal boundaries of events are assumed to be crisp, the only way out seems to be to reject some of the information, such that the remaining set of P-formulas is consistent.

However, it is clear that the real cause of this inconsistency is not the presence of false information, but the vagueness of the events involved. Rather than modelling the time spans of these events as intervals, we should acknowledge that these time spans may be fuzzy. The knowledge extracted from the documents may then be represented by stating that the fuzzy time intervals Xdc, Xbpb and Xfsm, whatever their exact definition is, should satisfy

where α, β ∈]0, 1]. Initially, we may assume that α = β = 1, i.e., we assume that the fall of the stock market was fully before the British Property Bubble, and that the end of the Dotcom Bubble was fully before the end of the fall of the stock market. Since this again leads to inconsistency, we may weaken these interpretations by lowering the value of α and/or β. It is of interest to find maximal values for α and β that lead to a consistent representation, in the same way that traditionally, we are interested in maximal consistent subsets of assertions.

5 Temporal reasoning about vague events

5.1 Temporal relations between vague events

We will define qualitative relations between fuzzy intervals as upper and lower bounds for the measures bb≪, bb≼, ee≪, ee≼, be≪, be≼, eb≪ and eb≼ introduced in Section 3.1. In the remainder of this paper, we will assume that all these upper and lower bounds are taken from a fixed set M = {0,Δ, 2Δ, . . . , 1}, where Δ = 1ρ for some ρ ∈ N \ {0}. For convenience, we will write M0 for M \ {0} and M1 for M \ {1}.

Definition 2 (Basic FI-relation) A basic FI-relation is an expression of the form bb≪≤k , bb≪≥l , bb≼≤k , bb≼≥l , ee≪≤k , ee≪≥l , ee≼≤k , ee≼≥l , be≪≤k , be≪≥l , be≼≤k , be≼≥l , eb≪≤k , eb≪≥l , eb≼≤k or eb≼≥l , where k ∈ M1 and l ∈ M0.

Definition 3 (FI-relation) A FI-relation is an expression of the form

where r1, r2, . . . , rn are basic FI-relations; n is called the complexity of the FI-relation. The set of all FI-relations is denoted by F.

Definition 4 (FI-formula) A FI-formula over a set of variables X is an expression of the form

where r is an FI-relation of complexity n, and x1, x2, . . . , x2n are variables from X.

Definition 5 (FI-interpretation) A FI-interpretation over a set of variables X is a mapping that assigns a fuzzy interval to each variable in X. An FIM-interpretation over X is an FI-interpretation that maps every variable from X to a fuzzy interval that takes only membership degrees fromM.

A FI-interpretation I over X satisfies the temporal formula bb≪≥l (x, y) (x, y ∈ X, l ∈ M0) iff bb≪(I(x), I(y)) ≥ l, and analogously for other types of basic temporal formulas. Furthermore, I satisfies (r1 ∨r2 ∨ · · · ∨rn)(x1, x2, . . . , x2n) iff I satisfies r1(x1, x2) or I satisfies r2(x3, x4) or . . . or I satisfies rn(x2n-1, x2n).

Definition 6 (FI-satisfiable) A set Θ of FI-formulas over a set of variables X is said to be FI-satisfiable if there exists an FI-interpretation I over X that satisfies every FI-formula in Θ. A FI-interpretation I meeting this requirement is called an FI-model of Θ. If there exists an FIM-interpretation over X that satisfies every FI-formula in Θ, Θ is called FIMsatisfiable.

5.2 FI-satisfiability

To decide if a set of FI-formulas Θ is FI-satisfiable, we will reduce this problem to the satisfiability problem in the point algebra with disjunctions described in Section 3.2. This reduction is made possible by virtue of the following proposition, stating that if the upper and lower bounds in a set of formulas are taken from the set M, as defined above, then we can restrict ourselves to fuzzy intervals that only take membership degrees fromM.

Proposition 1 Let Θ be a set of FI-formulas over X. It holds that Θ is FI-satisfiable iff Θ is FIM-satisfiable.

The following proposition provides a correspondence between FI-relations and P-relations that will be fundamental in reducing FI-satisfiability to P-satisfiability

Proposition 2 Let A and B be fuzzy intervals that only take membership degrees fromM, k ∈ M1 and l ∈ M0. It holds that:

Let Θ be a set of FI-formulas over a set of variables X. From this, we will construct a set of variables X ′ and a set of Pformulas Ψ over X ′ such that Θ is FI-satisfiable iff Ψ is Psatisfiable. From Proposition 1, we know that we can restrict ourselves to fuzzy intervals that only take membership degrees from M. The intuition behind the reduction process is that such a fuzzy interval A is completely characterized by the set of intervals {AΔ,A2Δ, . . . ,A1}, which is in turn completely characterized by the set of instants (real numbers) {A-Δ,A-2Δ, . . . ,A-1 ,A+1 , . . . ,A+2Δ,A+Δ}.

Let X ′ and Ψ initially be the empty set. For each variable x in X, we add the new variables x-Δ, x-2Δ, . . . , x-1 , x+1 , . . . , x+2Δ and x+Δ to X ′ , and add the Pformula (<)(x-1 , x+1 ) to Ψ. Furthermore, for each k in M1, we add the following P-formulas to Ψ:

This ensures that for every P-interpretation I ′ over X ′ that satisfies Ψ, there exists a (unique) FI-interpretation I over X defined for every x in X by

for every l in M0. Conversely, for every FI-interpretation I over X, (3) defines a (unique) P-interpretation I ′ over X ′ that satisfies Ψ.

Finally, for each FI-formula in Θ, we add a corresponding set of P-formulas to Ψ, based on the equivalences of Proposition 2. For example, assume that Θ contains the FIformula (bb≼≤k )(x, y) (k ∈ M1, x, y ∈ X). Since for all fuzzy intervals A and B, it holds that bb≼(A,B) ≤ k ⇔ 1 - bb≪(B,A) ≤ k ⇔ bb≪(B,A) ≥ 1 - k, we have that any FI-interpretation satisfies (bb≼≤k )(x, y) iff it satisfies (bb≪≥1-k )(y, x). From Proposition 2, it follows that any FIinterpretation I of X will satisfy (bb≪≥1-k )(y, x) iff the corresponding P-interpretation I ′ satisfies the P-formula

Therefore, (4) is added to Ψ. For other FI-formulas, we obtain P-formulas in a similar way. Thus we can reduce the problem of deciding FI-satisfiability of Θ to the problem of deciding P-satisfiability of Ψ in a polynomial amount of time. The following proposition expresses that this reduction is sound and complete.

Proposition 3 Let Θ be a set of FI-formulas over X, and let Ψ be the corresponding set of P-formulas, obtained by the procedure outlined above. It holds that Θ is FI-satisfiable iff Ψ is P-satisfiable.

5.3 Computational complexity

Let A be a subset of F, the set of all FI-relations. We call FISAT(A) the problem of deciding whether a set of FI-formulas involving only FI-relations from A, is FIsatisfiable. Deciding the satisfiability of a set of P-formulas is NP-complete [Broxvall and Jonsson, 2003], hence, since deciding FI-satisfiability can be polynomially reduced to deciding P-satisfiability, FISAT(A) is in NP for every A ⊆ F. As will become clear below, FISAT(F) is also NP-hard, and thus NP-complete. However, deciding the satisfiability of a set of P-formulas without disjunctions is tractable [Vilain et al., 1989]. From Proposition 2, it follows that a significant subset of the FI-relations corresponds to P-relations without disjunctions. We will refer to this subset as Ft. It holds that

From the tractability of the satisfiability of P-formulas without disjunctions, we immediately obtain that FISAT(Ft) is tractable. To show that Ft is a maximal tractable subset of F, it is sufficient to prove that for any FI-relation r in F \ Ft, FISAT(Ft ∪ {r}) is NP-hard. For every r in F \ Ft, we can show that 3SAT can be polynomially reduced to FISAT(Ft ∪ {r}), obtaining the following proposition.

Proposition 4 Ft is a maximal tractable subset of F, i.e., FISAT(Ft) is tractable, and for any r in F \ Ft, FISAT(Ft ∪ {r}) is NP-complete.

5.4 Entailment and BTVB

Let Θ be a set of FI-formulas over X, and γ an FI-formula over X. We say that Θ entails γ, written Θ |= γ, iff every FI-model of Θ is also an FI-model of {γ}. The notion of entailment is important for applications, because it allows to draw conclusions that are not explicitly contained in an initial set of assertions. We will restrict ourselves to the case where only FI-relations from Ft are used, and, in particular, show that the tractability of Ft w.r.t. satisfiability checking carries over to entailment checking. To show how entailment for a particular Θ and a basic FI-relation r can be reduced to deciding FI-satisfiability, we first define a mapping neg from basic FI-relations to basic FI-relations, defined as (k ∈ M1, l ∈ M0)

and analogous for the other basic FI-relations.

Proposition 5 Let Θ be a set of FI-formulas over X, involving only FI-relations from Ft, and r a basic FI-relation. It holds that Θ |= r(x, y) iff Θ ∪ {neg(r)(x, y)} is not FIsatisfiable.

Corollary 1 Deciding whether Θ |= r(x, y) holds for a basic FI-relation r and a set Θ of FI-formulas involving only FI-relations from Ft, is tractable.

Another reasoning task that is of interest to practical applications is finding the Best Truth Value Bound (BTVB), a notion we borrow from fuzzy description logics [Straccia, 2001]. In the following discussion, we will restrict ourselves to the measure bb≼; for bb≪, ee≼, ee≪, be≼, be≪, eb≼ and eb≪ entirely analogous results can be obtained.

The idea is that we want to find the best upper and lower bound for bb≼(I(x), I(y)) over all FI-models I of a set of FI-formulas Θ. In other words, if x and y represent the (unknown) time span of the events ex and ey, then we want to establish the strongest possible bounds on the degree to which the beginning of ex is before or at the same time as the beginning of ey, given that the temporal relations in Θ are satisfied. Formally, we want to obtain the value of lubbb≼((x, y);Θ) and glbbb≼((x, y); Θ), defined by

where mod(Θ) is the set of all FI-models of Θ. The following proposition enables us to solve the BTVB problem by checking a constant number of entailments.

Proposition 6 Let Θ be a set of FI-formulas over X, involving only FI-relations from Ft, and x, y ∈ X. It holds that the supremum in lubbb≼((x, y);Θ) and the infimum in glbbb≼((x, y); Θ) are attained for some m in M.

Hence, given the conditions from Proposition 6, we obtain

Corollary 2 Calculating the best truth value bound w.r.t. a set Θ of FI-formulas involving only FI-relations from Ft, is tractable.

6 Concluding remarks

We have shown how qualitative reasoning about vague events can be reduced to reasoning in a well-known point algebra with disjuntions, thus obtaining sound and complete procedures for several interesting reasoning tasks. Reasoning about vague events is shown to be NP-complete. An important advantage of our approach is that we can draw upon wellestablished results for solving disjunctive temporal reasoning problems. For example, in [Tsamardinos and Pollack, 2003], techniques such as conflict-directed backjumping and no-good search are used to solve disjunctive temporal reasoning problems more efficiently. These techniques can easily be adapted to solve the reasoning tasks discussed in this paper.

To support tractable reasoning, we have identified a maximal tractable subset of qualitative relations. This is an important result, as we believe that the relations in this subset are sufficient for many applications. An interesting direction for future work, however, is to identify particular classes of tractable problem instances, e.g., based on decomposition methods for constraint satisfaction problems (e.g., [Gottlob et al., 2000]). Such classes may involve relations that are not contained in the maximal tractable subset identified in this paper, by imposing restrictions on the variables the relations can be applied to.