Temporal Resoning with Intervals in Branching Time

TitleTemporal Resoning with Intervals in Branching Time
Publication TypeTechnical Report
Year of Publication1990
AuthorsLadkin, P., Anger F. D., & Rodriguez R. V.
Other Numbers592

Allen [ALLE83] adapted path-consistency techniques [MACK77] to heuristic reasoning concerning intervals over linear time, by calculating the composition table of binary relations on intervals, and using it in the path-consistency algorithm. We consider here a model of branching time which is dense, unbounded, future branching, without rejoining branches. The algorithm in [ALLE83] works directly with branching-time intervals, provided only that the composition table of the binary branching-time interval relations is used instead of Allen's table [LADK88]. Here we calculate the composition table which has to be used, which is considerably more complex than the table for linear-time intervals. This provides a heuristic, cubic-time algorithm for reasoning with branch-time intervals.

Bibliographic Notes

ICSI Technical Report TR-90-028

Abbreviated Authors

P. B. Ladkin, F. D. Anger, and R. V. Rodriguez

ICSI Publication Type

Technical Report