wpu.nu

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

Från wpu.nu

Den här sidan har inte korrekturlästs


Figure 67

The algorithm to add relations using reference intervals is identical to the previous addition algorithm except that the comparability condition is no longer universally true. For any node N, let Refs(N) return the set of reference intervals for N. For any two nodes K and' ], Comparable(K, J) is true if

1) Refs(K) n Refs(I) is not null, i.e., they share a reference interval;

or 2) K € Refs(J); or 3) Je Refs(K).

Since reference intervals are simply intervals themselves, they may in tur have their own reference intervals, possibly defining a hierarchy of clusters. In most of the usefUL applications that we have seen, these hierarchies are typically tree-like as depicted in Figure 7.

<Figure 7

If two intervals are not explicitly related in the network, a relationship can be retrieved by finding a path between them through the reference intervals by searching up the reference hierarchy until a path (or all paths) between the two nodes are found. Then, by simply applying the transitivity relationships along the path, a relationship between the two nodes can be inferred. If one is carefUL about structuring the reference hierarchy, this can be done with little loss of information from the original complete propagation scheme.

To find a relationship between two nodes I and J, where N(ij) represents the network relation between nodes i and j as in Section IV.1, we use the algorithm:

If N(1,5) exists then return N(I,J) else do Paths :=

Find-Paths(1,3) For each path in Paths do

R := Rn Constrain-along-path(path) return R; end;

The function Find-Paths does a straightforward graph search for a palh belween the two nodes with the restriction that each step of the path must be belween a node and one of its reference intervals except for the one case where a direct connection is found. Thus a path is of the general form

am

ոլ, որ, nk nk+1) where all of the following hold: