|
Abstract : |
The performance of constraint based problem solving depends crucially on the problem representation. The same problem may be easy or difficult to solve depending on the way we formulate it. In this paper, we study reformulations of discrete constraint satisfaction problems (CSPs). We present a technique to transform a CSP P into its Boolean form, which allows us to find different reformulations of P. We identify a new class of tractable CSPs and present sufficient conditions for detecting solvability and unsolvability of a CSP in linear time. Finally we introduce the notion of fault tolerance of solutions, and show how the Boolean form can be used to find them., |
