Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison |
| |
| Authors: | S Bistarelli U Montanari F Rossi T Schiex G Verfaillie H Fargier |
| |
| Affiliation: | (1) Dipartimento di Informatica, University of Pisa, Corso Italia 40, 56125 Pisa, Italy;(2) INRA, Chemin de Borde Rouge, BP 27, 31326 Castanet, Tolosan Cedex, France;(3) CERT /ONERA, 2 Av. E. Belin, BP 4025, 31055 Toulouse Cedex, France;(4) IRIT, 118 route de Narbonne, 31062 Toulouse Cedex, France |
| |
| Abstract: | In this paper we describe and compare two frameworks for constraint solving where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. One is based on a semiring, and the other one on a totally ordered commutative monoid. While comparing the two approaches, we show how to pass from one to the other one, and we discuss when this is possible. The two frameworks have been independently introduced in ijcai95,jacm and schiex-ijcai95. |
| |
| Keywords: | overconstrained problems constraint satisfaction optimization soft constraint dynamic programming branch and bound complexity |
| 本文献已被 SpringerLink 等数据库收录！ |
|
