(PDF) Peter van Beek. Exact and approximate reasoning about qualitative temporal relations.
PhD thesis, University of Waterloo, Department of Computer Science, 1990.


Much temporal information is qualitative information such as ``The Cuban Missile crisis took place during Kennedy's presidency,'' where only the ordering of the end points of the two events is specified. A point and an interval algebra have been proposed for representing qualitative temporal information about the relationships between pairs of intervals and pairs of points, respectively. In this thesis, we address two fundamental reasoning tasks that arise in these algebras: Given (possibly indefinite) knowledge of the relationships between some intervals or points, (i) find a scenario that is consistent with the information provided, and (ii) find the feasible relationships between some or all pairs of intervals or points. Solutions to these tasks have applications in natural language processing, planning, plan recognition, diagnosis, and knowledge-based systems. For the task of finding consistent scenarios the main results are as follows. For the point algebra, we develop an O(n^2) time algorithm that is an O(n) improvement over the previously known algorithm, where n is the number of points. For the interval algebra, finding a consistent scenario has been shown to be (almost assuredly) intractable in the worst case. We show how the results for the point algebra aid in the design of a backtracking algorithm. The algorithm is shown to be useful in practice for planning problems.
For the task of finding the feasible relationships the main results are as follows. For the point algebra, we develop the first exact algorithm for finding all the feasible relationships that takes O(n^4) time, where n is the number of points, and show that a previously known algorithm is exact for a subset of the point algebra. For the interval algebra, finding the feasible relationships is again (almost assuredly) intractable. The intractability of finding exact solutions leads us to develop new algorithms that find approximate solutions. We examine the effectiveness of the approximation algorithms through computational experiments and determine under what conditions the algorithms are exact. We also give a simple test for predicting when the approximation algorithms will and will not produce good quality approximations. Finally, we survey example applications chosen from the literature to show where the results of this thesis are useful.

Return to Publications