Integrating Finite Domain and Set Constraints into a Set-based Constraint Language

• Autorzy: Bergenti F. , Dal Palu A. , Rossi G.
• Języki publikacji: EN

Abstrakty

EN

This paper summarizes a constraint solving technique that is used to reason effectively in the scope of a set-based constraint language that supersedes existing finite domain languages. The first part of this paper motivates the presented work and introduces the constraint language, namely the language of Hereditarily Finite Sets (HFS). Then, the proposed constraint solver is detailed in terms of a set of rewrite rules that exploit finite domain reasoning within the HFS language. The proposed solution improves previous work on CLP(SET ) [11] by integrating intervals into the constraint system and by providing a new layered architecture for the solver that supports more effective constraint solving strategies. On the other hand, the proposed approach provides enhanced expressivity and flexibility of domain representation than those usually found in existing finite domain constraint solvers.

Słowa kluczowe

EN

Finite Domain constraints; Set Constraints; Hereditarily Finite Sets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 96, nr 3
• Strony: 227--252
• Opis fizyczny: Bibliogr. 32 poz.

Twórcy

autor

Bergenti F.

autor

Dal Palu A.

autor

Rossi G.

• Dipartimento di Matematica, Universita degli Studi di Parma, Viale G. P. Usberti 53, 43100 Parma, Italy,

Bibliografia

• [1] APT, K.R. (2003) Principles of Consraint Programming. Cmbridge University Press.
• [2] ARNI, N., GRECO, S., AND SACCà , D. (1996) Matching of Bounded Set Terms in the Logic Language LDL++. J. of Logic Programming, 27(1):73-87.
• [3] AZEVEDO, F. (2007) Cardinal: A Finite Sets Constraint Solver. Constraints, 12(37):93-129.
• [4] BERGENTI, F., PANEGAI, E., AND ROSSI, G. (2006) A Master-Slave Architecture to Integrate Sets and Finite Domains in Java. Presented at CILC'06 - Convegno Italiano di Logica Computazionale, Bari.
• [5] BOUQUET, F., LEGEARD, B., AND PEUREUX, F. (2002) CLPS-B - a constraint solver for B. In Tools and Algorithms for the Construction and Analysis of Systems, Vol. 2280 of LNCS, Springer Verlag, 188-204.
• [6] CODOGNET, P., AND DIAZ, D. (1996) Compiling constraints in CLP(FD). Journal of Logic Programming, 27(3):185-226.
• [7] CUCCHIARA, R., GAVANELLI, M., LAMMA, E., MELLO, P., MILANO, M., PICCARDI, M. (online) Extending the CSP Model to Cope With Partial Information. Available at: http://lia.deis.unibo.it/Research/Areas/icsp
• [8] DAL PAL`U , A., DOVIER, A., PONTELLI, E., AND ROSSI, G. (2003) Integrating Finite Domain Constraints and CLP with Sets. In D. Miller, ed., Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming, ACM Press, 219-229.
• [9] DAL PAL`U , A., DOVIER, A., PONTELLI, E., AND ROSSI, G. (2006) Constraint Logic Programming Language for Effective Programming with Sets and Finite Domains. Research Report "Quaderno del Dipartimento di Matematica", 437, Università di Parma. F. Bergenti et al. / Integrating Finite Domain and Set Constraints 251
• [10] DOVIER, A., OMODEO, E. G., PONTELLI, E., AND ROSSI, G. (1996) {log}: A Language for Programming in Logic with Finite Sets. Journal of Logic Programming, 28(1):1-44.
• [11] DOVIER, A., PIAZZA, C., PONTELLI, E., AND ROSSI, G. (2000) Sets and Constraint Logic Programming. ACM Transactions on Programming Languages and Systems, 22(5):861-931.
• [12] DOVIER, A., PONTELLI, E., AND ROSSI, G. (2006) Set unification. Theory and Practice of Logic Programming, 6:645-701.
• [13] FLENER, P., HNICH, B., AND KIZILTAN, Z. (2001) Compiling high-level type constructor in constraint programming. In I.V. Ramakrishnan ed., Practical Aspects of Declarative Languages, Vol. 1990 of LNCS, Springer Verlag, pp. 229-244.
• [14] FLENER, P., PEARSON, J., AND AGREN. M. (2004) Introducing ESRA, a relational language for modeling combinatorial problems. In M. Bruynooghe ed., LOPSTR'03: Revised Selected Papers, pp. 214-232, Springer-Verlag.
• [15] FOURER, R., GAY, D., AND KERNIGHAN, B.W. (1993) AMPL: a modeling language for mathematical programming. The Scientific Press.
• [16] FRŰHWIRTH, T. (1998) Theory and practice of constraint handling rules. J. of Logic Programming, 37(1-3):95-138.
• [17] GAVANELLI M., LAMMA E., MELLO P., AND MILANO, M. (2005) Dealing with incomplete knowledge on CLP(FD) variable domains. ACM Transactions on Programming Languages and Systems, 27(2):236-263.
• [18] GERVET, C. (1997) Interval Propagation to Reason about Sets: Definition and Implementation of a Practical Language. Constraints, 1(3):191-244.
• [19] GERVET, C. (2006) Constraints over Structured Domains. In Rossi, F. van Beek, P., and Walsh, T. (Eds.), Handbook of Constraint Programming, Elsevier.
• [20] GRECO S. (1996) Optimal Unification of Bound Simple Set Terms. In Proc. of Conf. on Information and Knowledge Management, 326-336, ACM Press.
• [21] HOFSTEDT, P. (2000) Cooperating Constraint Solvers. In Dechter, R. (Ed.), International Conference on Principle and Practice of Constraint Programming, Vol. 1894 of LNCS, Springer Verlag, 520-524.
• [22] IC PARC (2003) The ECLiPSe Constraint Logic Programming System. London. www.icparc.ic.ac.uk/eclipse/.
• [23] LECONTE, M. (1996) A bounds-based reduction scheme for constraints of difference. In Proceedings of the Constraint-96 International Workshop on Constraint-Based Reasoning, pp. 19-28
• [24] NORBERG, M. (2006) Writing a compiler for the finite domain CSP modeling language ESRA. Master's Thesis, Department of Information Technology, Uppsala University.
• [25] PANDINI, D. (2008) Progettazione e realizzazione in Java di un risolutore di vincoli su domini finiti. Tesi di Laurea, Dipartimento di Matematica, Università degli Studi di Parma.
• [26] ROSSI, G. (2005) The {log} Constraint Logic Programming Language. prmat.math.unipr.it/~gianfr/setlog.Home.html.
• [27] ROSSI, G., PANEGAI, E., AND POLEO, E. (2007) JSetL: A Java Library for Supporting Declarative Programming in Java. Software-Practice & Experience, 37:115-149.
• [28] VAN ROY, P. (ED.) (2005) Multiparadigm Programming in Mozart/Oz. Lecture Notes in Computer Science 3389 Springer 2005, ISBN 3-540-25079-4.
• [29] SWEDISH INSTITUTE OF COMPUTER SCIENCE. The SICStus Prolog Home Page. www.sics.se.
• [30] VAN HENTENRYCK, P., MICHEL, L., AND DEVILLE, Y. (1997) Numerica: a modeling language for global optimization. MIT Press.
• [31] WIELEMAKER, J. (2004) SWI-Prolog Reference Manual (Version 5.4). University of Amsterdam.
• [32] ZHOU, N-F. (2005) B-Prolog User's Manual (Version 6.8). Afany Software.