Incremental qualitative temporal reasoning: Algorithms for the Point Algebra and the ORD-Horn class

摘要

In many applications of temporal reasoning we are interested in processing temporal information incrementally. In particular, given a set of temporal constraints (a temporal CSP) and a new constraint, we want to maintain certain properties of the extended temporal 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. The reasoning algorithms for PA and the tractable fragments of IA, such as Nebel and Bürckert's maximal tractable class of relations (ORD-Horn), have originally been designed for “static” reasoning.