Back to Search
Start Over
Incremental qualitative temporal reasoning: Algorithms for the Point Algebra and the ORD-Horn class
- Source :
-
Artificial Intelligence . Aug2005, Vol. 166 Issue 1/2, p37-80. 44p. - Publication Year :
- 2005
-
Abstract
- Abstract: 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. In this paper, we study the incremental version of the fundamental reasoning problems in the context of these tractable classes. We propose a collection of new polynomial algorithms that can amortize their complexity when processing a sequence of input constraints to incrementally decide satisfiability, to maintain a solution, or to update the minimal representation of the CSP. Our incremental algorithms improve the total time complexity of using existing static techniques by a factor of or , where n is the number of the variables involved by the temporal CSP. An experimental analysis focused on constraints over PA confirms the computational advantage of our incremental approach. [Copyright &y& Elsevier]
- Subjects :
- *ALGORITHMS
*FOUNDATIONS of arithmetic
*ALGEBRA
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 00043702
- Volume :
- 166
- Issue :
- 1/2
- Database :
- Academic Search Index
- Journal :
- Artificial Intelligence
- Publication Type :
- Academic Journal
- Accession number :
- 18127293
- Full Text :
- https://doi.org/10.1016/j.artint.2005.04.005