×

zbMATH — the first resource for mathematics

Adaptive CHR meets CHR\(^{ \vee }\). An extended refined operational semantics for CHR\(^{ \vee }\) based on justifications. (English) Zbl 1229.68025
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, 48-69 (2008).
Summary: Adaptive constraint processing with Constraint Handling Rules (CHR) allows the application of intelligent search strategies to solve Constraint Satisfaction Problems (CSP), but these search algorithms have to be implemented in the host language of adaptive CHR which is currently Java. On the other hand, CHR\(^{ \vee }\) enables to explicitly formulate search in CHR, using disjunctive bodies to model choices. However, a naive implementation for handling disjunctions, in particular chronological backtracking (as implemented in Prolog), might cause “thrashing” due to an inappropriate order of decisions. In order to avoid this, a first combination of adaptive CHR and CHR\(^{ \vee }\) is presented to offer a more efficient embedded search mechanism to handle disjunctions. Therefore, the refined operational semantics of CHR is extended for disjunctions and adaptation.
For the entire collection see [Zbl 1157.68008].

MSC:
68N17 Logic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdennadher, S., Schütz, H.: CHR \(^{\lor}\) : A flexible query language. In: Andreasen, T., Christiansen, H., Larsen, H.L. (eds.) FQAS 1998. LNCS (LNAI), vol. 1495, pp. 1–14. Springer, Heidelberg (1998) · doi:10.1007/BFb0055987
[2] Duck, G.J., García de la Banda, M., Stuckey, P.J., 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
[3] Frühwirth, T., Di Pierro, A., Wiklicky, H.: Probabilistic constraint handling rules. Electronic Notes in Theoretical Computer Science 76, 1–16 (2002) · doi:10.1016/S1571-0661(04)80789-8
[4] Frühwirth, T.: Constraint Handling Rules. In: Podelski, A. (ed.) Constraint Programming: Basics and Trends. LNCS, vol. 910, pp. 90–107. Springer, Heidelberg (1995) · doi:10.1007/3-540-59155-9_6
[5] Frühwirth, T.: Theory and practice of Constraint Handling Rules. The Journal of Logic Programming 37, 95–138 (1998) · Zbl 0920.68029 · doi:10.1016/S0743-1066(98)10005-5
[6] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman & Co., New York (1979) · Zbl 0411.68039
[7] Ginsberg, M.L.: Dynamic backtracking. Journal of Artificial Intelligence Research 1, 25–46 (1993) · Zbl 0900.68179
[8] Holzbaur, C., Frühwirth, T.: A Prolog Constraint Handling Rules compiler and runtime system. Applied Artificial Intelligence 14(4), 369–388 (2000) · Zbl 05386824 · doi:10.1080/088395100117043
[9] De Koninck, L., Schrijvers, T., Demoen, B.: Flexible search strategies in Prolog CHR. Report CW 447, Department of Computer Science, K. U. Leuven (May 2006); Also presented at the Workshop on CHR (2006) · Zbl 1229.68018
[10] De Koninck, L., Schrijvers, T., Demoen, B.: A Flexible Search Framework for CHR. In: Schrijvers, T., Frühwirth, T. (eds.) Constraint Handling Rules. LNCS (LNAI), vol. 5388, pp. 16–47. Springer, Heidelberg (2008) · Zbl 1229.68018 · doi:10.1007/978-3-540-92243-8_2
[11] Prosser, P.: Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence 9(3), 268–299 (1991); also available as technical report AISL-46-91, Stratchclyde (1991) · doi:10.1111/j.1467-8640.1993.tb00310.x
[12] The ROARS project (last visited February 25, 2008), http://www.cin.ufpe.br/ jr/mysite/RoarsProject.html
[13] Schrijvers, T., Frühwirth, T.: Optimal union-find in constraint handling rules. Theory and Practice of Logic Programming 6(1–2), 213–224 (2006) · Zbl 1109.68029 · doi:10.1017/S1471068405002541
[14] Sneyers, J., Schrijvers, T., Demoen, B.: The computational power and complexity of constraint handling rules. In: Schrijvers, T., Frühwirth, T. (eds.) Proceedings of CHR 2005, Second Workshop on Constraint Handling Rules, number CW 421 in CW Reports, pp. 3–17. Katholieke Universiteit Leuven, Department of Computer Science (2005) (last visited August 26, 2008), http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW421.abs.html · Zbl 1165.68348
[15] Wolf, A.: Projection in adaptive constraint solving based on chrs. In: Apt, K.R., Kakas, A.C., Monfroy, E., Rossi, F. (eds.) Proceedings of the ERCIM/COMPULOG Workshop on Constraints, Department of Computer Science, University of Cyprus, Nicosia, Cyprus (October 1999)
[16] Wolf, A.: Adaptive constraint handling with CHR in Java. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 256–270. Springer, Heidelberg (2001) · Zbl 1067.68682 · doi:10.1007/3-540-45578-7_18
[17] 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
[18] Wolf, A., Gruenhagen, T., Geske, U.: On incremental adaptation of CHR derivations. Applied Artificial Intelligence 14(4), 389–416 (2000) · Zbl 05387207 · doi:10.1080/088395100117052
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.