Reasoning with Sequences of Intervals for Efficient Constraint Propagation

Traditional interval reasoning assumes that all events pick out convex intervals. We are extending this model by allowing events to take place over sequences of convex intervals. This allows for a more natural treatment of the part-whole structure underlying such entities as an interrupted event or an event that consists of several stages. More significantly, we find that this extension results in a more efficient method for propagating temporal information. This supports the contention that combining nontemporal, domain-specific information with temporal information will tend to improve the efficiency of the temporal reasoning process. 1 INTRODUCTION It has been noted by Allen [1] and Williamson and Hanks [7], among others, that combining nontemporal, domain-specific information with temporal information will tend to improve the efficiency of the temporal reasoning process. This paper supports this contention by demonstrating rigorously that adding information to the effect that a co..