Dynamic abstractions and reformulations in constraint satisfaction problems
Rainer Weigel · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 1998
(short version) Constraint satisfaction is the most successful computational paradigm for problem-solving today. A major difficulty is efficient formulation of constraint satisfaction proiblems (CSP). This thesis describes several methods for abstractions and reformulations of CSPs. The thesis presents three major results. The first is a technique for finding context-dependent interchangeability, an abstraction that allows simplifying CSP. The second is a technique for abstracting a CSP solution space into a tree of abstractions, which can in particular be used for compiling CSP. The third is a general reformulation technique that allows enumerating all equivalent formulations of a CSP