Weight constraint programs with evaluable functions. (English) Zbl 1230.68186
Summary: In the current practice of answer set programming (ASP), evaluable functions are represented as special kinds of relations. This often makes the resulting program unnecessarily large when instantiated over a large domain. The extra constraints needed to enforce the relation as a function also make the logic program less transparent. In this paper, we consider adding evaluable functions to answer set logic programs. The class of logic programs that we consider here is that of weight constraint programs, which are widely used in ASP. We propose an answer set semantics to these extended weight constraint programs and define loop completion to characterize the semantics. Computationally, we provide a translation from loop completions of these programs to instances of the constraint satisfaction problem (CSP) and use the off-the-shelf CSP solvers to compute the answer sets of these programs. A main advantage of this approach is that global constraints implemented in such CSP solvers become available to ASP. The approach also provides a new encoding for CSP problems in the style of weight constraint programs. We have implemented a prototype system based on these results, and our experiments show that this prototype system competes well with the state-of-the-art ASP solvers. In addition, we illustrate the utilities of global constraints in the ASP context.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68T27 | Logic in artificial intelligence |
| 68N17 | Logic programming |
| 68T30 | Knowledge representation |
Keywords:
answer set programming; weight constraints; evaluable functions; constraint satisfaction problemReferences:
| [1] | Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, New York (2003) · Zbl 1056.68139 |
| [2] | Baselice, S., Bonatti, P.A., Criscuolo, G.: On finitely recursive programs. In: Proceedings of the Twenty Third International Conference on Logic Programming, pp. 89–103, Porto, Portugal. Springer, New York (2007) · Zbl 1213.68170 |
| [3] | Bessiere, C., Katsirelos, G., Narodytska, N., Quimper, C.-G., Walsh, T.: Decompositions of all different, global cardinality and related constraints. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, pp. 419–424. Pasadena, California (2009) |
| [4] | Bonatti, P.A.: Reasoning with infinite stable models. Artif. Intell. 156(1), 75–111 (2004) · Zbl 1085.68681 · doi:10.1016/j.artint.2004.02.001 |
| [5] | Bordeaux, L., Hamadi, Y., Zhang, L.: Propositional satisfiability and constraint programming: a comparative survey. ACM Comput. Surv. 38(4), 12:1–12:54 (2006) |
| [6] | Cabalar, P.: A functional action language front-end. In: The Third International Workshop on Answer Set Programming: Advances in Theory and Implementation. http://www.dc.fi.udc.es/\(\sim\)cabalar/asp05_C.pdf (2005) |
| [7] | Cabalar, P., Lorenzo, D.: Logic programs with functions and default values. In: Proceedings of the Ninth European Conference on Logics in Artificial Intelligence, pp. 294–306, Lisbon, Portugal. Springer, New York (2004) · Zbl 1111.68378 |
| [8] | Cadoli, M., Schaerf, M.: A survey of complexity results for nonmonotonic logics. Log. Program. 17(2/3&4), 127–160 (1993) · Zbl 0784.68039 · doi:10.1016/0743-1066(93)90029-G |
| [9] | Calimeri, F., Cozza, S., Ianni, G., Leone, N.: Computable functions in ASP: theory and implementation. In: Logic Programming, 24th International Conference, Udine, Italy, vol. 5366 of Lecture Notes in Computer Science, pp. 407–424. Springer, New York (2008) · Zbl 1185.68150 |
| [10] | Chen, Y., Lin, F., Wang, Y., Zhang, M.: First-order loop formulas for normal logic programs. In: Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR 2006), Lake District of the United Kingdom, pp. 298–307. AAAI Press, Menlo Park (2006) |
| [11] | Dovier, A., Formisano, A., Pontelli, E.: An empirical study of constraint logic programming and answer set programming solutions of combinatorial problems. J. Exp. Theoret. Artif. Intell. 21(2), 79–121 (2009) · Zbl 1193.68073 · doi:10.1080/09528130701538174 |
| [12] | Drescher, C., Walsh, T.: A translational approach to constraint answer set solving. Theory Pract. Log. Program. 10(4–6), 465–480 (2010) · Zbl 1209.68511 · doi:10.1017/S1471068410000220 |
| [13] | Eiter, T., Faber, W., Mushthofa, M.: Space efficient evaluation of asp programs with bounded predicate arities. In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, Atlanta, Georgia, USA, pp. 303–308. AAAI Press, Menlo Park (2010) |
| [14] | Eiter, T., Simkus, M.: FDNC: decidable nonmonotonic disjunctive logic programs with function symbols. ACM Trans. Comput. Log. 11(2), 14:1–14:50 (2010) · Zbl 1351.68052 |
| [15] | Erdem, E., Lin, F., Schaub, T. (eds.): Logic Programming and Nonmonotonic Reasoning, 10th International Conference, LPNMR 2009, Potsdam, Germany, 14–18 September 2009. Proceedings, vol. 5753 of Lecture Notes in Computer Science. Springer, New York (2009) |
| [16] | Ferraris, P., Lee, J., Lifschitz, V.: A new perspective on stable models. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence, pp. 372–379. Hyderabad, India (2007) |
| [17] | Ferraris, P., Lifschitz, V.: Weight constraints as nested expressions. Theory Pract. Log. Program. 5(1–2), 45–74 (2005) · Zbl 1093.68017 · doi:10.1017/S1471068403001923 |
| [18] | Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: Conflict-driven answer set enumeration. In: Logic Programming and Nonmonotonic Reasoning, 9th International Conference, Tempe, AZ, USA, LPNMR 2007, vol. 4483 of Lecture Notes in Computer Science, pp. 136–148. Springer, New York (2007) · Zbl 1149.68332 |
| [19] | Gebser, M., Ostrowski, M., Schaub, T.: Constraint answer set solving. In: Logic Programming, 25th International Conference, ICLP 2009, Pasadena, CA, USA, vol. 5649 of Lecture Notes in Computer Science, pp. 235–249. Springer, New York (2009) · Zbl 1251.68061 |
| [20] | Gelfond, M., Leone, N.: Logic programming and knowledge representation–the a-prolog perspective. Artif. Intell. 138(1–2), 3–38 (2002) · Zbl 0995.68022 · doi:10.1016/S0004-3702(02)00207-2 |
| [21] | Järvisalo, M., Oikarinen, E., Janhunen, T., Niemelä, I.: A module-based framework for multi-language constraint modeling. In: Logic Programming and Nonmonotonic Reasoning, 10th International Conference, vol. 5753 of Lecture Notes in Computer Science, pp. 155–168. Springer, New York (2009) · Zbl 1258.68136 |
| [22] | Lee, J.: A model-theoretic counterpart of loop formulas. In: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, pp. 503–508. Professional Book Center, London (2005) |
| [23] | Lee, J., Lifschitz, V.: Loop formulas for disjunctive logic programs. In: Proceedings of the Nineteenth International Conference on Logic Programming, Mumbai, India, vol. 2916 of Lecture Notes in Computer Science, pp. 451–465. Springer, New York (2003) · Zbl 1204.68056 |
| [24] | Lifschitz, V., Razborov, A.A.: Why are there so many loop formulas? ACM Trans. Comput. Log. 7(2), 261–268 (2006) · Zbl 1367.68036 · doi:10.1145/1131313.1131316 |
| [25] | Lifschitz, V., Turner, H.: Splitting a logic program. In: Proceedings of the Eleventh International Conference on Logic Programming, Santa Margherita Ligure, Italy, pp. 23–37. MIT Press, Cambridge (1994) |
| [26] | Lin, F., Wang, Y.: Answer set programming with functions. In: Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning, Sydney, Australia, pp. 454–464. AAAI Press, Menlo Park (2008) |
| [27] | Lin, F., Zhao, Y.: ASSAT: computing answer sets of a logic program by SAT solvers. Artif. Intell. 157(1–2), 115–137 (2004) · Zbl 1085.68544 · doi:10.1016/j.artint.2004.04.004 |
| [28] | Liu, G., You, J.-H.: Level mapping induced loop formulas for weight constraint and aggregate logic programs. Fundam. Inform. 101(3), 237–255 (2010) · Zbl 1284.68116 |
| [29] | Liu, L., Truszczynski, M.: Properties and applications of programs with monotone and convex constraints. J. Artif. Intell. Res. 27, 299–334 (2006) · Zbl 1182.68043 |
| [30] | Lloyd, J.W.: Foundations of Logic Programming, 2nd edn. Springer, New York (1987) · Zbl 0668.68004 |
| [31] | Wiktor Marek, V., Truszczynski, M.: Stable models and an alternative logic programming paradigm. In: Apt, K.R., Marek, V.W., Truszczynski, M., Warren, D.S. (eds.) The Logic Programming Paradigm: A 25-Year Perspective, pp. 375–398. Springer, Berlin (1999) |
| [32] | Marek, V., Niemelä, I., Truszczyński, M.: Logic programs with monotone abstract constraint atoms. Theory Pract. Log. Program. 8(2), 167–199 (2008) · Zbl 1142.68018 |
| [33] | Mellarkod, V.S., Gelfond, M., Zhang, Y.: Integrating answer set programming and constraint logic programming. Ann. Math. Artif. Intell. 53(1–4), 251–287 (2008) · Zbl 1165.68504 · doi:10.1007/s10472-009-9116-y |
| [34] | Niemelä, I.: Logic programs with stable model semantics as a constraint programming paradigm. Ann. Math. Artif. Intell. 25(3–4), 241–273 (1999) · Zbl 0940.68018 · doi:10.1023/A:1018930122475 |
| [35] | Niemelä, I., Simons, P.: Extending the Smodels System with Cardinality and Weight Constraints, Chapter 21, pp. 491–521. Kluwer, Dordrecht (2000) · Zbl 0979.68015 |
| [36] | Oikarinen, E., Janhunen, T.: Achieving compositionality of the stable model semantics for smodels programs. Theory Pract. Log. Program. (TPLP) 8(5–6), 717–761 (2008) · Zbl 1156.68012 · doi:10.1017/S147106840800358X |
| [37] | Papadimitriou, C.H.: Computatioinal Complexity. Addison Wesley, Reading (1994) |
| [38] | Pearce, D., Valverde, A.: Towards a first order equilibrium logic for nonmonotonic reasoning. In: Logics in Artificial Intelligence, 9th European Conference, Lisbon, Portugal, vol. 3229 of Lecture Notes in Computer Science, pp. 147–160. Springer, New York (2004) · Zbl 1111.68687 |
| [39] | Rina, D.: Constraint Processing. Morgan Kaufmann, San Mateo (2003) · Zbl 1057.68114 |
| [40] | Simons, P., Niemelä, I., Soininen, T.: Extending and implementing the stable model semantics. Artif. Intell. 138(1–2), 181–234 (2002) · Zbl 0995.68021 · doi:10.1016/S0004-3702(02)00187-X |
| [41] | Syrjänen, T.: Omega-restricted logic programs. In: Proceedings of the Sixth International Conference on Logic Programming and Nonmonotonic Reasoning, Vienna, Austria, pp. 267–279. Springer, New York (2001) · Zbl 1007.68503 |
| [42] | Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972) · Zbl 0251.05107 · doi:10.1137/0201010 |
| [43] | Wang, Y., You, J.-H., Yuan, L.-Y., Zhang, M.: Weight constraint programs with functions. In: Logic Programming and Nonmonotonic Reasoning, 10th International Conference, LPNMR 2009, Potsdam, Germany, vol. 5753 of Lecture Notes in Computer Science, pp. 329–341. Springer, New York (2009) · Zbl 1258.68041 |
| [44] | You, J.-H., Liu, G.: Loop formulas for logic programs with arbitrary constraint atoms. In: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI 2008), Chicago, Illinois, USA, pp. 584–589. AAAI Press, Menlo Park (2008) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
