Abstract
In this paper we describe 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. We then compare the two approaches and we discuss the relationship between them. The two frameworks have been independently introduced in [2] and [28].
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Bistarelli. Programmazione con vincoli pesati e ottimizzazione (in italian). Dipartimento di Informatica, Università di Pisa, Italy, 1994.
S. Bistarelli, U. Montanari, and F. Rossi. Constraint Solving over Semirings. In Proc. IJCAI95. Morgan Kaufman, 1995.
A. Borning, M. Maher, A. Martindale, and M. Wilson. Constraint hierarchies and logic programming. In Martelli M. Levi G., editor, Proc. 6th ICLP. MIT Press, 1989.
R. Dechter, A. Dechter, and J. Pearl. Optimization in constraint networks. In R.M Oliver and J.Q. Smith, editors, Influence Diagrams, Belief Nets and Decision Analysis, chapter 18, pages 411–425. John Wiley & Sons Ltd., 1990.
D. Dubois and H. Prade. 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–61, 1982.
D. Dubois, H. Fargier, and H. Prade. The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. In Proc. IEEE Int. Conf. on Fuzzy Systems. IEEE, 1993.
H. Fargier and J. Lang. Uncertainty in constraint satisfaction problems: a probabilistic approach. Proc. ECSQARU. Springer-Verlag, LNCS 747, 1993.
H. Fargier and J. Lang and T. Schiex. Selecting Preferred Solutions in Fuzzy Constraint Satisfaction Problems. Proc. 1st European Congress on Fuzzy and Intelligent Technologies (EUFIT). 1993.
E. Freuder. Synthesizing constraint expressions. CACM, 21(11), 1978.
E. Freuder. Backtrack-free and backtrack-bounded search. In Kanal and Kumar, editors, Search in Artificial Intelligence. Springer-Verlag, 1988.
E. Freuder and R. Wallace. Partial constraint satisfaction. AI Journal, 58, 1992.
M. Garey, D. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237–267, 1976.
P. Hubbe and E. Freuder. An efficient cross-product representation of the constraint satisfaction problem search space. In Proc. of AAAI-92, pages 421–427, San Jose, CA, 1992.
V. Kumar. Algorithms for constraint satisfaction problems: a survey. AI Magazine, 13(1), 1992.
J. Jaffar and J.L. Lassez. Constraint Logic Programming. Proc. POPL, ACM, 1987.
M. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 36:490–509, 1988.
A. Mackworth. Consistency in networks of relations. AI Journal, 8(1), 1977.
A. Mackworth. Encyclopedia of AI, chapter Constraint Satisfaction, pages 205–211. Springer Verlag, 1988.
A. Mackworth and E. Freuder. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. AI Journal, 25, 1985.
U. Montanari. Networks of constraints: Fundamental properties and application to picture processing. Information Science, 7, 1974.
U. Montanari and F. Rossi. Constraint relaxation may be perfect. AI Journal, 48:143–170, 1991.
H. Moulin. Axioms for Cooperative Decision Making. Cambridge University Press, 1988.
B. A. Nadel. Constraint satisfaction algorithms. Comput. Intell., 5(4):188–224, November 1989.
C. M. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company. 1994.
A. Rosenfeld, R. Hummel, S. Zucker. Scene Labelling by Relaxation Operations. IEEE Trans. on Sys., Man, and Cyb., vol. 6. n.6, 1976.
Z. Ruttkay. Fuzzy constraint satisfaction. Proc. 3rd Int. Conf. on Fuzzy Systems, 1994.
T. Schiex. Possibilistic constraint satisfaction problems, or “How to handle soft constraints?”. Proc. 8th Conf. of Uncertainty in AI, 1992.
T. Schiex, H. Fargier, and G. Verfaillie. Valued Constraint Satisfaction Problems: Hard and Easy Problems. In Proc. IJCAI95. Morgan Kaufmann, 1995.
G. Shafer. An axiomatic study of computation in hypertrees. Working paper 232, University of Kansas, School of Business, Lawrence, 1991.
L. Shapiro and R. Haralick. Structural descriptions and inexact matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3:504–519, 1981.
P. Snow and E. Freuder. 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–230, May 1990.
L. Zadeh. 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, 1975.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bistarelli, S., Faxgier, H., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G. (1996). Semiring-based CSPs and valued CSPs: Basic properties and comparison. In: Jampel, M., Freuder, E., Maher, M. (eds) Over-Constrained Systems. OCS 1995. Lecture Notes in Computer Science, vol 1106. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61479-6_19
Download citation
DOI: https://doi.org/10.1007/3-540-61479-6_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61479-1
Online ISBN: 978-3-540-68601-9
eBook Packages: Springer Book Archive