{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T00:20:34Z","timestamp":1768436434807,"version":"3.49.0"},"reference-count":42,"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>Standard answer set programming (ASP) targets at solving search problems from the first level of the polynomial time hierarchy (PH). Tackling search problems beyond NP using ASP is less straightforward. The class of disjunctive logic programs offers the most prominent way of reaching the second level of the PH, but encoding respective hard problems as disjunctive programs typically requires sophisticated techniques such as saturation or meta-interpretation. The application of such techniques easily leads to encodings that are inaccessible to non-experts. Furthermore, while disjunctive ASP solvers often rely on calls to a (co-)NP oracle, it may be difficult to detect from the input program where the oracle is being accessed. In other formalisms, such as Quantified Boolean Formulas (QBFs), the interface to the underlying oracle is more transparent as it is explicitly recorded in the quantifier prefix of a formula. On the other hand, ASP has advantages over QBFs from the modeling perspective. The rich high-level languages such as ASP-Core-2 offer a wide variety of primitives that enable concise and natural encodings of search problems. In this paper, we present a novel logic programming\u2013based modeling paradigm that combines the best features of ASP and QBFs. We develop so-called<jats:italic>combined logic programs<\/jats:italic>in which oracles are directly cast as (normal) logic programs themselves. Recursive incarnations of this construction enable logic programming on arbitrarily high levels of the PH. We develop a proof-of-concept implementation for our new paradigm.<\/jats:p>","DOI":"10.1017\/s1471068416000387","type":"journal-article","created":{"date-parts":[[2016,10,15]],"date-time":"2016-10-15T21:28:20Z","timestamp":1476566900000},"page":"570-586","source":"Crossref","is-referenced-by-count":13,"title":["Stable-unstable semantics: Beyond NP with normal logic programs"],"prefix":"10.1017","volume":"16","author":[{"given":"BART","family":"BOGAERTS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TOMI","family":"JANHUNEN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SHAHAB","family":"TASHARROFI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,10,14]]},"reference":[{"key":"S1471068416000387_ref32","unstructured":"Leone N. , Rosati R. and Scarcello F. 2001. Enhancing answer set planning. In Proceedings of the IJCAI-01 Workshop on Planning under Uncertainty and Incomplete Information. Seattle, Washington, USA."},{"key":"S1471068416000387_ref12","first-page":"84","volume-title":"Proceedings of the 9th International Conference on Logic Programming and Non-monotonic Reasoning, LPNMR 2007","author":"Denecker","year":"2007"},{"key":"S1471068416000387_ref24","doi-asserted-by":"publisher","DOI":"10.1142\/S0218194096000053"},{"key":"S1471068416000387_ref33","first-page":"23","volume-title":"Proceedings of the 16th International Conference on Logic Programming, ICLP 1999","author":"Lifschitz","year":"1999"},{"key":"S1471068416000387_ref19","first-page":"368","volume-title":"Proceedings of the 13th International Conference on Logic Programming and Non-monotonic Reasoning, LPNMR 2015","author":"Gebser","year":"2015"},{"key":"S1471068416000387_ref36","doi-asserted-by":"crossref","first-page":"12","DOI":"10.4064\/fm-44-1-12-36","article-title":"On a generalization of quantifiers.","volume":"44","author":"Mostowski","year":"1957","journal-title":"Fundamenta Mathematicae"},{"key":"S1471068416000387_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530761"},{"key":"S1471068416000387_ref9","unstructured":"Calimeri F. , Faber W. , Gebser M. , Ianni G. , Kaminski R. , Krennwallner T. , Leone N. , Ricca F. and Schaub T. 2013. ASP-Core-2 input language format. Tech. rep., ASP Standardization Working Group."},{"key":"S1471068416000387_ref30","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068415000265"},{"key":"S1471068416000387_ref31","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"S1471068416000387_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-007-9082-1"},{"key":"S1471068416000387_ref15","first-page":"289","volume-title":"Proceedings of the 4th International Conference on Logic Programming and Non-monotonic Reasoning, LPNMR 1997","author":"Eiter","year":"1997"},{"key":"S1471068416000387_ref25","first-page":"591","volume-title":"Proceedings of the 10th International Conference on Logic Programming and Non-monotonic Reasoning, LPNMR 2009","author":"Grasso","year":"2009"},{"key":"S1471068416000387_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"S1471068416000387_ref41","first-page":"1","volume-title":"Proceedings of the 5th Annual ACM Symposium on Theory of Computing, STOC 1973","author":"Stockmeyer","year":"1973"},{"key":"S1471068416000387_ref34","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","article-title":"First order predicate logic with generalized quantifiers","volume":"32","author":"Lindstr\u00f6m","year":"1966","journal-title":"Theoria"},{"key":"S1471068416000387_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.05.004"},{"key":"S1471068416000387_ref39","first-page":"412","volume-title":"Proceedings of the 17th European Conference on Artificial Intelligence, ECAI 2006","author":"Oikarinen","year":"2006"},{"key":"S1471068416000387_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S147106841400009X"},{"key":"S1471068416000387_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068405002577"},{"key":"S1471068416000387_ref40","doi-asserted-by":"crossref","first-page":"35","DOI":"10.3233\/FI-2010-357","article-title":"A logic-based system for e-tourism.","volume":"105","author":"Ricca","year":"2010","journal-title":"Fundam. Inform."},{"key":"S1471068416000387_ref3","first-page":"74","volume-title":"Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning, KR 2016","author":"Bogaerts","year":"2016"},{"key":"S1471068416000387_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068415000150"},{"key":"S1471068416000387_ref1","first-page":"69","volume-title":"Proceedings of the 13th International Conference on Logic Programming and Non-monotonic Reasoning, LPNMR 2015","author":"Andres","year":"2015"},{"key":"S1471068416000387_ref29","first-page":"978","volume-title":"Proceedings of the 30th AAAI Conference on Artificial Intelligence, AAAI 2016","author":"Janhunen","year":"2016"},{"key":"S1471068416000387_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S1471068416000387_ref21","first-page":"266","volume-title":"Proceedings of the 9th International Conference on Logic Programming and Non-monotonic Reasoning, LPNMR 2007","author":"Gebser","year":"2007"},{"key":"S1471068416000387_ref27","doi-asserted-by":"crossref","unstructured":"Janhunen T. , Gebser M. , Rintanen J. , Nyman H. , Pensar J. and Corander J. 2015. Learning discrete decomposable graphical models via constraint optimization. Statistics and Computing. Advance access.","DOI":"10.1007\/s11222-015-9611-4"},{"key":"S1471068416000387_ref22","first-page":"1070","volume-title":"Proceedings of the Fifth International Conference on Logic Programming, ICLP 1988","author":"Gelfond","year":"1988"},{"key":"S1471068416000387_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2015.09.008"},{"key":"S1471068416000387_ref17","first-page":"368","volume-title":"Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, FOCS 1991","author":"Emerson","year":"1991"},{"key":"S1471068416000387_ref13","first-page":"422","volume-title":"Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning, KR 2008","author":"Drescher","year":"2008"},{"key":"S1471068416000387_ref6","first-page":"187","volume-title":"Proceedings of the 12th International Conference on Logic Programming and Non-monotonic Reasoning, LPNMR 2013","author":"Bomanson","year":"2013"},{"key":"S1471068416000387_ref38","first-page":"169","volume-title":"Proceedings of the 3rd International Symposium on Practical Aspects of Declarative Languages, PADL 2001","author":"Nogueira","year":"2001"},{"key":"S1471068416000387_ref4","first-page":"307","volume-title":"Proceedings of the AAAI-16 Workshop on Beyond NP","author":"Bogaerts","year":"2016"},{"key":"S1471068416000387_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000329"},{"key":"S1471068416000387_ref28","doi-asserted-by":"publisher","DOI":"10.1145\/1119439.1119440"},{"key":"S1471068416000387_ref37","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930122475"},{"key":"S1471068416000387_ref42","first-page":"1290","volume-title":"Proceedings of the 14th International Conference on Engineering Design, ICED 2003","author":"Tiihonen","year":"2003"},{"key":"S1471068416000387_ref11","unstructured":"Denecker M. , Lierler Y. , Truszczy\u0144ski M. and Vennekens J. 2012. A Tarskian informal semantics for answer set programming. In Technical Communications of the 28th International Conference on Logic Programming, ICLP 2012. LIPIcs, vol. 17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Budapest, Hungary, 277\u2013289."},{"key":"S1471068416000387_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536399"},{"key":"S1471068416000387_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000155"}],"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\/S1471068416000387","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T23:36:12Z","timestamp":1718840172000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068416000387\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":42,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["S1471068416000387"],"URL":"https:\/\/doi.org\/10.1017\/s1471068416000387","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}