×

Partial compilation of ASP programs. (English) Zbl 1434.68072

Summary: Answer Set Programming (ASP) is a well-known declarative formalism in logic programming. Efficient implementations made it possible to apply ASP in many scenarios, ranging from deductive databases applications to the solution of hard combinatorial problems. State-of-the-art ASP systems are based on the traditional ground&solve approach and are general-purpose implementations, i.e., they are essentially built once for any kind of input program. In this paper, we propose an extended architecture for ASP systems, in which parts of the input program are compiled into an ad-hoc evaluation algorithm (i.e., we obtain a specific binary for a given program), and might not be subject to the grounding step. To this end, we identify a condition that allows the compilation of a sub-program, and present the related partial compilation technique. Importantly, we have implemented the new approach on top of a well-known ASP solver and conducted an experimental analysis on publicly-available benchmarks. Results show that our compilation-based approach improves on the state of the art in various scenarios, including cases in which the input program is stratified or the grounding blow-up makes the evaluation unpractical with traditional ASP systems.

MSC:

68N17 Logic programming
68N20 Theory of compilers and interpreters
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alviano, M., Dodaro, C., Leone, N., and Ricca, F.2015. Advances in WASP. In LPNMR. LNCS, vol. 9345. Springer, 40-54. · Zbl 1467.68021
[2] Amendola, G., Greco, G., Leone, N., and Veltri, P.2016. Modeling and reasoning about NTU games via answer set programming. In IJCAI. IJCAI/AAAI Press, 38-45.
[3] Aschinger, M., Drescher, C., Friedrich, G., Gottlob, G., Jeavons, P., Ryabokon, A., and Thorstensen, E.2011. Optimization methods for the partner units problem. In CPAIOR. 4-19. · Zbl 1302.90164
[4] Balduccini, M. and Lierler, Y.2017. Constraint answer set solver EZCSP and why integration schemas matter. TPLP 17, 4, 462-515. · Zbl 1379.68038
[5] Bartholomew, M. and Lee, J.2014. System aspmt2smt: Computing ASPMT theories by SMT solvers. In JELIA. Lecture Notes in Computer Science, vol. 8761. Springer, 529-542. · Zbl 1432.68055
[6] Bogaerts, B. and Weinzierl, A.2018. Exploiting justifications for lazy grounding of answer set programs. In IJCAI. 1737-1745.
[7] Brewka, G., Eiter, T., and Truszczynski, M.2011. Answer set programming at a glance. Commun. ACM 54, 12, 92-103.
[8] Calimeri, F., Fuscà, D., Perri, S., and Zangari, J.2017. I-DLV: the new intelligent grounder of DLV. Intelligenza Artificiale11 , 1, 5-20. · Zbl 1472.68179
[9] Ceri, S., Gottlob, G., and Tanca, L.1990. Logic Programming and Databases. Surveys in computer science. Springer.
[10] Cuteri, B., Dodaro, C., Ricca, F., and Schüller, P.2017. Constraints, lazy constraints, or propagators in ASP solving: An empirical analysis. TPLP17, 5-6, 780-799. · Zbl 06803822
[11] Cuteri, B., Reale, K., and Ricca, F.2019. A logic-based question answering system for cultural heritage. In JELIA. Lecture Notes in Computer Science, vol. 11468. Springer, 526-541. · Zbl 1525.68163
[12] Dal Palù, A., Dovier, A., Pontelli, E., and Rossi, G.2009. GASP: answer set programming with lazy grounding. Fundam. Inform. 96 , 3, 297-322. · Zbl 1207.68118
[13] Dodaro, C., Gasteiger, P., Leone, N., Musitsch, B., Ricca, F., and Schekotihin, K.2016. Combining answer set programming and domain heuristics for solving hard industrial problems (application paper). TPLP 16, 5-6, 653-669. · Zbl 1379.68281
[14] Dodaro, C. and Ricca, F.2018. The external interface for extending WASP. TPLP in press CORR abs/1811.01692. · Zbl 1472.68183
[15] Eiter, T., Fink, M., Ianni, G., Krennwallner, T., Redl, C., and Schüller, P.2016. A model building framework for answer set programming with external computations. TPLP 16, 4, 418-464. · Zbl 1379.68058
[16] Eiter, T., Ianni, G., and Krennwallner, T.2009. Answer set programming: A primer. In Reasoning Web. Lecture Notes in Computer Science, vol. 5689. Springer, 40-110. · Zbl 1254.68248
[17] Erdem, E., Gelfond, M., and Leone, N.2016. Applications of answer set programming. AI Magazine 37, 3, 53-68.
[18] Erdem, E. and Öztok, U.2015. Generating explanations for biomedical queries. TPLP 15, 1, 35-78. · Zbl 1379.68059
[19] Faber, W., Leone, N., and Perri, S.2012. The intelligent grounder of DLV. In Correct Reasoning. Lecture Notes in Computer Science, vol. 7265. Springer, 247-264. · Zbl 1357.68032
[20] Garcia-Molina, H., Ullman, J. D., and Widom, J.2009. Database systems - the complete book (2. ed.). Pearson Education.
[21] Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., and Wanko, P.2016. Theory solving made easy with clingo 5. In ICLP TCs. OASICS, vol. 52. 2:1-2:15.
[22] Gebser, M., Kaminski, R., Kaufmann, B., Romero, J., and Schaub, T.2015. Progress in clasp series 3. In LPNMR. Lecture Notes in Computer Science, vol. 9345. Springer, 368-383. · Zbl 1467.68181
[23] Gebser, M., Kaminski, R., König, A., and Schaub, T.2011. Advances in gringo series 3. In LPNMR. LNCS, vol. 6645. Springer, 345-351.
[24] Gebser, M., Leone, N., Maratea, M., Perri, S., Ricca, F., and Schaub, T.2018. Evaluation techniques and systems for answer set programming: a survey. In IJCAI. ijcai.org, 5450-5456.
[25] Gebser, M., Ryabokon, A., and Schenner, G.2015. Combining heuristics for configuration problems using answer set programming. In LPNMR. Springer, 384-397. · Zbl 1467.68166
[26] Gelfond, M. and Lifschitz, V.1991. Classical negation in logic programs and disjunctive databases. New Generation Comput. 9, 3/4, 365-386. · Zbl 0735.68012
[27] Ianni, G., Martello, A., Panetta, C., and Terracina, G.2009. Efficiently querying RDF(S) ontologies with answer set programming. J. Log. Comput. 19, 4, 671-695. · Zbl 1192.68128
[28] Janhunen, T., Oikarinen, E., Tompits, H., and Woltran, S.2009. Modularity Aspects of Disjunctive Stable Models. Journal Of Artificial Intelligence Research 35, 813-857. · Zbl 1192.68129
[29] Kojo, T., Männistö, T., and Soininen, T.2003. Towards intelligent support for managing evolution of configurable software product families. In SCM. LNCS, vol. 2649. Springer, 86-101. · Zbl 1028.68814
[30] Koponen, L., Oikarinen, E., Janhunen, T., and Säilä, L.2015. Optimizing phylogenetic supertrees using answer set programming. TPLP 15, 4-5, 604-619. · Zbl 1379.92038
[31] Lefevre, C., Béatrix, C., Stéphan, I., and Garcia, L.2017. Asperix, a first-order forward chaining approach for answer set computing. Theory and Practice of Logic Programming17, 3, 266-310. · Zbl 1379.68075
[32] Leone, N., Allocca, C., Alviano, M., Calimeri, F., Civili, C., Costabile, R., Fiorentino, A., Fuscà, D., Germano, S., Laboccetta, G., Cuteri, B., Manna, M., Perri, S., Reale, K., Ricca, F., Veltri, P., and Zangari, J.2019. Enhancing DLV for large-scale reasoning. In LPNMR. Lecture Notes in Computer Science, vol. 11481. Springer, 312-325. · Zbl 07115983
[33] Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., and Scarcello, F.2006. The DLV system for knowledge representation and reasoning. ACM TOCL 7, 3, 499-562. · Zbl 1367.68308
[34] Lierler, Y., Maratea, M., and Ricca, F.2016. Systems, engineering environments, and competitions. AI Magazine37, 3, 45-52.
[35] Lifschitz, V. and Turner, H.1994. Splitting a logic program. In ICLP. MIT Press, 23-37.
[36] Manna, M., Ricca, F., and Terracina, G.2015. Taming primary key violations to query large inconsistent data via ASP. TPLP 15, 4-5, 696-710. · Zbl 1379.68114
[37] Marileo, M. C. and Bertossi, L. E.2010. The consistency extractor system: Answer set programs for consistent query answering in databases. Data Knowl. Eng. 69, 6, 545-572.
[38] Muchnick, S. S.1997. Advanced Compiler Design and Implementation. Morgan Kaufmann.
[39] Nogueira, M., Balduccini, M., Gelfond, M., Watson, R., and Barry, M.2001. An A Prolog decision support system for the space shuttle. In Answer Set Programming.
[40] Ostrowski, M. and Schaub, T.2012. ASP modulo CSP: the clingcon system. TPLP 12, 4-5, 485-503. · Zbl 1260.68066
[41] Simons, P., Niemelä, I., and Soininen, T.2002. Extending and implementing the stable model semantics. Artif. Intell. 138, 1-2, 181-234. · Zbl 0995.68021
[42] Ullman, J. D.1988. Principles of Database and Knowledge-Base Systems, Volume I. Principles of computer science series, vol. 14. Computer Science Press.
[43] Weinzierl, A.2017. Blending Lazy-Grounding and CDNL Search for Answer-Set Solving. In LPNMR. LNCS, vol. 10377. 191-204. · Zbl 1491.68262
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.