Exact and approximate reasoning about qualitative temporal relations
Peter van Beek · 1992
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, • find a scenario that is consistent with the information provided, and • 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,