{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T01:32:34Z","timestamp":1720488754932},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"4-5","license":[{"start":{"date-parts":[[2015,9,3]],"date-time":"2015-09-03T00:00:00Z","timestamp":1441238400000},"content-version":"unspecified","delay-in-days":64,"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":[[2015,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Disjunctive Answer Set Programming is a powerful declarative programming paradigm with complexity beyond NP. Identifying classes of programs for which the consistency problem is in NP is of interest from the theoretical standpoint and can potentially lead to improvements in the design of answer set programming solvers. One of such classes consists of <jats:italic>dual-normal programs<\/jats:italic>, where the number of positive body atoms in proper rules is at most one. Unlike other classes of programs, dual-normal programs have received little attention so far. In this paper we study this class. We relate dual-normal programs to propositional theories and to normal programs by presenting several inter-translations. With the translation from dual-normal to normal programs at hand, we introduce the novel class of <jats:italic>body-cycle<\/jats:italic> free programs, which are in many respects dual to head-cycle free programs. We establish the expressive power of dual-normal programs in terms of SE- and UE-models, and compare them to normal programs. We also discuss the complexity of deciding whether dual-normal programs are strongly and uniformly equivalent.<\/jats:p>","DOI":"10.1017\/s1471068415000186","type":"journal-article","created":{"date-parts":[[2015,9,3]],"date-time":"2015-09-03T08:21:21Z","timestamp":1441268481000},"page":"495-510","source":"Crossref","is-referenced-by-count":3,"title":["Dual-normal logic programs \u2013 the forgotten class"],"prefix":"10.1017","volume":"15","author":[{"given":"JOHANNES K.","family":"FICHTE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MIROS\u0141AW","family":"TRUSZCZY\u0143SKI","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":[[2015,9,3]]},"reference":[{"key":"S1471068415000186_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530761"},{"key":"S1471068415000186_ref11","doi-asserted-by":"crossref","DOI":"10.2200\/S00457ED1V01Y201211AIM019","volume-title":"Answer Set Solving in Practice","author":"Gebser","year":"2012"},{"key":"S1471068415000186_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S147106840999010X"},{"key":"S1471068415000186_ref17","first-page":"603","volume-title":"Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR 1992)","author":"Lifschitz","year":"1992"},{"key":"S1471068415000186_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45402-0_6"},{"key":"S1471068415000186_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S1471068415000186_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037171"},{"key":"S1471068415000186_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-006-9026-1"},{"key":"S1471068415000186_ref14","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.16.35-86"},{"key":"S1471068415000186_ref10","first-page":"320","volume-title":"Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI 2013)","author":"Fichte","year":"2013"},{"key":"S1471068415000186_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068410000463"},{"key":"S1471068415000186_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/1119439.1119440"},{"key":"S1471068415000186_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(84)90014-1"},{"key":"S1471068415000186_ref3","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068415000186_ref5","first-page":"224","volume-title":"Proceedings 19th International Conference on Logic Programming (ICLP 2003)","author":"Eiter","year":"2003"},{"key":"S1471068415000186_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/1243996.1244000"},{"key":"S1471068415000186_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45241-9_12"},{"key":"S1471068415000186_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S147106841100007X"},{"key":"S1471068415000186_ref6","doi-asserted-by":"publisher","DOI":"10.1080\/11663081.2013.799318"},{"key":"S1471068415000186_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49201-1_21"},{"key":"S1471068415000186_ref13","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt393"},{"key":"S1471068415000186_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/383779.383783"},{"key":"S1471068415000186_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536399"},{"key":"S1471068415000186_ref7","first-page":"447","volume-title":"Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning (KR 2004)","author":"Eiter","year":"2004"}],"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\/S1471068415000186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T23:32:32Z","timestamp":1555803152000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068415000186\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7]]},"references-count":24,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["S1471068415000186"],"URL":"https:\/\/doi.org\/10.1017\/s1471068415000186","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7]]}}}