{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T04:45:02Z","timestamp":1778215502355,"version":"3.51.4"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1999,9,1]],"date-time":"1999-09-01T00:00:00Z","timestamp":936144000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1999,9,1]],"date-time":"1999-09-01T00:00:00Z","timestamp":936144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[1999,9]]},"DOI":"10.1023\/a:1026441215081","type":"journal-article","created":{"date-parts":[[2003,11,6]],"date-time":"2003-11-06T11:45:40Z","timestamp":1068119140000},"page":"199-240","source":"Crossref","is-referenced-by-count":159,"title":["Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison"],"prefix":"10.1007","volume":"4","author":[{"given":"S.","family":"Bistarelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"U.","family":"Montanari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Rossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"Schiex","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Verfaillie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"Fargier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"235746_CR1","volume-title":"Programmazione con vincoli pesati e ottimizzazione","author":"S. Bistarelli","year":"1994","unstructured":"S. Bistarelli (1994). Programmazione con vincoli pesati e ottimizzazione (in italian). Dipartimento di Informatica, Universit`a di Pisa, Italy."},{"key":"235746_CR2","unstructured":"S. Bistarelli, U. Montanari, and F. Rossi (1995). Constraint solving over semirings. In Proc. IJCAI95. Morgan Kaufman."},{"issue":"2","key":"235746_CR3","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/256303.256306","volume":"44","author":"S. Bistarelli","year":"1997","unstructured":"S. Bistarelli, U. Montanari and F. Rossi (1997). Semiring-based constraint solving and optimization. Journal of the ACM 44(2): 201\u2013236.","journal-title":"Journal of the ACM"},{"key":"235746_CR4","unstructured":"S. Bistarelli, U. Montanari, and F. Rossi (1997). Semiring-based constraint logic programming. In Proc. IJCAI97. Morgan Kaufman."},{"key":"235746_CR5","unstructured":"A. Borning, M. Maher, A. Martindale, and M. Wilson (1989). Constraint hierarchies and logic programming. In M. Martell, Levi G., editors, Proc. 6th ICLP. MIT Press."},{"key":"235746_CR6","unstructured":"R. Dechter, A. Dechter, and J. Pearl (1990). Optimization in constraint networks. In R. M. Oliver and J. Q. Smith, editors, Influence Diagrams, Belief Nets and Decision Analysis, chapter 18, pages 411\u2013425. John Wiley & Sons Ltd."},{"issue":"1","key":"235746_CR7","first-page":"43","volume":"8","author":"D. Dubois","year":"1982","unstructured":"D. Dubois and H. Prade (1982). A class of fuzzy measures based on triangular norms. a general framework for the combination of uncertain information. Int. Journal of Intelligent Systems 8(1): 43\u201361.","journal-title":"Int. Journal of Intelligent Systems"},{"key":"235746_CR8","doi-asserted-by":"crossref","unstructured":"D. Dubois, H. Fargier, and H. Prade (1993). The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. In Proc. IEEE Int. Conf. on Fuzzy Systems. IEEE.","DOI":"10.1109\/FUZZY.1993.327356"},{"key":"235746_CR9","volume-title":"Proc. ECSQARU","author":"H. Fargier","year":"1993","unstructured":"H. Fargier and J. Lang (1993). Uncertainty in constraint satisfaction problems: a probabilistic approach. Proc. ECSQARU. Springer-Verlag, LNCS 747."},{"key":"235746_CR10","unstructured":"H. Fargier and J. Lang and T. Schiex (1993). Selecting preferred solutions in fuzzy constraint satisfaction problems. Proc. 1st European Congress on Fuzzy and Intelligent Technologies (EUFIT)."},{"key":"235746_CR11","doi-asserted-by":"crossref","unstructured":"E. Freuder (1978). Synthesizing constraint expressions. CACM 21(11).","DOI":"10.1145\/359642.359654"},{"key":"235746_CR12","doi-asserted-by":"crossref","unstructured":"E. Freuder (1988). Backtrack-free and backtrack-bounded search. In Kanal and Kumar, editors, Search in Artificial Intelligence, Springer-Verlag.","DOI":"10.1007\/978-1-4613-8788-6_10"},{"key":"235746_CR13","doi-asserted-by":"crossref","unstructured":"E. Freuder and R. Wallace (1992). Partial constraint satisfaction. Artificial Intelligence Journal 58.","DOI":"10.1016\/0004-3702(92)90004-H"},{"key":"235746_CR14","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. Garey","year":"1976","unstructured":"M. Garey, D. Johnson, and L. Stockmeyer (1976). Some simplified NP-complete graph problems. Theoretical Computer Science 1: 237\u2013267.","journal-title":"Theoretical Computer Science"},{"key":"235746_CR15","volume-title":"Proc. CP98","author":"Y. Georget","year":"1998","unstructured":"Y. Georget, and P. Codognet (1998). Compiling semiring-based constraints with clp(FD,S). Proc. CP98, Springer Verlag, LNCS 1520."},{"key":"235746_CR16","doi-asserted-by":"crossref","unstructured":"S. de Givry, G. Verfaillie and T. Schiex (1997). Bounding the optimum of constraint optimization problems. Proc. of the Third International Conference on Principles and Practice of Constraint Programming, pages 405\u2013419, Schloss Hagenberg, Austria.","DOI":"10.1007\/BFb0017456"},{"key":"235746_CR17","unstructured":"P. Hubbe and E. Freuder (1992). An efficient cross-product representation of the constraint satisfaction problem search space. In Proc. of AAAI-92, pages 421\u2013427, San Jose, CA."},{"key":"235746_CR18","unstructured":"V. Kumar (1992). Algorithms for constraint satisfaction problems: a survey. AI Magazine 13(1)."},{"key":"235746_CR19","doi-asserted-by":"crossref","unstructured":"J. Jaffar and J.L. Lassez (1987). Constraint logic programming. Proc. POPL, ACM.","DOI":"10.1145\/41625.41635"},{"key":"235746_CR20","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. Krentel","year":"1988","unstructured":"M. Krentel (1988). The complexity of optimization problems. Journal of Computer and System Sciences 36: 490\u2013509.","journal-title":"Journal of Computer and System Sciences"},{"key":"235746_CR21","doi-asserted-by":"crossref","unstructured":"J. Larrosa and P. Meseguer (1996). Exploiting the use ofDACinMAX-CSP. Proc. of the Second International Conference on Principles and Practice of Constraint Programming, pages 308\u2013322, Cambridge (MA).","DOI":"10.1007\/3-540-61551-2_83"},{"key":"235746_CR22","unstructured":"J. Larrosa, P. Meseguer, T. Schiex, and G. Verfaillie (1998). Reversible DAC and other improvements for solving Max-CSP. Proc. of the National Conf. on Artificial Intelligence (AAAI'98), pages 347\u2013352, Madison (WI)."},{"key":"235746_CR23","doi-asserted-by":"crossref","unstructured":"J. Larrosa, P. Meseguer, and T. Schiex (1999). Maintaining reversible DAC for Max-CSP. Artificial Intelligence Journal, 107(1).","DOI":"10.1016\/S0004-3702(98)00108-8"},{"key":"235746_CR24","doi-asserted-by":"crossref","unstructured":"A. Mackworth (1977). Consistency in networks of relations. Artificial Intelligence Journal, 8(1).","DOI":"10.1016\/0004-3702(77)90007-8"},{"key":"235746_CR25","unstructured":"A. Mackworth (1988). Encyclopedia of AI, chapter Constraint Satisfaction, pages 205\u2013211. Springer Verlag."},{"key":"235746_CR26","doi-asserted-by":"crossref","unstructured":"A. Mackworth and E. Freuder (1985). The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence Journal 25.","DOI":"10.1016\/0004-3702(85)90041-4"},{"key":"235746_CR27","doi-asserted-by":"crossref","unstructured":"U. Montanari (1974). Networks of constraints: Fundamental properties and application to picture processing. Information Science 7.","DOI":"10.1016\/0020-0255(74)90008-5"},{"key":"235746_CR28","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0004-3702(91)90059-S","volume":"48","author":"U. Montanari","year":"1991","unstructured":"U. Montanari and F. Rossi (1991). Constraint relaxation may be perfect. Artificial Intelligence Journal 48:143\u2013170.","journal-title":"Artificial Intelligence Journal"},{"key":"235746_CR29","doi-asserted-by":"crossref","unstructured":"H. Moulin (1988). Axioms for Cooperative Decision Making. Cambridge University Press.","DOI":"10.1017\/CCOL0521360552"},{"issue":"4","key":"235746_CR30","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1111\/j.1467-8640.1989.tb00328.x","volume":"5","author":"B. A. Nadel","year":"1989","unstructured":"B. A. Nadel (1989). Constraint satisfaction algorithms. Comput. Intell. 5(4): 188\u2013224.","journal-title":"Comput. Intell."},{"key":"235746_CR31","unstructured":"C. M. Papadimitriou (1994). Computational Complexity. Addison Wesley Publishing Company."},{"key":"235746_CR32","doi-asserted-by":"crossref","unstructured":"A. Rosenfeld, R. Hummel, and S. Zucker (1976). Scene labelling by relaxation operations. IEEE Trans. on Sys., Man, and Cyb. 6(6).","DOI":"10.1109\/TSMC.1976.4309519"},{"key":"235746_CR33","doi-asserted-by":"crossref","unstructured":"Z. Ruttkay (1994). Fuzzy constraint satisfaction. Proc. 3rd Int. Conf. on Fuzzy Systems.","DOI":"10.1109\/FUZZY.1994.343640"},{"key":"235746_CR34","doi-asserted-by":"crossref","unstructured":"T. Schiex (1992). Possibilistic constraint satisfaction problems, or \u201cHow to handle soft constraints?\u201d. Proc. 8th Conf. of Uncertainty in AI.","DOI":"10.1016\/B978-1-4832-8287-9.50041-4"},{"key":"235746_CR35","unstructured":"T. Schiex, H. Fargier, and G. Verfaillie (1995). Valued constraint satisfaction problems: Hard and easy problems. In Proc. IJCAI95. Morgan Kaufmann."},{"key":"235746_CR36","series-title":"Working paper","volume-title":"An axiomatic study of computation in hypertrees","author":"G. Shafer","year":"1991","unstructured":"G. Shafer (1991). An axiomatic study of computation in hypertrees. Working paper 232, University of Kansas, School of Business, Lawrence."},{"key":"235746_CR37","unstructured":"P. Shenoy (1991). Valuation-based systems for discrete optimization. In Bonissone, Henrion, Kanal and Lemmer, editors, Uncertainty in AI. North-Holland Publishers."},{"key":"235746_CR38","unstructured":"P. Shenoy (1994). Valuation-based systems: A framework for managing uncertainty in expert systems. In L. Zadeh and J. Kacprzyk, editors, Fuzzy Logic for the Management of Uncertainty. Wiley."},{"key":"235746_CR39","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1109\/TPAMI.1981.4767144","volume":"3","author":"L. Shapiro","year":"1981","unstructured":"L. Shapiro and R. Haralick (1981). Structural descriptions and inexact matching. IEEE Transactions on Pattern Analysis and Machine Intelligence 3: 504\u2013519.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"235746_CR40","unstructured":"P. Snow and E. Freuder (1990). Improved relaxation and search methods for approximate constraint satisfaction with a maximin criterion. In Proc. of the 8th Biennal Conf. of the Canadian Society for Comput. Studies of Intelligence, pages 227\u2013230."},{"key":"235746_CR41","unstructured":"G. Verfaillie, M. Lematre, and T. Schiex (1996). Russian doll search. In Proc. of AAAI-96, pages 181\u2013187, Portland (OR)."},{"key":"235746_CR42","doi-asserted-by":"crossref","unstructured":"R. J. Wallace (1994). Directed arc consistency preprocessing as a strategy for maximal constraint satisfaction. In the Proc. of ECAI'94 Workshop on Constraint Processing. pages 69\u201377. Also available in LNCS 923, pp. 121\u2013138 (1995).","DOI":"10.1007\/3-540-59479-5_22"},{"key":"235746_CR43","doi-asserted-by":"crossref","unstructured":"L. Zadeh (1975). Calculus of fuzzy restrictions. In K. Tanaka, L.A. Zadeh, K.S. Fu and M. Shimura, editors, Fuzzy sets and their applications to cognitive and decision processes. Academic Press.","DOI":"10.1016\/B978-0-12-775260-0.50006-2"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1026441215081.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1026441215081\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1026441215081.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,13]],"date-time":"2025-07-13T04:08:21Z","timestamp":1752379701000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1026441215081"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,9]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1999,9]]}},"alternative-id":["235746"],"URL":"https:\/\/doi.org\/10.1023\/a:1026441215081","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,9]]}}}