{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:23:58Z","timestamp":1792070638753,"version":"4.4.0"},"reference-count":49,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2020,9,21]],"date-time":"2020-09-21T00:00:00Z","timestamp":1600646400000},"content-version":"unspecified","delay-in-days":20,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Answer-Set Programming (ASP) is a powerful and expressive knowledge representation paradigm with a significant number of applications in logic-based AI. The traditional ground-and-solve approach, however, requires ASP programs to be grounded upfront and thus suffers from the so-called grounding bottleneck (i.e., ASP programs easily exhaust all available memory and thus become unsolvable). As a remedy, lazy-grounding ASP solvers have been developed, but many state-of-the-art techniques for grounded ASP solving have not been available to them yet. In this work we present, for the first time, adaptions to the lazy-grounding setting for many important techniques, like restarts, phase saving, domain-independent heuristics, and learned-clause deletion. Furthermore, we investigate their effects and in general observe a large improvement in solving capabilities and also uncover negative effects in certain cases, indicating the need for portfolio solving as known from other solvers.<\/jats:p>","DOI":"10.1017\/s1471068420000332","type":"journal-article","created":{"date-parts":[[2020,9,21]],"date-time":"2020-09-21T01:25:42Z","timestamp":1600651542000},"page":"609-624","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":14,"title":["Advancing Lazy-Grounding ASP Solving Techniques \u2013 Restarts, Phase Saving, Heuristics, and More"],"prefix":"10.1017","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2040-6123","authenticated-orcid":false,"given":"ANTONIUS","family":"WEINZIERL","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7639-1616","authenticated-orcid":false,"given":"RICHARD","family":"TAUPE","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"GERHARD","family":"FRIEDRICH","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2020,9,21]]},"reference":[{"key":"S1471068420000332_ref48","unstructured":"48. Weinzierl, A. 2013. Learning non-ground rules for answer-set solving. In 2nd Workshop on Grounding and Transformations for Theories With Variables. 25\u201337."},{"key":"S1471068420000332_ref43","unstructured":"43. Redl, C. 2016. Automated benchmarking of KR-systems. In RCRA@AI*IA. CEUR Workshop Proceedings, vol. 1745. CEUR-WS.org, 45\u201356."},{"key":"S1471068420000332_ref9","unstructured":"9. Biere, A. and Fr\u00f6hlich, A. 2018. Evaluating CDCL restart schemes. In POS@SAT. EPiC Series in Computing, vol. 59. EasyChair, 1\u201317."},{"key":"S1471068420000332_ref15","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1017\/S1471068412000105","article-title":"The third open answer set programming competition","volume":"1","author":"Calimeri","year":"2014","journal-title":"Theory Pract. Log. Program. 14,"},{"key":"S1471068420000332_ref8","volume-title":"Computer Science","volume":"7514","author":"Audemard","year":"2012"},{"key":"S1471068420000332_ref1","first-page":"3","volume-title":"Computer Science","volume":"11481","author":"Abels","year":"2019"},{"key":"S1471068420000332_ref46","unstructured":"46. Taupe, R. , Weinzierl, A. , and Schenner, G. 2017. Introducing heuristics for lazy-grounding ASP solving. In 1st International Workshop on Practical Aspects of Answer Set Programming."},{"key":"S1471068420000332_ref26","unstructured":"26. Gebser, M. , Kaminski, R. , Kaufmann, B. , Ostrowski, M. , Schaub, T. , and Wanko, P. 2016. Theory solving made easy with clingo 5. In ICLP (Technical Communications). OASICS, vol. 52. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2:1\u20132:15."},{"key":"S1471068420000332_ref32","unstructured":"32. Gomes, C. P. , Selman, B. , Crato, N. , and Kautz, H. A. 2000. Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. J. Autom. Reasoning 24, 1\/2, 67\u2013100."},{"key":"S1471068420000332_ref36","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0020-0190(93)90029-9","article-title":"Optimal speedup of las vegas algorithms","volume":"4","author":"Luby","year":"1993","journal-title":"Inf. Process. Lett. 47,"},{"key":"S1471068420000332_ref22","unstructured":"22. Elffers, J. , Gir\u00e1ldez-Cru, J. , Gocht, S. , Nordstr\u00f6m, J. , and Simon, L. 2018. Seeking practical CDCL insights from theoretical SAT benchmarks. In IJCAI. ijcai.org, 1300\u20131308."},{"key":"S1471068420000332_ref18","unstructured":"18. Dao-Tran, M. , Eiter, T. , Fink, M. , Weidinger, G. , and Weinzierl, A. 2012. Omiga : An open minded grounding on-the-fly answer set solver. In JELIA. LNCS, vol. 7519. Springer, 480\u2013483."},{"key":"S1471068420000332_ref10","unstructured":"10. Bogaerts, B. and Weinzierl, A. 2018. Exploiting justifications for lazy grounding of answer set programs. In IJCAI. ijcai.org, 1737\u20131745."},{"key":"S1471068420000332_ref33","first-page":"266","article-title":"ASPeRiX, a first-order forward chaining approach for answer set computing","volume":"3","author":"Lef\u00e8vre","year":"2017","journal-title":"TPLP 17"},{"key":"S1471068420000332_ref31","unstructured":"31. Goldberg, E. and Novikov, Y. 2002. Berkmin: A fast and robust SAT-solver. In Design, Automation and Test in Europe Conference and Exhibition, 2002. IEEE, 142\u2013149."},{"key":"S1471068420000332_ref4","unstructured":"4. Alviano, M. , Dodaro, C. , Faber, W. , Leone, N. , and Ricca, F. 2013. WASP: A native ASP solver based on constraint learning. In LPNMR. LNCS, vol. 8148. Springer, 54\u201366."},{"key":"S1471068420000332_ref30","doi-asserted-by":"publisher","DOI":"10.3233\/AIC-2011-0496"},{"key":"S1471068420000332_ref34","unstructured":"34. 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 Trans. Comput. Log. 7, 3, 499\u2013562."},{"key":"S1471068420000332_ref42","unstructured":"42. Pretolani, D. 1993. Efficiency, and stability of hypergraph SAT algorithms. In Cliques, Coloring, and Satisfiability. Vol. 26. DIMACS\/AMS, 479\u2013498."},{"key":"S1471068420000332_ref49","unstructured":"49. Weinzierl, A. 2017. Blending lazy-grounding and CDNL search for answer-set solving. In LPNMR. LNCS, vol. 10377. Springer, 191\u2013204."},{"key":"S1471068420000332_ref19","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4591"},{"key":"S1471068420000332_ref20","volume-title":"Computer Science","volume":"2919","author":"E\u00e9n","year":"2003"},{"key":"S1471068420000332_ref45","volume-title":"Computer Science","volume":"11481","author":"Taupe","year":"2019"},{"key":"S1471068420000332_ref40","doi-asserted-by":"crossref","first-page":"297","DOI":"10.3233\/FI-2009-180","article-title":"GASP: answer set programming with lazy grounding","volume":"3","author":"Pal\u00f9","year":"2009","journal-title":"Fundam. Inform. 96"},{"key":"S1471068420000332_ref35","volume-title":"Computer Science","volume":"10997","author":"Leutgeb","year":"2017"},{"key":"S1471068420000332_ref41","volume-title":"Computer Science","volume":"4501","author":"Pipatsrisawat","year":"2007"},{"key":"S1471068420000332_ref27","unstructured":"27. Gebser, M. , Kaminski, R. , K\u00f6nig, A. , and Schaub, T. 2011. Advances in gringo series 3. In LPNMR. LNCS, vol. 6645. Springer, 345\u2013351."},{"key":"S1471068420000332_ref13","doi-asserted-by":"crossref","first-page":"5","DOI":"10.3233\/IA-170104","article-title":"I-DLV: the new intelligent grounder of DLV","volume":"1","author":"Calimeri","year":"2017","journal-title":"Intelligenza Artificiale 11"},{"key":"S1471068420000332_ref37","unstructured":"37. Marple, K. , Bansal, A. , Min, R. , and Gupta, G. 2012. Goal-directed execution of answer set programs. In PPDP. ACM, 35\u201344."},{"key":"S1471068420000332_ref47","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.artint.2017.04.002","article-title":"On the complexity of the partner units decision problem","author":"Teppan","year":"2017","journal-title":"Artif. Intell. 248"},{"key":"S1471068420000332_ref21","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1613\/jair.1.11221","article-title":"Exploiting partial assignments for efficient evaluation of answer set programs with external source access","author":"Eiter","year":"2018","journal-title":"J. Artif. Intell. Res. 62"},{"key":"S1471068420000332_ref17","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1017\/S1471068419000231","article-title":"Partial compilation of ASP programs","volume":"5","author":"Cuteri","year":"2019","journal-title":"Theory Pract. Log. Program. 19,"},{"key":"S1471068420000332_ref24","first-page":"165","article-title":"Industrial applications of answer set programming","volume":"2","author":"Falkner","year":"2018","journal-title":"KI 32"},{"key":"S1471068420000332_ref6","volume-title":"Computer Science","volume":"6697","author":"Aschinger","year":"2011"},{"key":"S1471068420000332_ref11","unstructured":"11. Bomanson, J. , Janhunen, T. , and Weinzierl, A. 2019. Enhancing lazy grounding with lazy normalization in answer-set programming. In AAAI. AAAI Press, 2694\u20132702."},{"key":"S1471068420000332_ref28","doi-asserted-by":"crossref","unstructured":"28. Gebser, M. , Kaufmann, B. , Romero, J. , Otero, R. , Schaub, T. , and Wanko, P. 2013. Domain-specific heuristics in answer set programming. In AAAI. AAAI Press.","DOI":"10.1609\/aaai.v27i1.8585"},{"key":"S1471068420000332_ref12","unstructured":"12. Cabalar, P. , Kaminski, R. , Morkisch, P. , and Schaub, T. 2019. telingo = ASP + time. In LPNMR. Lecture Notes in Computer Science, vol. 11481. Springer, 256\u2013269."},{"key":"S1471068420000332_ref44","unstructured":"44. Taupe, R. , Schekotihin, K. , Sch\u00fcller, P. , Weinzierl, A. , and Friedrich, G. 2019. Exploiting partial knowledge in declarative domain-specific heuristics for ASP. In ICLP Technical Communications. EPTCS, vol. 306. 22\u201335."},{"key":"S1471068420000332_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2015.09.008"},{"key":"S1471068420000332_ref23","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/j.artint.2010.04.002","article-title":"Semantics and complexity of recursive aggregates in answer set programming","volume":"1","author":"Faber","year":"2011","journal-title":"Artif. Intell. 175"},{"key":"S1471068420000332_ref39","unstructured":"39. Moskewicz, M. W. , Madigan, C. F. , Zhao, Y. , Zhang, L. , and Malik, S. 2001. Chaff: Engineering an efficient SAT solver. In DAC. ACM, 530\u2013535."},{"key":"S1471068420000332_ref2","unstructured":"2. Alviano, M. , Calimeri, F. , Charwat, G. , Dao-Tran, M. , Dodaro, C. , Ianni, G. , Krennwallner, T. , Kronegger, M. , Oetsch, J. , Pfandler, A. , P\u00fchrer, J. , Redl, C. , Ricca, F. , Schneider, P. , Schwengerer, M. , Spendier, L. K. , Wallner, J. P. , and Xiao, G. 2013. The fourth answer set programming competition: Preliminary report. In LPNMR. LNCS, vol. 8148. Springer, 42\u201353."},{"key":"S1471068420000332_ref5","unstructured":"5. Anger, C. , Gebser, M. , Janhunen, T. , and Schaub, T. 2006. What\u2019s a head without a body? In ECAI. Frontiers in Artificial Intelligence and Applications, vol. 141. IOS Press, 769\u2013770."},{"key":"S1471068420000332_ref3","volume-title":"Computer Science","volume":"10377","author":"Alviano","year":"2017"},{"key":"S1471068420000332_ref7","first-page":"399","article-title":"Predicting learnt clauses quality in modern SAT solvers","author":"Audemard","year":"2009","journal-title":"In IJCAI."},{"key":"S1471068420000332_ref25","unstructured":"25. Friedrich, G. , Ryabokon, A. , Falkner, A. A. , Haselb\u00f6ck, A. , Schenner, G. , and Schreiner, H. 2011. (Re)configuration using answer set programming. In Configuration Workshop. CEUR Workshop Proceedings, vol. 755. CEUR-WS.org."},{"key":"S1471068420000332_ref29","unstructured":"29. Gebser, M. , Kaufmann, B. , and Schaub, T. 2012. Conflict-driven answer set solving: From theory to practice. Artif. Intell. 187, 52\u201389."},{"key":"S1471068420000332_ref16","unstructured":"16. Clark, K. L. 1977. Negation as failure. In Logic and Data Bases. Advances in Data Base Theory. Plemum Press, New York, 293\u2013322."},{"key":"S1471068420000332_ref38","unstructured":"38. Marple, K. , Salazar, E. , and Gupta, G. 2017. Computing stable models of normal logic programs without grounding. CoRR abs\/1709.00501."}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068420000332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T03:27:43Z","timestamp":1668828463000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068420000332\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":49,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["S1471068420000332"],"URL":"https:\/\/doi.org\/10.1017\/s1471068420000332","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}