Incremental Tractable Reasoning about Qualitative Temporal Constraints

Abstract

In many applications of temporal reasoning we are interested in reasoning incrementally. In particular, given a CSP of temporal constrains and a new constraint, we want to maintain certain properties in the extended CSP (e.g., a solution), rather than recomputing them from scratch. The Point Algebra (PA) and the Interval Algebra (IA) are two well-known frameworks for qualitative temporal reasoning. Most of the existing algorithms for PA and the known tractable fragments of IA, such as ORDHorn , has been designed for "static" reasoning . In this paper we study the incremental version of some fundamental problems of temporal reasoning, proposing new algorithms that amortize their complexity when processing a sequence of input constraints. After analyzing the role of path-consistency for incremental satisfiability, we propose algorithms for maintaining a solution of a CSP over either PA or ORD-Horn, and the minimal labels of a CSP over PA. Our algorithms improve the complexity of using existing techniques by a factor of O(n) or O(n 2 ), where n is the number of variables involved in the CSP.