×

zbMATH — the first resource for mathematics

A flexible search framework for CHR. (English) Zbl 1229.68018
Schrijvers, Tom (ed.) et al., Constraint Handling Rules. Current research topics. Berlin: Springer (ISBN 978-3-540-92242-1/pbk). Lecture Notes in Computer Science 5388. Lecture Notes in Artificial Intelligence, 16-47 (2008).
Summary: This paper introduces a framework for the specification of tree search strategies in CHR with disjunction (CHR\(^{ \vee })\). We support the specification of common search strategies such as depth-first, breadth-first and best-first, as well as constrained optimization by means of branch & bound search. The framework is given as an extension of CHR with rule priorities (CHR\(^{\text{rp}})\) in which each branch of the search tree is assigned a branch priority. This approach leads to a uniform solution to execution control in CHR.
For the entire collection see [Zbl 1157.68008].

MSC:
68N17 Logic programming
Software:
Mercury; OPL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdennadher, S.: Operational semantics and confluence of constraint propagation rules. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 252–266. Springer, Heidelberg (1997) · doi:10.1007/BFb0017444
[2] Abdennadher, S.: A language for experimenting with declarative paradigms. In: 2nd Workshop on Rule-Based Constraint Reasoning and Programming (2000)
[3] Abdennadher, S.: Rule Based Constraint Programming: Theory and Practice. Habilitation, Institut für Informatik, Ludwig-Maximilians-Universität München (2001)
[4] Abdennadher, S., Krämer, E., Saft, M., Schmauss, M.: JACK: A Java constraint kit. Electronic Notes in Theoretical Computer Science, vol. 64 (2002) · Zbl 06190981 · doi:10.1016/S1571-0661(04)80344-X
[5] Abdennadher, S., Schütz, H.: CHR : A flexible query language. In: Andreasen, T., Christiansen, H., Larsen, H.L. (eds.) FQAS 1998. LNCS, vol. 1495, pp. 1–14. Springer, Heidelberg (1998) · doi:10.1007/BFb0055987
[6] Bruynooghe, M.: Enhancing a search algorithm to perform intelligent backtracking. Theory and Practice of Logic Programming 4(3), 371–380 (2004) · Zbl 1088.68557 · doi:10.1017/S1471068403001893
[7] Carlsson, M., Ottosson, G., Carlson, B.: An open-ended finite domain constraint solver. In: Glaser, H., Hartel, P.H., Kuchen, H. (eds.) PLILP 1997. LNCS, vol. 1292, pp. 191–206. Springer, Heidelberg (1997) · doi:10.1007/BFb0033845
[8] Chen, X., van Beek, P.: Conflict directed backjumping revisited. Journal of Artificial Intelligence Research 14, 53–81 (2001) · Zbl 0970.68192
[9] De Koninck, L., Schrijvers, T., Demoen, B.: Search strategies in CHR (Prolog). In: Schrijvers, T., Frühwirth, T. (eds.) 3rd Workshop on Constraint Handling Rules, Report CW 452, pp. 109–123. Dept. of Computer Science, K.U.Leuven (2006)
[10] De Koninck, L., Schrijvers, T., Demoen, B.: User-definable rule priorities for CHR. In: Leuschel, M., Podelski, A. (eds.) 9th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. ACM Press, New York (2007) · Zbl 1213.68175
[11] Duck, G.J., Stuckey, P.J., García de la Banda, M., Holzbaur, C.: The refined operational semantics of Constraint Handling Rules. In: Demoen, B., Lifschitz, V. (eds.) ICLP 2004. LNCS, vol. 3132, pp. 90–104. Springer, Heidelberg (2004) · Zbl 1104.68359 · doi:10.1007/978-3-540-27775-0_7
[12] Frühwirth, T.: Theory and practice of Constraint Handling Rules. Journal of Logic Programming 37(1-3), 95–138 (1998) · Zbl 0920.68029 · doi:10.1016/S0743-1066(98)10005-5
[13] Frühwirth, T., Michel, L., Schulte, C.: Constraints in procedural and concurrent languages. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming. Foundations of Artificial Intelligence, ch. 13, pp. 453–494. Elsevier Science Publishers, Amsterdam (2006) · doi:10.1016/S1574-6526(06)80017-9
[14] Ginsberg, M.L.: Dynamic backtracking. Journal of Artificial Intelligence Research 1, 25–46 (1993) · Zbl 0900.68179
[15] Ginsberg, M.L., Harvey, W.D.: Iterative broadening. Artificial Intelligence 55(2), 367–383 (1992) · doi:10.1016/0004-3702(92)90059-7
[16] Hanus, M.: Adding Constraint Handling Rules to Curry. In: Fink, M., Tompits, H., Woltran, S. (eds.) 20th Workshop on Logic Programming, INFSYS Research Report 1843-06-02, pp. 81–90. TU Wien (2006)
[17] Hanus, M., Steiner, F.: Controlling search in declarative programs. In: Palamidessi, C., Glaser, H., Meinke, K. (eds.) ALP 1998 and PLILP 1998. LNCS, vol. 1490, pp. 374–390. Springer, Heidelberg (1998) · Zbl 0949.68034 · doi:10.1007/BFb0056627
[18] Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4(2), 100–107 (1968) · doi:10.1109/TSSC.1968.300136
[19] Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. In: 14th International Joint Conference on Artificial Intelligence, vol. 1, pp. 607–615. Morgan Kaufmann, San Francisco (1995)
[20] Hermenegildo, M.V., Bueno, F., Cabeza, D., Carro, M., García de la Banda, M.J., López-García, P., Puebla, G.: The CIAO multi-dialect compiler and system: An experimentation workbench for future (C)LP systems. In: Lucio, P., Martelli, M., Navarro, M. (eds.) 1996 Joint Conference on Declarative Programming, APPIA-GULP-PRODE, pp. 105–110 (1996)
[21] Korf, R.E.: Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence 27(1), 97–109 (1985) · Zbl 0573.68030 · doi:10.1016/0004-3702(85)90084-0
[22] Menezes, L., Vitorino, J., Aurelio, M.: A high performance CHR execution engine. In: Schrijvers, T., Frühwirth, T. (eds.) 2nd Workshop on Constraint Handling Rules, Report CW 421, pp. 35–45. Dept. of Computer Science, K.U.Leuven (2005)
[23] Müller, H.: Static and dynamic variable sorting strategies for backtracking-based search algorithms. In: Wolf, A., Frühwirth, T.W., Meister, M. (eds.) 19th Workshop on (Constraint) Logic Programming. Ulmer Informatik-Berichte, vol. 2005-01, pp. 99–110 (2005)
[24] Prosser, P.: Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence 9, 268–299 (1993) · doi:10.1111/j.1467-8640.1993.tb00310.x
[25] Robin, J., Vitorino, J., Wolf, A.: Constraint programming architectures: Review and a new proposal. Journal of Universal Computer Science 13(6), 701–720 (2007)
[26] Schrijvers, T., Demoen, B.: The K.U.Leuven CHR system: implementation and application. In: Frühwirth, T., Meister, M. (eds.) First Workshop on Constraint Handling Rules: Selected Contributions. Ulmer Informatik-Berichte, vol. 2004-01, pp. 1–5. Universität Ulm (2004)
[27] Schulte, C.: Comparing trailing and copying for constraint programming. In: De Schreye, D. (ed.) 1999 International Conference on Logic Programming, pp. 275–289. MIT Press, Cambridge (1999)
[28] Schulte, C., Carlsson, M.: Finite domain constraint programming systems. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, Foundations of Artificial Intelligence, ch. 14, pp. 495–526. Elsevier Science Publishers, Amsterdam (2006) · doi:10.1016/S1574-6526(06)80018-0
[29] Schulte, C., Smolka, G., Würtz, J.: Encapsulated search and constraint programming in Oz. In: Borning, A. (ed.) PPCP 1994. LNCS, vol. 874, pp. 134–150. Springer, Heidelberg (1994) · doi:10.1007/3-540-58601-6_96
[30] Smith, B.M., Sturdy, P.: Value ordering for finding all solutions. In: Kaelbling, L.P., Saffiotti, A. (eds.) 19th International Joint Conference on Artificial Intelligence, pp. 311–316. Professional Book Center (2005)
[31] Somogyi, Z., Henderson, F., Conway, T.: The execution algorithm of Mercury, an efficient purely declarative logic programming language. Journal of Logic Programming 29(1-3), 17–64 (1996) · Zbl 0877.68015 · doi:10.1016/S0743-1066(96)00068-4
[32] van Hentenryck, P., Perron, L., Puget, J.-F.: Search and strategies in OPL. Transactions on Computational Logic 1(2), 285–320 (2000) · Zbl 1365.90281 · doi:10.1145/359496.359529
[33] Van Weert, P., Schrijvers, T., Demoen, B.: K.U.Leuven JCHR: A user-friendly, flexible and efficient CHR system for Java. In: Schrijvers, T., Frühwirth, T. (eds.) 2nd Workshop on Constraint Handling Rules, Report CW 421, pp. 47–62. Dept. of Computer Science, K.U.Leuven (2005)
[34] Wallace, M., Novello, S., Schimpf, J.: ECL i PS e : A platform for constraint logic programming. ICL Systems Journal 12(1), 159–200 (1997)
[35] Walsh, T.: Depth-bounded discrepancy search. In: 15th International Joint Conference on Artificial Intelligence, vol. 2, pp. 1388–1395. Morgan Kaufmann, San Francisco (1997)
[36] Wolf, A.: Intelligent search strategies based on adaptive Constraint Handling Rules. Theory and Practice of Logic Programming 5(4-5), 567–594 (2005) · Zbl 1105.68429 · doi:10.1017/S1471068405002383
[37] Wolf, A., Gruenhagen, T., Geske, U.: On the incremental adaptation of CHR derivations. Applied Artificial Intelligence 14(4), 389–416 (2000) · Zbl 05387207 · doi:10.1080/088395100117052
[38] Wolf, A., Robin, J., Vitorino, J.: Adaptive CHR meets CHR : An extended refined operational semantics for CHR based on justifications. In: Schrijvers, T., Frühwirth, T. (eds.) Constraint Handling Rules. LNCS (LNAI), vol. 5388, pp. 48–69. Springer, Heidelberg (2008) · Zbl 1229.68025 · doi:10.1007/978-3-540-92243-8_3
[39] Wuille, P., Schrijvers, T., Demoen, B.: CCHR: The fastest CHR implementation. In: In Khalil Djelloul, C., Duck, G.J., Sulzmann, M. (eds.) 4th Workshop on Constraint Handling Rules, pp. 123–137. U.Porto (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.