Tech Report CS-93-24

Exploiting Locality in Temporal Reasoning

Shieu-Hong Lin and Thomas Dean

June 1993


Temporal reasoning with uncertainty about the ordering of events is important in a wide variety of applications. Previous research shows that the associated decision problems are hard even for very restricted cases. In this paper, we investigate using the temporal locality of events and the spatial locality of state spaces to speed inference. We propose a new perspective for representing cause-and-effect relationships based on finite state automata. This perspective exposes the sources of complexity in temporal reasoning more clearly, and facilitates transforming rule-based temporal reasoning problems into graph reachability problems. We present both positive and negative results that provide insight into the complexity of temporal reasoning.

(complete text in pdf or gzipped postscript)