Constraint Reasoning With Intervals: A Tutorial, Survey and Bibliography

TitleConstraint Reasoning With Intervals: A Tutorial, Survey and Bibliography
Publication TypeTechnical Report
Year of Publication1990
AuthorsLadkin, P.
Other Numbers623

A version of this work was presented at the 1990 Berkeley Workshop on Temporal and Real-Time Specification, held at ICSI, Berkeley. In Part I, we present a short tutorial on constraint reasoning with time intervals, of the sort initially introduced by James Allen, and continued by many others. The tutorial concentrates on the general mathematical expression of common algorithms, in particular path-consistency algorithms, for constraint satisfaction using the thirteen interval relations. We use the relation algebra of Tarski to express the important concepts. In Part II, we survey important research in this field to date, focusing on mathematical results and algorithms for reasoning directly with intervals, although we do attempt to include as much literature as the author is aware of. Part III is a select bibliography. Three appendices include the mathematical background, and the operation tables for the Point Algebra and Interval Algebra, which form the focus of Part I.

Bibliographic Notes

ICSI Technical Report TR-90-059

Abbreviated Authors

P. B. Ladkin

ICSI Publication Type

Technical Report