Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9650011 | Artificial Intelligence | 2005 | 44 Pages |
Abstract
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 O(n) or O(n2), 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Alfonso Gerevini,