wpu.nu

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

Från wpu.nu

Den här sidan har inte korrekturlästs


܀

The precise algorithm is as follows: assume for any temporal relation names rl and 12 that T(r1,12) is the entry in the transitivity table in Figure 4. Let Rl and R2 be arc labels, assume the usual set operations (n for intersection, U for union, C for proper subset), and let & be the empty set. Then constraints(R1, R2) is the transitivity function for lists of relation games (i.e., arc labels), and is defined by:

Constraints(R1, R2)

CHE, For each rl in RI For each r2 in R2

C + CUT(rl, r2);

Return C; Assume we have a queue data structure named ToDo with the appropriate queue operations defined. For any two intervals ij, let N(ij) be the relations on the arc between i and j in the network, and let R(ij) be the new relation between i and j to be added to the network. Then we have the following algorithm for updating the temporal network:

To Add R(1)

Add <ij) to queue ToDo; While ToDo is not empty do begin

Get next (ij) from queue ToDo, Nij) + R(ij); For each node k such that comparable(k.) do begin

R(k,]) + N(k,j) n Constraints(N(ki), R(ij)) If R(ki) C N(k, :)

then add <k, i to ToDo; end For each node k such that Comparablelik) do begin

R(sk) + N(i,k) n Constraints(R(1), NC,k)) If Rijk) C N(k, 1)

then add <ik> to ToDo; end end;

We have used the predicate Comparable(ij) above which will be defined in Section V. For the present, we can assume it always returns true for any pair of nodes.

IV.2. An Example

Consider a simple example of this algorithm in operation. Assume we are given the facts:

S overlaps or meets L S is before, meels, is met by, or after R.