Temporal Resoning with Intervals in Branching Time
Title | Temporal Resoning with Intervals in Branching Time |
Publication Type | Technical Report |
Year of Publication | 1990 |
Authors | Ladkin, P., Anger F. D., & Rodriguez R. V. |
Other Numbers | 592 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-90-028.pdf |
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 |