Incremental tractable reasoning about qualitative temporal constraints
Alfonso Gerevini · 2003
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 ORD-Horn, 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 where n is the number of variables involved in the CSP. 1