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
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.