wpu.nu

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

Från wpu.nu

Den här sidan har inte korrekturlästs


From the transitivity tables, we find:

T(0,0) = ( o m) T(0,5) = (0) T(mo) = () T(ms) = (m)

Thus the inferred constraint between S and R is

S--(om) R.

Intersecting this with our previous constraint between S and R yields

S--(< m)- R. With respect to the example story, this is equivalent to inferring that John entered the room (i.e., R started) either after I touched the switch or at the same time that I finished touching the switch. Thus the new betwork is: R+(< m-- S --o m) - L

1

-(o )------- Of course, if there were other nodes in the network, there would be other constraints derived from this new information. Thus, if we added a new interval D, say with the constraint D --(d)→ S, we would in fer the following new relationships as well:

D --<)→ R

T

D-(omd s) → L.

IV.3. Analysis

A nice property of this algorithm is that it only continues to operate as long as il is producing new further constrained relationships between intervals. Since there are at most thirteen possible relationships that could hold belween two intervals, there are at most thirteen steps that could modify this relationship. Thus for a fixed number of nodes N, the upper limit on the number of modifications that can be made, irrespective of how many constraints are added to the network, is 13 x the number of binary relations between N nodes, which is:

13 x (N

x (N-1)(N-2)

(N-2)

Thus, in practice, if we add approximately the same number of constraints as we have nodes, the average amount of work for each addition is essentially linear (i.e., N additions take O(N2) time; one addition on average lakes O(N) time).

The major problem with this algorithm is the space requirement. Il requires O(N2) space for N temporal intervals. Methods for controlling the propagation, saving time and space, will be discussed in the next section.