Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison. Bistarelli, S., Ugo, M., Francesca, R., Thomas, S., Gerard, V., & Helene, F. CONSTRAINTS, 4:199–240, 1999. doi abstract bibtex 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 [2], [3] and [35].
@article{
11391_120844,
author = {Bistarelli, Stefano and Ugo, Montanari and Francesca, Rossi and Thomas, Schiex and Gerard, Verfaillie and Helene, Fargier},
title = {Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison},
year = {1999},
journal = {CONSTRAINTS},
volume = {4},
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 [2], [3] and [35].},
keywords = {Branch and bound, Complexity, CONSTRAINT SATISFACTION, dynamic programming, optimization, Overconstrained problems, Soft Constraint},
doi = {10.1023/A:1026441215081},
pages = {199--240}
}
Downloads: 0
{"_id":"mKAfpcShncv3W2Req","bibbaseid":"bistarelli-ugo-francesca-thomas-gerard-helene-semiringbasedcspsandvaluedcspsframeworkspropertiesandcomparison-1999","author_short":["Bistarelli, S.","Ugo, M.","Francesca, R.","Thomas, S.","Gerard, V.","Helene, F."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Bistarelli"],"firstnames":["Stefano"],"suffixes":[]},{"propositions":[],"lastnames":["Ugo"],"firstnames":["Montanari"],"suffixes":[]},{"propositions":[],"lastnames":["Francesca"],"firstnames":["Rossi"],"suffixes":[]},{"propositions":[],"lastnames":["Thomas"],"firstnames":["Schiex"],"suffixes":[]},{"propositions":[],"lastnames":["Gerard"],"firstnames":["Verfaillie"],"suffixes":[]},{"propositions":[],"lastnames":["Helene"],"firstnames":["Fargier"],"suffixes":[]}],"title":"Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison","year":"1999","journal":"CONSTRAINTS","volume":"4","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 [2], [3] and [35].","keywords":"Branch and bound, Complexity, CONSTRAINT SATISFACTION, dynamic programming, optimization, Overconstrained problems, Soft Constraint","doi":"10.1023/A:1026441215081","pages":"199–240","bibtex":"@article{\n\t11391_120844,\n\tauthor = {Bistarelli, Stefano and Ugo, Montanari and Francesca, Rossi and Thomas, Schiex and Gerard, Verfaillie and Helene, Fargier},\n\ttitle = {Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison},\n\tyear = {1999},\n\tjournal = {CONSTRAINTS},\n\tvolume = {4},\n\tabstract = {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 [2], [3] and [35].},\n\tkeywords = {Branch and bound, Complexity, CONSTRAINT SATISFACTION, dynamic programming, optimization, Overconstrained problems, Soft Constraint},\n\tdoi = {10.1023/A:1026441215081},\t\n\tpages = {199--240}\n}\n","author_short":["Bistarelli, S.","Ugo, M.","Francesca, R.","Thomas, S.","Gerard, V.","Helene, F."],"key":"11391_120844","id":"11391_120844","bibbaseid":"bistarelli-ugo-francesca-thomas-gerard-helene-semiringbasedcspsandvaluedcspsframeworkspropertiesandcomparison-1999","role":"author","urls":{},"keyword":["Branch and bound","Complexity","CONSTRAINT SATISFACTION","dynamic programming","optimization","Overconstrained problems","Soft Constraint"],"metadata":{"authorlinks":{}},"downloads":0,"html":""},"bibtype":"article","biburl":"http://www.dmi.unipg.it/~bista/papers/pubblicazioni.bib","dataSources":["GhB5rb8JzW6az3exo"],"keywords":["branch and bound","complexity","constraint satisfaction","dynamic programming","optimization","overconstrained problems","soft constraint"],"search_terms":["semiring","based","csps","valued","csps","frameworks","properties","comparison","bistarelli","ugo","francesca","thomas","gerard","helene"],"title":"Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison","year":1999}