### Citation

(PDF)
Peter van Beek.
Reasoning about qualitative temporal information.
*Artificial Intelligence*
58:297-326, 1992.
Preliminary versions of the paper appear in
*Proceedings of the 8th National Conference on
Artificial Intelligence,*
Boston, Massachusetts, 728-734, July, 1990;
and in
*Recent Advances in Qualitative Physics,*
Boi Faltings and Peter Struss (eds.),
The MIT Press, 211-227, 1992.

### Abstract

Representing and reasoning about incomplete and indefinite
qualitative temporal information is an essential part of many
artificial intelligence tasks. An interval-based framework and a
point-based framework have been proposed for representing such
temporal information. In this paper, we address two fundamental
reasoning tasks that arise in applications of these frameworks:
Given possibly indefinite and incomplete 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 relations between all pairs of intervals
or points.
For the point-based framework and a restricted version of the
interval-based framework, we give computationally efficient
procedures for finding a consistent scenario and for finding the
feasible relations. Our algorithms are marked improvements over
the previously known algorithms. In particular, we develop an
*O(n^2)* time algorithm for finding one consistent scenario that
is an *O(n)* improvement over the previously known algorithm,
where *n* is the number of intervals or points, and we develop an
algorithm for finding all the feasible relations that is of far
more practical use than the previously known algorithm. For the
unrestricted version of the interval-based framework, finding a
consistent scenario and finding the feasible relations have been
shown to be NP-complete. We show how the results for the point
algebra aid in the design of a backtracking algorithm for finding
one consistent scenario that is shown to be useful in practice
for planning problems.

**Return to Publications**