Algorithms and complexity for reasoning about time

Abstract

Interval consistency problems deal with events, each of which is assumed to be an interval on the real line or on any other linearly ordered set. This paper deals with problems in reasoning about such intervals when the precise topological relationships between them is unknown or only partially specified. This work unifies notions of interval algebras for temporal reasoning in artificial intelligence with those of interval orders and interval graphs in combinatorics, obtaining new algorithmic and complexity results of interest to both disciplines. Several versions of the satisfiability, minimum labelling and all consistent solutions problems for temporal (interval) data are investigated. The satisfiability question is shown to be NP-complete even when restricting the possible interval relationships to subsets of the relations intersection and precedence only. On the other hand, we give efficient algorithm for several other restrictions of the problem. Many of these problems are also important in molecular biology, archaeology, and resolving mutual-exclusion constraints in circuit design.