Stefano Bistarelli
Ugo Montanari
Abstract
We extend the Constraint Logic Programming (CLP) formalism in order to handle semiring-based constraints. This allows us to perform in the same language both constraint solving and optimization. In fact, constraints based on semirings are able to model both classical constraint solving and more sophisticated features like uncertainty, probability, fuzziness, and optimization. We then provide this class of languages with three equivalent semantics: model-theoretic, fix-point, and proof-theoretic, in the style of classical CLP programs.
- Bistarelli, S., Fargier, H., Montanari, U., Rossi, F., Schiex, T., and Verfaillie, G. 1999. Semiring-based CSPs and Valued CSPs: Frameworks, properties, and comparison. CON- STRAINTS: An international journal. Kluwer 4, 3.]] Google Scholar
- Bistarelli, S., Montanari, U., and Rossi, F. 1995. Constraint Solving over Semirings. In Proc. IJCAI95. Morgan Kaufman, San Francisco, CA, USA.]]Google Scholar
- Bistarelli, S., Montanari, U., and Rossi, F. 1997b. Semiring-based Constraint Logic Programming. In Proc. IJCAI97. Morgan Kaufman, San Francisco, CA, USA.]]Google Scholar
- Bistarelli, S., Montanari, U., and Rossi, F. 1997a. Semiring-based Constraint Solving and Optimization. Journal of the ACM 44, 2 (Mar), 201-236.]] Google Scholar
- Bistarelli, S., Montanari, U., and Rossi, F. 2001. Soft constraint logic programming and generalized shortest path problems. Journal of Heuristics. Kluwer. toappear.]] Google Scholar
- Borning, A., Maher, M., Martindale, A., and Wilson, M. 1989. Constraint hierarchies and logic programming. In Proc. 6th International Conference on Logic Programming,G. Levi and M. Martelli, Eds. MIT Press, Cambridge, MA, USA, 149-164.]]Google Scholar
- Codognet, P. and Diaz, D. 1996. Compiling constraints in clp(fd). The Journal of Logic Programming. Elsevier Science 27, 3.]]Google Scholar
- Dubois, D., Fargier, H., and Prade, H. 1993. The calculus of fuzzy restrictions as a basis for exible constraint satisfaction. In Proc. IEEE International Conference on Fuzzy Systems. IEEE, Piscataway, NJ, U.S.A., 1131-1136.]]Google Scholar
- Fargier, H. and Lang, J. 1993. Uncertainty in constraint satisfaction problems: a probabilistic approach. In Proc. European Conference on Symbolic and Qualitative Approaches to Reasoning and Uncertainty (ECSQARU). Number 747 in LNCS. Springer-Verlag, Heidelberg, Germany, 97-104.]] Google Scholar
- Fitting, M. 1981. Bilattices and the semantics of logic programming. The Journal of Logic Programming. Elsevier Science 11, 1-2, 91-116.]] Google Scholar
- Freuder, E. and Wallace, R. 1992. Partial constraint satisfaction. AI Journal. Morgan Kaufmann 58.]] Google Scholar
- Georget, Y. and Codognet, P. 1998. Compiling semiring-based constraints with clp(fd,s). In Proc. CP98. Number 1520 in LNCS. Springer-Verlag, Heidelberg, Germany.]] Google Scholar
- Jaffar, J. and Lassez, J. L. 1987. Constraint logic programming. In Proc. POPL. ACM, New York, NY, USA.]] Google Scholar
- Jaffar, J. and Maher, M. 1994. Constraint logic programming: A survey. The Journal of Logic Programming. Elsevier Science 19 and 20.]]Google Scholar
- Lloyd, J. W. 1987. Foundations of Logic Programming. Springer-Verlag, Heidelberg, Germany.]] Google Scholar
- Mackworth, A. 1992. Constraint satisfaction. In Encyclopedia of AI (second edition), S. Shapiro, Ed. John Wiley & Sons, New York, NY, USA, 285-293.]]Google Scholar
- Mobasher, B., Pigozzi, D., and Slutzki, G. 1997. Multi-valued logic programming semantics: An algebraic approach. Theoretical Computer Science. Elsevier Science 171, 77-109.]] Google Scholar
- Schiex, T., Fargier, H., and Verfaille, G. 1995. Valued Constraint Satisfaction Problems: Hard and Easy Problems. In Proc. IJCAI95. Morgan Kaufmann, San Francisco, CA, USA, 631-637.]]Google Scholar
- Tarski, A. 1955. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics. International Press 5, 285-309.]]Google Scholar
- Tsang, E. P.1993. Foundations of Constraint Satisfaction. Academic Press, San Diego, CA.]]Google Scholar
- Van Emden, M. 1986. Quantitative deduction and its fixpoint theory. The Journal of Logic Programming. Elsevier Science 3, 1.]] Google Scholar
- Van Hentenryck, P. 1989. Constraint Satisfaction in Logic Programming. MIT Press, Cambridge, MA, USA.]] Google Scholar
- Wallace, M. 1996. Practical applications of constraint programming. Constraints: An International Journal. Kluwer 1, 1 and 2.]]Google Scholar
Index Terms
- Semiring-based constraint logic programming: syntax and semantics
Recommendations
Constraint Hierarchies as Semiring-Based CSPs
ICTAI '09: Proceedings of the 2009 21st IEEE International Conference on Tools with Artificial IntelligenceConstraints provide an effective means for the high-level modeling and reasoning of various problems. In particular, soft constraints are useful since they treat over-constrained problems that naturally arise in real-life applications. Therefore, ...
Soft concurrent constraint programming
Soft constraints extend classical constraints to represent multiple consistency levels, and thus provide a way to express preferences, fuzziness, and uncertainty. While there are many soft constraint solving formalisms, even distributed ones, as yet ...
Semiring-based constraint logic programming
IJCAI'97: Proceedings of the 15th international joint conference on Artifical intelligence - Volume 1We extend the Constraint Logic Programming (CLP) formalism in order to handle semiringbased constraint systems. This allows us to perform in the same language both constraint solving and optimization. In fact, constraint systems based on semirings are ...
Comments