On The Duel Representation Of Non-Binary Semiring-Based CSP'sJavier Larrosa (firstname.lastname@example.org) & Rina Dechter (email@example.com)
It is well known that any non-binary CSP can be reformulated as a binary CSP. In this paper we show that the same translation methods can be applied in the soft constraints framework. We observe that any non-binary soft constraint CSP can be reformulated as a problem with only binary and unary constraints. Interestingly, the translation leads to binary constraints that are hard (define conditions of mandatory satisfaction) and unary constraints that are soft (define a preference criterion among the set of solutions). We elaborate our observation in the semiring based framework.