UW Constraint-Based Languages and Systems: Papers - Theory

Title: Constraint Hierarchies

Authors: Alan Borning, Bjorn Freeman-Benson, and Molly Wilson

Lisp and Symbolic Computation, Vol. 5 No. 3, (September 1992), pages 223-270.

Reprinted in Constraint Programming, B. Mayoh, E. Tougu, J. Penjam (Eds.), NATO Advanced Science Institute Series, Series F: Computer and System Sciences, Vol 131, Springer-Verlag, 1994, pages 75-115.


Constraints allow programmers and users to state declaratively a relation that should be maintained, rather than requiring them to write procedures to maintain the relation themselves. They are thus useful in such applications as programming languages, user interface toolkits, and simulation packages. In many situations, it is desirable to be able to state both required and preferential constraints. The required constraints must hold. Since the other constraints are merely preferences, the system should try to satisfy them if possible, but no error condition arises if it cannot. A constraint hierarchy consists of a set of constraints, each labeled as either required or preferred at some strength. An arbitrary number of different strengths is allowed. In the discussion of a theory of constraint hierarchies, we present alternate ways of selecting among competing possible solutions, and prove a number of propositions about the relations among these alternatives. We then outline algorithms for satisfying constraint hierarchies, and ways in which we have used constraint hierarchies in a number of programming languages and systems.

full paper: compressed postscript; pdf