A note on some collapse results of valued constraints |
| |
Authors: | Bruno Zanuttini Stanislav ?ivný |
| |
Affiliation: | a GREYC, Université de Caen Basse-Normandie, Boulevard du Maréchal Juin, 14 032 Caen Cedex, France b Computing Laboratory, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK |
| |
Abstract: | Valued constraint satisfaction problem (VCSP) is an optimisation framework originally coming from Artificial Intelligence and generalising the classical constraint satisfaction problem (CSP). The VCSP is powerful enough to describe many important classes of problems. In order to investigate the complexity and expressive power of valued constraints, a number of algebraic tools have been developed in the literature. In this note we present alternative proofs of some known results without using the algebraic approach, but by representing valued constraints explicitly by combinations of other valued constraints. |
| |
Keywords: | Valued constraint satisfaction problems Expressive power Max-closed constraints Theory of computation |
本文献已被 ScienceDirect 等数据库收录! |
|