{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:45:21Z","timestamp":1762101921815,"version":"3.37.3"},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2016,10,14]],"date-time":"2016-10-14T00:00:00Z","timestamp":1476403200000},"content-version":"unspecified","delay-in-days":43,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Answer set programming (ASP) is a well-established logic programming language that offers an intuitive, declarative syntax for problem solving. In its traditional application, a fixed ASP program for a given problem is designed and the actual instance of the problem is fed into the program as a set of facts. This approach typically results in programs with comparably short and simple rules. However, as is known from complexity analysis, such an approach limits the expressive power of ASP; in fact, an entire NP-check can be encoded into a single large rule body of bounded arity that performs both a guess and a check within the same rule. Here, we propose a novel paradigm for encoding hard problems in ASP by making explicit use of large rules which depend on the actual instance of the problem. We illustrate how this new encoding paradigm can be used, providing examples of problems from the first, second, and even third level of the polynomial hierarchy. As state-of-the-art solvers are tuned towards short rules, rule decomposition is a key technique in the practical realization of our approach. We also provide some preliminary benchmarks which indicate that giving up the convenient way of specifying a fixed program can lead to a significant speed-up.<\/jats:p>","DOI":"10.1017\/s1471068416000338","type":"journal-article","created":{"date-parts":[[2016,10,15]],"date-time":"2016-10-15T21:28:20Z","timestamp":1476566900000},"page":"552-569","source":"Crossref","is-referenced-by-count":5,"title":["The power of non-ground rules in Answer Set Programming"],"prefix":"10.1017","volume":"16","author":[{"given":"MANUEL","family":"BICHLER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2077-7672","authenticated-orcid":false,"given":"MICHAEL","family":"MORAK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"STEFAN","family":"WOLTRAN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,10,14]]},"reference":[{"key":"S1471068416000338_ref13","doi-asserted-by":"crossref","unstructured":"Dermaku A. , Ganzow T. , Gottlob G. , McMahan B. J. , Musliu N. and Samer M. 2008. Heuristic methods for hypertree decomposition. In Proc. MICAI, 1\u201311.","DOI":"10.1007\/978-3-540-88636-5_1"},{"key":"S1471068416000338_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00179-X"},{"key":"S1471068416000338_ref10","doi-asserted-by":"crossref","unstructured":"Chandra A. K. and Merlin P. M. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proc. STOC, 77\u201390.","DOI":"10.1145\/800105.803397"},{"key":"S1471068416000338_ref5","unstructured":"Bichler M. 2015. Optimizing non-ground answer set programs via rule decomposition. BSc Thesis, TU Wien. http:\/\/dbai.tuwien.ac.at\/proj\/lpopt\/thesis.pdf."},{"key":"S1471068416000338_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068416000338_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"S1471068416000338_ref27","doi-asserted-by":"publisher","DOI":"10.1145\/1119439.1119440"},{"key":"S1471068416000338_ref32","doi-asserted-by":"crossref","first-page":"297","DOI":"10.3233\/FI-2009-180","article-title":"GASP: answer set programming with lazy grounding.","volume":"96","author":"Pal\u00f9","year":"2009","journal-title":"Fundam. Inform."},{"key":"S1471068416000338_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536399"},{"key":"S1471068416000338_ref12","unstructured":"de Cat B. , Denecker M. and Stuckey P. J. 2012. Lazy model expansion by incremental grounding. In Proc. ICLP, 201\u2013211."},{"key":"S1471068416000338_ref1","doi-asserted-by":"crossref","unstructured":"Alviano M. , Dodaro C. , Faber W. , Leone N. and Ricca F. 2013. WASP: A native ASP solver based on constraint learning. In Proc. LPNMR, 54\u201366.","DOI":"10.1007\/978-3-642-40564-8_6"},{"key":"S1471068416000338_ref7","unstructured":"Bonatti P. A. , Pontelli E. and Son T. C. 2008. Credulous resolution for answer set programming. In Proc. AAAI, 418\u2013423."},{"key":"S1471068416000338_ref23","unstructured":"Gelfond M. and Lifschitz V. 1988. The stable model semantics for logic programming. In Proc. ICLP\/SLP, 1070\u20131080."},{"key":"S1471068416000338_ref15","unstructured":"Eiter T. , Faber W. and Mushthofa M. 2010. Space efficient evaluation of ASP programs with bounded predicate arities. In Proc. AAAI, 303\u2013308."},{"key":"S1471068416000338_ref24","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568320"},{"key":"S1471068416000338_ref4","unstructured":"ASP-Core-2 2015. ASP Core 2 Standard, v2.03c. https:\/\/www.mat.unical.it\/aspcomp2013\/ASPStandardization. Accessed: 2016-04-28."},{"key":"S1471068416000338_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068405002577"},{"key":"S1471068416000338_ref31","unstructured":"Morak M. and Woltran S. 2012. Preprocessing of complex non-ground rules in answer set programming. In Proc. ICLP, 247\u2013258."},{"key":"S1471068416000338_ref20","doi-asserted-by":"crossref","DOI":"10.2200\/S00457ED1V01Y201211AIM019","volume-title":"Answer Set Solving in Practice","author":"Gebser","year":"2012"},{"key":"S1471068416000338_ref8","unstructured":"Brewka G. , Delgrande J. P. , Romero J. and Schaub T. 2015. asprin: Customizing answer set preferences without a headache. In Proc. AAAI, 1467\u20131474."},{"key":"S1471068416000338_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.04.001"},{"key":"S1471068416000338_ref2","unstructured":"Alviano M. , Faber W. , Leone N. , Perri S. , Pfeifer G. and Terracina G. 2010. The disjunctive datalog system DLV. In Datalog Reloaded. Revised Selected Papers, 282\u2013301."},{"key":"S1471068416000338_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"S1471068416000338_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-008-9086-5"},{"key":"S1471068416000338_ref19","doi-asserted-by":"crossref","unstructured":"Elkabani I. , Pontelli E. and Son T. C. 2005. Smodels A - A system for computing answer sets of logic programs with aggregates. In Proc. LPNMR, 427\u2013431.","DOI":"10.1007\/11546207_40"},{"key":"S1471068416000338_ref29","doi-asserted-by":"crossref","unstructured":"Lonsing F. , Bacchus F. , Biere A. , Egly U. and Seidl M. 2015. Enhancing search-based QBF solving by dynamic blocked clause elimination. In Proc. LPAR, 418\u2013433.","DOI":"10.1007\/978-3-662-48899-7_29"},{"key":"S1471068416000338_ref26","unstructured":"Gottlob G. and Schwentick T. 2012. Rewriting ontological queries into small nonrecursive datalog programs. In Proc. KR, 254\u2013263."},{"key":"S1471068416000338_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000329"},{"key":"S1471068416000338_ref28","unstructured":"Lef\u00e8vre C. , B\u00e9atrix C. , St\u00e9phan I. and Garcia L. 2015. ASPeRiX, a first order forward chaining approach for answer set computing. CoRR abs\/1503.07717."},{"key":"S1471068416000338_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00012-9"},{"key":"S1471068416000338_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"S1471068416000338_ref3","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"}],"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\/S1471068416000338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,26]],"date-time":"2020-09-26T17:49:16Z","timestamp":1601142556000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068416000338\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":32,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["S1471068416000338"],"URL":"https:\/\/doi.org\/10.1017\/s1471068416000338","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}