Constraints

By Guy L. Steele, Gerald J. Sussman. 1979

We present an interactive system organized around networks of constraints rather than the programs which manipulate them. We describe a language of hierarchical constraint networks. We describe one method of deriving useful consequences of a set of constraints which we call propagation. Dependency analysis is used to spot and track down inconsistent subsets of a constraint set. Propagation of constraints is most flexible and useful when coupled with the ability to perform symbolic manipulations on algebraic expressions. Such manipulations are in turn best expressed as alterations or augmentations of the constraint network. Numerous diagrams ornament the text.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Andrei A. Bulatov
2. Peter G. Jeavons
3. Andrei A. Krokhin
4. Dmitriy Zhuk
5. B. Larose

Citations in the corpus

• Combinatorial problems raised from 2-semilattices (2006, background): “The tractability has been proved for many famous classes of algebras including finite semilattices [26], groups [18], quasiprimal [22] and paraprimal [14] algebras.”
• Classifying the Complexity of Constraints Using Finite Algebras (2005, background): “This link between relational clones and polymorphisms has already played a key role in identifying many tractable constraint classes and developing appropriate efficient solution algorithms for them [3, 4, 6, 7, 12, 28].”