On The Duel Representation Of Non-Binary Semiring-Based CSP's
Javier Larrosa (javier@ics.uci.edu) & Rina Dechter (dechter@ics.uci.edu)
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.

PostScript | PDF