(PDF) Marc Vilain, Henry Kautz, and Peter van Beek. Constraint propagation algorithms for temporal reasoning: A revised report. In Readings in Qualitative Reasoning about Physical Systems, Daniel S. Weld and Johan de Kleer (eds.), Morgan-Kaufman, 373-381, 1989.
This paper revises and expands upon a paper presented by two of the present authors at AAAI 1986 (Vilain & Kautz 1986). As with the original, this revised document considers computational aspects of interval-based and point-based temporal representations. Computing the consequences of temporal assertions is shown to be computationally intractable in the interval-based representation, but not in the point-based one. However, a fragment of the interval language can be expressed using the point language and benefits from the tractability of the latter. The present paper departs from the original primarily in correcting claims made there about the point algebra, and in presenting some closely related results of van Beek (1989).