wpu.nu

Sida:Ann-1983 JBC25001-00 James Allen - Maintaining knowledge about temporal intervals.pdf/8

Från wpu.nu

Den här sidan har inte korrekturlästs


We saw above five relations that can hold between intervals. Further subdividing the during relation, however, provides a better computational model. Considering the inverses of these relations, there are a total of thirteen ways in which an ordered pair of intervals can be related. These are shown in Figure

<Figure 2>

Sometimes it is convenient to collapse the three during relations (d, s, 1) into one relationship called dur, and the three containment relations (di, si, fi) into one relationship called con. After a quick inspection, it is easy to see that these thirteen relationships can be used to express any relationship that can hold between two intervals.

The relationships between intervals are maintained in a network where the nodes represent individual intervals. Each arc is labelled to indicate the possible relationship between the two intervals represented by its nodes. In cases where there is uncertainty about the relationship, all possible cases are entered on the arc. Nole that since the thirteen possible relationships are mutually exclusive, there is no ambiguity in this notation. Figure 3 contains some examples of the notation. Throughout let N; be the node representing interval i. Notice that the third set of conditions describes disjoint intervals.

<Figure 3) Throughout this paper, both the above notations will be used for the sake of readability. In general, if the arc asserts more than one possible relationship, the network form will be used, and in the case where only one relationship is possible, the relation form will be used.

For the present, we shall assume that the network always maintains complete information about how its intervals could be related. When a new interval relation is entered, all consequences are computed. This is done by computing the transitive closure of the temporal relations as follows: the new fact adds a constraint about how its two intervals could be related, which may in turn introduce new constraints between other intervals through the transitivity rules governing the temporal relationships. For instance, if the fact that i is during j is added, and j is before k, then it is inferred that i must be before k. This new fact is then added to the network in an identical fashion, possibly introducing further constraints on the relationship between other intervals. The transitivity relations are summarized in Figure 4.

<Figure >

This fact was pointed out to me by Marc Vilain and was first utilized in his system (Vilain, 1982).