{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,15]],"date-time":"2023-01-15T11:28:04Z","timestamp":1673782084751},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2013,8,9]],"date-time":"2013-08-09T00:00:00Z","timestamp":1376006400000},"content-version":"unspecified","delay-in-days":0,"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":[[2014,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Adapting techniques from database theory in order to optimize Answer Set Programming (ASP) systems, and in particular the grounding components of ASP systems, is an important topic in ASP. In recent years, the Magic Set method has received some interest in this setting, and a variant of it, called Dynamic Magic Set, has been proposed for ASP. However, this technique has a caveat, because it is not correct (in the sense of being query-equivalent) for all ASP programs. In a recent work, a large fragment of ASP programs, referred to as<jats:italic>super-coherent programs<\/jats:italic>, has been identified, for which Dynamic Magic Set is correct. The fragment contains all programs which possess at least one answer set, no matter which set of facts is added to them. Two open question remained: How complex is it to determine whether a given program is super-coherent? Does the restriction to super-coherent programs limit the problems that can be solved? Especially the first question turned out to be quite difficult to answer precisely. In this paper, we formally prove that deciding whether a propositional program is super-coherent is \u03a0<jats:sub>3<\/jats:sub><jats:sup><jats:italic>P<\/jats:italic><\/jats:sup>-complete in the disjunctive case, while it is \u03a0<jats:sub>2<\/jats:sub><jats:sup><jats:italic>P<\/jats:italic><\/jats:sup>-complete for normal programs. The hardness proofs are the difficult part in this endeavor: We proceed by characterizing the reductions by the models and reduct models which the ASP programs should have, and then provide instantiations that meet the given specifications. Concerning the second question, we show that all relevant ASP reasoning tasks can be transformed into tasks over super-coherent programs, although this transformation is more of theoretical than practical interest.<\/jats:p>","DOI":"10.1017\/s147106841300001x","type":"journal-article","created":{"date-parts":[[2013,8,9]],"date-time":"2013-08-09T12:46:40Z","timestamp":1376052400000},"page":"339-361","source":"Crossref","is-referenced-by-count":3,"title":["Complexity of super-coherence problems in ASP"],"prefix":"10.1017","volume":"14","author":[{"given":"MARIO","family":"ALVIANO","sequence":"first","affiliation":[]},{"given":"WOLFGANG","family":"FABER","sequence":"additional","affiliation":[]},{"given":"STEFAN","family":"WOLTRAN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2013,8,9]]},"reference":[{"key":"S147106841300001X_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.05.006"},{"key":"S147106841300001X_ref2","doi-asserted-by":"crossref","first-page":"125","DOI":"10.3233\/AIC-2011-0492","article-title":"Dynamic magic sets and super-coherent answer set programs","volume":"24","author":"Alviano","year":"2011","journal-title":"AI Communications"},{"key":"S147106841300001X_ref29","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":"Fundamenta Informaticae"},{"key":"S147106841300001X_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.04.008"},{"key":"S147106841300001X_ref1","unstructured":"Alviano M. and Faber W. 2010. Dynamic magic sets for super-consistent answer set programs. In Proceedings of the 3rd Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2010), M. Balduccini and S. Woltran, Eds."},{"key":"S147106841300001X_ref16","first-page":"97","volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI'05)","author":"Eiter","year":"2005"},{"key":"S147106841300001X_ref20","doi-asserted-by":"publisher","DOI":"10.1145\/1119439.1119440"},{"key":"S147106841300001X_ref31","volume-title":"Principles of Database and Knowledge Base Systems","author":"Ullman","year":"1989"},{"key":"S147106841300001X_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/1243996.1244000"},{"key":"S147106841300001X_ref10","first-page":"422","volume-title":"Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008)","author":"Drescher","year":"2008"},{"key":"S147106841300001X_ref28","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1451"},{"key":"S147106841300001X_ref27","first-page":"458","volume-title":"Proceedings of the 22nd National Conference on Artificial Intelligence (AAAI'07)","author":"Oetsch","year":"2007"},{"key":"S147106841300001X_ref30","doi-asserted-by":"publisher","DOI":"10.1017\/S147106841100007X"},{"key":"S147106841300001X_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530761"},{"key":"S147106841300001X_ref12","first-page":"447","volume-title":"Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning (KR 2004)","author":"Eiter","year":"2004"},{"key":"S147106841300001X_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90285-N"},{"key":"S147106841300001X_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"S147106841300001X_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543357"},{"key":"S147106841300001X_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536399"},{"key":"S147106841300001X_ref5","first-page":"1","volume-title":"Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems","author":"Bancilhon","year":"1986"},{"key":"S147106841300001X_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S147106841300001X_ref19","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1185840"},{"key":"S147106841300001X_ref32","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80053-4"},{"key":"S147106841300001X_ref23","first-page":"447","volume-title":"Proceedings of Logic Programming and Nonmonotonic Reasoning \u2013 8th International Conference (LPNMR'05), Diamante, Italy, September 2005","author":"Lierler","year":"2005"},{"key":"S147106841300001X_ref25","unstructured":"Manna M. , Ruffolo M. , Oro E. , Alviano M. and Leone N. 2012. The HiLeX system for semantic information extraction. Transactions on Large-Scale Data and Knowledge-Centered Systems, 91\u2013125."},{"key":"S147106841300001X_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066286"},{"key":"S147106841300001X_ref9","first-page":"371","volume-title":"Proceedings of the the 20th International Conference on Logic Programming \u2013 ICLP'04","author":"Cumbo","year":"2004"},{"key":"S147106841300001X_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-934613-40-8.50006-3"},{"key":"S147106841300001X_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"key":"S147106841300001X_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(91)90038-Q"},{"key":"S147106841300001X_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(98)00057-8"},{"key":"S147106841300001X_ref24","first-page":"23","volume-title":"Proceedings of the 11th International Conference on Logic Programming (ICLP'94)","author":"Lifschitz","year":"1994"}],"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\/S147106841300001X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,1]],"date-time":"2020-08-01T18:57:25Z","timestamp":1596308245000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106841300001X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,9]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["S147106841300001X"],"URL":"https:\/\/doi.org\/10.1017\/s147106841300001x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8,9]]}}}