Publication Details
Title: Temporal Resoning with Intervals in Branching Time
Author: P. B. Ladkin, F. D. Anger, and R. V. Rodriguez
Group: ICSI Technical Reports
Date: July 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-028.pdf
Overview:
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 Information:
ICSI Technical Report TR-90-028
Bibliographic Reference:
P. B. Ladkin, F. D. Anger, and R. V. Rodriguez. Temporal Resoning with Intervals in Branching Time. ICSI Technical Report TR-90-028, July 1990
Author: P. B. Ladkin, F. D. Anger, and R. V. Rodriguez
Group: ICSI Technical Reports
Date: July 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-028.pdf
Overview:
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 Information:
ICSI Technical Report TR-90-028
Bibliographic Reference:
P. B. Ladkin, F. D. Anger, and R. V. Rodriguez. Temporal Resoning with Intervals in Branching Time. ICSI Technical Report TR-90-028, July 1990