Qualitative Temporal Reasoning with Points and Durations

We present here a qualitative temporal reasoning system that takes both points and durations as primitive objects and allows relative and indefinite information. We formaly define a point duration network, as a structure formed by two point algebra (PA) networks separately but not independently, since ternary constraints are introduced for relating point and duration information. We adapt some of the concepts and reasoning techniques developed for the point algebra networks, such as consistency and minimality. We prove that the problem of determining consistency in a point duration network is NP-complete. A simpler and polynomial-time decision problem is introduced for a restricted kind of point duration networks. Finally we suggest how to determine consistency and find minimal point duration network in the general case.