Dynamic abstractions and reformulations in constraint satisfaction problems

(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 CS