Dynamic constraint satisfaction in configuration

Configuration tasks exhibit dynamic aspects which re-quire extending the basic constraint satisfaction frame-work. In this paper we give a new, well-founded and relatively simple definition of such dynamic constraint satisfaction problems (DCSP). On the basis of the def-inition, we show that the decision problem for DCSP is NP-complete. We also show that although the com-plexity of DCSP is the same as for CSP, DCSP is strictly more expressive in a knowledge representation sense. However, DCSP has its limitations in represent-ing configuration knowledge. We generalise the activ-ity constraints of DCSP with disjunctions and default negation, and show that the decision problem remains NP-complete with this generalization. We finally de-scribe two approaches to implementing DCSP and pro-vide test results for both