Next: Computing the of two Up: An Efficient Representation and Previous: Computing the Span of

## Computing the of a Normalized Spanning Interval

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

An important property of normalized spanning intervals is that for any normalized spanning interval  , contains at most 1, 4, 4, 2, 2, 4, 4, 2, 2, 2, 2, 4, or 4 normalized spanning intervals when r is =, <, >, , , , , , , , , , or  respectively. In practice, however, fewer normalized spanning intervals are needed, often only one.

The intuition behind the above definition is as follows. Let us handle each of the cases separately.

r=<
For any intervals  and  in the extensions of  and  respectively we want . From (2) we get . Furthermore, from (14) we get . Combining these we get . In this case, both  and  are free indicating that either endpoint of  can be open or closed.
r=>
For any intervals  and  in the extensions of  and  respectively we want . From (3) we get . Furthermore, from (14) we get . Combining these we get . In this case, both  and  are free indicating that either endpoint of  can be open or closed.
For any intervals  and  in the extensions of  and  respectively we want . From (4) we get and . Furthermore, from (14) we get . Combining these we get and . In this case, only  is free indicating that the upper endpoint of  can be open or closed.
For any intervals  and  in the extensions of  and  respectively we want . From (5) we get and . Furthermore, from (14) we get . Combining these we get and . In this case, only  is free indicating that the lower endpoint of  can be open or closed.
For any intervals  and  in the extensions of  and  respectively we want . From (6) we get . Furthermore, from (14) we get and . Combining these we get and . In this case, both  and  are free indicating that either endpoint of  can be open or closed.
For any intervals  and  in the extensions of  and  respectively we want . From (7) we get . Furthermore, from (14) we get and . Combining these we get and . In this case, both  and  are free indicating that either endpoint of  can be open or closed.
For any intervals  and  in the extensions of  and  respectively we want . From (8) we get , , and . Furthermore, from (14) we get and . Combining these we get , , and . In this case, only  is free indicating that the upper endpoint of  can be open or closed.
For any intervals  and  in the extensions of  and  respectively we want . From (9) we get , , and . Furthermore, from (14) we get and . Combining these we get , , and . In this case, only  is free indicating that the upper endpoint of  can be open or closed.
For any intervals  and  in the extensions of  and  respectively we want . From (10) we get , , and . Furthermore, from (14) we get and . Combining these we get , , and . In this case, only  is free indicating that the lower endpoint of  can be open or closed.
For any intervals  and  in the extensions of  and  respectively we want . From (11) we get , , and . Furthermore, from (14) we get and . Combining these we get , , and . In this case, only  is free indicating that the lower endpoint of  can be open or closed.
For any intervals  and  in the extensions of  and  respectively we want . From (12) we get and . Furthermore, from (14) we get and . Combining these we get and . In this case, both  and  are free indicating that either endpoint of  can be open or closed.
For any intervals  and  in the extensions of  and  respectively we want . From (13) we get and . Furthermore, from (14) we get and . Combining these we get and . In this case, both  and  are free indicating that either endpoint of  can be open or closed.

Next: Computing the of two Up: An Efficient Representation and Previous: Computing the Span of

Jeffrey Mark Siskind
Wed Aug 1 19:08:09 EDT 2001