Dynamization of backtrack-free search for the constraint satisfaction problem

Many AI tasks can be formulated as a Constraint Satisfaction Problem (CSP), i.e. the problem of finding an assignment of values for a set of variables subject to a given collection of constraints. In this framework each constraint is defined over a set of variables and specifies the set of allowed combinations of values as a collection of tuples. In some cases the knowledge of the problem defined by the set of constraints may vary along the time. In particular one might be interested in further restrictions i.e. in deletions of values from existing constraints, or in introducing new ones. In general the problem to find a solution to a CSP is NP-complete, but there exist some cases that can be solved efficiently. In this paper we consider classes of problems with a tractable solution, and present dynamic algorithms that solve this problem efficiently and are shown to be optimal.