Path Consistency in a Network of Non-Convex Intervals

Abstract

Reasoning about time often involves incomplete information about periods and their relationships. Varieties of incompleteness include uncertainty about the number of objects involved, the distribution of a set of temporal relations among these objects, and what can be called the participation of a set of objects in a temporal relation. A solution to the problem of representing and reasoning about incomplete temporal information of these kinds is forthcoming if a restricted class of non-convex intervals (called n-tntervals) is added to the temporal domain of discourse. An n-interval corresponds to the common sense notion of a recurring period of time with a (possibly) unspecified number of occurrences. In this paper, we formalize a representation for temporal reasoning problems using n-intervals. The language of the framework is restricted in such a way that tractable techniques from constraint satisfaction can be applied. Specifically, it is demonstrated how the problem of determining path-consistency in a network of binary n-interval relations can be solved. 1