GASP: Answer Set Programming with Lazy Grounding

• Autorzy: Dal Palu A. , Dovier A. , Pontelli E. , Rossi G.
• Języki publikacji: EN

Abstrakty

EN

In recent years, Answer Set Programming has gained popularity as a viable paradigm for applications in knowledge representation and reasoning. This paper presents a novel methodology to compute answer sets of an answer set program. The proposed methodology maintains a bottom-up approach to the computation of answer sets (as in existing systems), but it makes use of a novel structuring of the computation, that originates from the non-ground version of the program. Grounding is lazily performed during the computation of the answer sets. The implementation has been realized using Constraint Logic Programming over finite domains.

Słowa kluczowe

EN

answer set programming; Logic Programming (LP); non-monotonic reasoning

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 96, nr 3
• Strony: 297--322
• Opis fizyczny: Bibliogr. 25 poz., tab., wykr.

Twórcy

autor

Dal Palu A.

autor

Dovier A.

autor

Pontelli E.

autor

Rossi G.

• Dipartimento di Matematica, University of Parma, Viale G.P.Usberti, 53/A - 43100 Parma, Italy,

Bibliografia

• [1] Babovich, Y., Maratea, M.: Cmodels-2: SAT-based Answer Sets Solver Enhanced to Non-tight Programs, Logic Programming and Non-Monotonic Reasoning, LNCS 2923, 2004, 346-350.
• [2] Baral, C.: Knowledge Representation, Reasoning, and Declarative Problem Solving, Cambridge University Press, 2003.
• [3] Bonatti, P., Pontelli, E., Son, T. Credulous Resolution for ASP, AAAI, 2008, 418-423.
• [4] Brooks, D., Erdem, E., Erdogan, S., Minett, J., Ringe, D.: Inferring Phylogenetic Trees Using Answer Set Programming, Journal of Automated Reasoning, 39(4), 2007, 471-511.
• [5] Codognet, P., Diaz, D.: A Minimal Extension of the WAM for clp(fd), International Conference on Logic Programming, pp. 774-790,MIT Press, 1993.
• [6] Dal Palu, A., Dovier, A., Pontelli, E., Rossi, G.: GASP: Answer Set Programming with Lazy Grounding, CILC08: 23-esimo Convegno Italiano di Logica Computazionale, Perugia, Italy, July 10-12th, 2008, and LaSh08: International Workshop on Logic and Search, Nov. 6-7th 2008, Leuven, Belgium.
• [7] Dovier, A., Formisano, A., Pontelli, E.: A Comparison of CLP(FD) and ASP Solutions to NP-Complete Problems, International Conference on Logic Programming, LNCS 3668, Springer Verlag, pp. 67-82, 2005.
• [8] Dovier, A., Formisano, A., Pontelli, E.: Multivalued Action Languages with Constraints in CLP(FD), International Conference on Logic Programming, LNCS 4670, Springer Verlag, pp. 255-270, 2007.
• [9] Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: CLASP: a Conflict-driven Answer Set Solver, Logic Programming and Non-Monotonic Reasoning, Springer Verlag, 2007, 260-265.
• [10] Gelfond, M., Lifschitz, V.: The Stable Model Semantics for Logic Programs, International Symposium on Logic Programming,MIT Press, 1988, 1070-1080.
• [11] Hoffmann, J., Nebel, B.: The FF Planning System: Fast Plan Generation Through Heuristic Search, Journal of Artificial Intelligence Research, 14, 2001, 253-302.
• [12] Lefèvre, C., Nicolas, P.: Integrating Grounding in the Search Process for Answer Set Computing, Workshop on Answer Set Programming and Other Computing Paradigms, Udine, Italy, Dec. 13, 2008.
• [13] Leone, N., Pfeifer, G., Faber, W., Eiter, T., Perri, S., Scarcello, F.: The DLV System for Knowledge Representation and Reasoning, ACM Transactions on Computational Logic, 7(3), 2006, 499-562.
• [14] Lifschitz, V.: Answer Set Planning. Logic Programming and Non-monotonic Reasoning, LNCS 1730, Springer Verlag, 1999, 373-374.
• [15] Lin, F., Zhao, Y.: ASSAT: Computing answer sets of a logic program by SAT solvers, Artificial Intelligence, 157(1-2), 2004, 115-137.
• [16] Liu, L., Pontelli, E., Tran, S., Truszczyński, M.: Logic Programs with Abstract Constraint Atoms: the Role of Computations, International Conference on Logic Programming, Springer Verlag, 2007, 286-301.
• [17] Marek, V.W., Truszczyński,M.: Stable Models and an Alternative Logic Programming Paradigm, The Logic Programming Paradigm, Springer Verlag, 1999.
• [18] Mellarkod, V. S., Gelfond,M., Zhang, Y.: Integrating answer set programming and constraint logic programming. Ann. Math. Artif. Intell. (AMAI) 53(1-4):251-287, 2008.
• [19] Niemela, I.: Logic Programs with Stable Model Semantics as a Constraint Programming Paradigm, Annals of Mathematics and AI, 25(3-4), 1999, 241-273.
• [20] Niemela, I., Simons, P.: Smodels - An Implementation of the Stable Model andWell-Founded Semantics for Normal LP, Logic Programming and Non-monotonic Reasoning, Springer Verlag, 1997, 421-430.
• [21] P. Simons. Extending and Implementing the Stable Model Semantics. Ph.D. Thesis, Helsinki University of Technology, 2000.
• [22] Son, T., Pontelli,E.: Set Constraints in Logic Programming, Logic Programming and Non-Monotonic Reasoning, LNCS 2923, Springer Verlag, 2004, 167-179.
• [23] Son, T., Pontelli, E.: Planning for Biochemical Pathways: a Case Study of Answer Set Planning in Large Planning Problem Instances, First International Workshop on Software Engineering for Answer Set Programming, 2007, 116-130.
• [24] Van Gelder, A., Ross, K. A., Schlipf, J. S.: The Well-Founded Semantics for General Logic Programs, Journal of the ACM, 38(3), 1991, 620-650.
• [25] Zukowski, U., Freitag, B., Brass, S.: Improving the Alternating Fixpoint: The Transformation Approach, Logic Programming and Nonmonotonic Reasoning, LNCS 1265, Springer-Verlag, 1997, 4-59.