Computing the of two Normalized Spanning Intervals

 

Given an Allen relation r and two sets I and J of intervals, let denote the set K of all intervals  such that for some and , where . Given an Allen relation r and two normalized spanning intervals  and  , let denote a set of normalized spanning intervals whose extension is , where I and J are the extensions of  and  respectively. One can compute as follows:

Here, denotes the inverse relation corresponding to r, i.e. the same relation as r but with the arguments reversed. It is easy to see that . Thus an important property of normalized spanning intervals is that for any two normalized spanning intervals  and  , contains at most 4, 64, 64, 16, 16, 64, 64, 16, 16, 16, 16, 64, or 64 normalized spanning intervals, when r is =, <, >, , , , , , , , , , or  respectively. While simple combinatorial enumeration yields the above weak bounds on the number of normalized spanning intervals needed to represent , in practice, far fewer normalized spanning intervals are needed, in most cases only one.

The intuition behind the above definition is as follows. Let I and J be the extensions of  and  respectively. The extension of the set of all  is the set of all intervals  such that for some  in J. Furthermore, the extension of the set of all  is the set of all intervals  in I such that for some  in J. Similarly, the extension of the set of all  is the set of all intervals  such that for some  in I. Analogously, the extension of the set of all  is the set of all intervals  in J such that for some  in I. Thus the extension of the set of all is the set of all intervals  such that where  is in I, is in J, and .