James Gosling Algebraic Constraints Degree Type: Ph.D. in Computer Science Advisor(s): Robert Sproull, Raj Reddy Graduated: May 1983 Abstract: Constraints are a way of expressing relationships among objects; satisfying a set of constraints involves finding an assignment of values to variables that is consistent with the constraints. In its full generality, constructing a constraint satisfaction algorithm is a hopeless task. This dissertation focuses on the problem of performing constraint satisfaction in an interactive graphical layout system. It takes a pragmatic approach and restricts itself to a narrow but very useful domain. The algorithms used by MAGRITTE, an editor for simple line drawings, are presented. A major portion of the work concerns the algebraic transformation of sets of constraints. It describes algorithms for identifying difficult subregions of a constraint graph and replacing them with a transformed and simplified new constraint. CMU-CS-83-132.pdf (5.88 MB) Copyright Notice