Dynamic Constraints

TitleDynamic Constraints
Publication TypeTechnical Report
Year of Publication1990
AuthorsGuesgen, H. Werner, & Hertzberg J.
Other Numbers578
Abstract

Usually, a constraint describes a relation on variables, and networks of constraints are obtained by sharing variables among constraints. Manipulating a constraint or a constraint network means manipulating the variables until a consistent assignment is found. There are, however, deviations from this classical view, e.g., manipulating the constraints themselves to make the computation of consistent assignments more efficient, or relaxing constraints to make an overspecified constraint problem solvable.In this paper, we present a formalism that subsumes classical constraint satisfaction, constraint manipulation, and constraint relaxation. The idea is that the constraints in a network are not static but that their relations can and must be manipulated and that manipulating relations subsumes manipulating variable values. We clarify the relation between classical constraint networks and the newly developed dynamical ones; we prove termination properties of dynamic constraint networks in the special case of filtering; and we show by examples how to express constraint manipulation and constraint relaxation in the new formalism.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-90-14.pdf
Bibliographic Notes

ICSI Technical Report TR-90-014

Abbreviated Authors

H. W. Guesgen and J. Hertzberg

ICSI Publication Type

Technical Report