{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T07:15:49Z","timestamp":1712301349174},"reference-count":36,"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>Aggregation functions are widely used in answer set programming for representing and reasoning on knowledge involving sets of objects collectively. Current implementations simplify the structure of programs in order to optimize the overall performance. In particular, aggregates are rewritten into simpler forms known as monotone aggregates. Since the evaluation of normal programs with monotone aggregates is in general on a lower complexity level than the evaluation of normal programs with arbitrary aggregates, any faithful translation function must introduce disjunction in rule heads in some cases. However, no function of this kind is known. The paper closes this gap by introducing a polynomial, faithful, and modular translation for rewriting common aggregation functions into the simpler form accepted by current solvers. A prototype system allows for experimenting with arbitrary recursive aggregates, which are also supported in the recent version 4.5 of the grounder<jats:sc>gringo<\/jats:sc>, using the methods presented in this paper.<\/jats:p>","DOI":"10.1017\/s1471068415000228","type":"journal-article","created":{"date-parts":[[2015,9,3]],"date-time":"2015-09-03T04:21:21Z","timestamp":1441254081000},"page":"559-573","source":"Crossref","is-referenced-by-count":17,"title":["Rewriting recursive aggregates in answer set programming: back to monotonicity"],"prefix":"10.1017","volume":"15","author":[{"given":"MARIO","family":"ALVIANO","sequence":"first","affiliation":[]},{"given":"WOLFGANG","family":"FABER","sequence":"additional","affiliation":[]},{"given":"MARTIN","family":"GEBSER","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2015,9,3]]},"reference":[{"key":"S1471068415000228_ref32","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068406002973"},{"key":"S1471068415000228_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068408003323"},{"key":"S1471068415000228_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.002"},{"key":"S1471068415000228_ref22","first-page":"1070","volume-title":"Fifth International Conference and Symposium on Logic Programming (ICLP 1988)","author":"Gelfond","year":"1988"},{"key":"S1471068415000228_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001923"},{"key":"S1471068415000228_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30743-0_24"},{"key":"S1471068415000228_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970401"},{"key":"S1471068415000228_ref8","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1007\/978-3-319-11558-0_12","volume-title":"Fourteenth European Conference on Logics in Artificial Intelligence (JELIA 2014)","author":"Bomanson","year":"2014"},{"key":"S1471068415000228_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-006-9033-2"},{"key":"S1471068415000228_ref9","first-page":"187","volume-title":"Twelfth International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR 2013)","author":"Bomanson","year":"2013"},{"key":"S1471068415000228_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000222"},{"key":"S1471068415000228_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068412000233"},{"key":"S1471068415000228_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536399"},{"key":"S1471068415000228_ref1","doi-asserted-by":"crossref","unstructured":"Abseher M. , Bliem B. , Charwat G. , Dusberger F. and Woltran S. 2014. Computing secure sets in graphs using answer set programming. In Seventh International Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2014), D. Inclezan and M. Maratea , Eds.","DOI":"10.1093\/logcom\/exv060"},{"key":"S1471068415000228_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.04.002"},{"key":"S1471068415000228_ref26","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.16.35-86"},{"key":"S1471068415000228_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.05.001"},{"key":"S1471068415000228_ref28","doi-asserted-by":"publisher","DOI":"10.1145\/383779.383783"},{"key":"S1471068415000228_ref29","doi-asserted-by":"publisher","DOI":"10.1017\/S147106841100038X"},{"key":"S1471068415000228_ref31","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1613\/jair.2009","article-title":"Properties and applications of programs with monotone and convex constraints","volume":"27","author":"Liu","year":"2006","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S1471068415000228_ref36","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001819"},{"key":"S1471068415000228_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000325"},{"key":"S1471068415000228_ref6","first-page":"16","volume-title":"AAAI 2011 Spring Symposium on Logical Formalizations of Commonsense Reasoning (SS-11-06)","author":"Bartholomew","year":"2011"},{"key":"S1471068415000228_ref12","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1613\/jair.4175","article-title":"Efficient HEX-program evaluation based on unfounded sets","volume":"49","author":"Eiter","year":"2014","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S1471068415000228_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068415000228_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2009.11.016"},{"key":"S1471068415000228_ref15","first-page":"97","volume-title":"Nineteenth International Joint Conference on Artificial Intelligence (IJCAI 2005)","author":"Eiter","year":"2005"},{"key":"S1471068415000228_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S1471068415000228_ref35","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068406002936"},{"key":"S1471068415000228_ref4","first-page":"67","volume-title":"Twelfth International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR 2013)","author":"Alviano","year":"2013"},{"key":"S1471068415000228_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00187-X"},{"key":"S1471068415000228_ref2","first-page":"487","article-title":"Unfounded sets and well-founded semantics of answer set programs with aggregates","volume":"42","author":"Alviano","year":"2011","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S1471068415000228_ref5","first-page":"282","volume-title":"First International Workshop on Datalog 2.0 (Datalog Reloaded)","author":"Alviano","year":"2010"},{"key":"S1471068415000228_ref7","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1852"},{"key":"S1471068415000228_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.04.001"},{"key":"S1471068415000228_ref20","first-page":"345","volume-title":"Eleventh International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR 2011)","author":"Gebser","year":"2011"}],"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\/S1471068415000228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,30]],"date-time":"2019-08-30T00:20:07Z","timestamp":1567124407000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068415000228\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7]]},"references-count":36,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["S1471068415000228"],"URL":"https:\/\/doi.org\/10.1017\/s1471068415000228","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7]]}}}