---
title: "Incremental Tractable Reasoning about Qualitative Temporal Constraints"
authors:
  - "Alfonso Gerevini"
doi: ""
url: "https://ijcai.org/proceedings/2003/182"
pdf: "https://ijcai.org/proceedings/2003/0182.pdf"
venue: "Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence"
year: 2003
pages: "1283-1287"
track: ""
keywords:
---

# Incremental Tractable Reasoning about Qualitative Temporal Constraints

Alfonso Gerevini

*Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence*, pages 1283-1287.

## 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.