{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T11:15:18Z","timestamp":1778670918722,"version":"3.51.4"},"reference-count":48,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2008,11,1]],"date-time":"2008-11-01T00:00:00Z","timestamp":1225497600000},"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":[[2008,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Disjunctive logic programming (DLP) is a very expressive formalism. It allows for\n                    expressing every property of finite structures that is decidable in the\n                    complexity class \u03a3<jats:sup><jats:italic>P<\/jats:italic><\/jats:sup><jats:sub>2<\/jats:sub>(=NP<jats:sup>NP<\/jats:sup>). Despite this high expressiveness, there\n                    are some simple properties, often arising in real-world applications, which\n                    cannot be encoded in a simple and natural manner. Especially properties that\n                    require the use of arithmetic operators (like sum, times, or count) on a set or\n                    multiset of elements, which satisfy some conditions, cannot be naturally\n                    expressed in classic DLP. To overcome this deficiency, we extend DLP by\n                    aggregate functions in a conservative way. In particular, we avoid the\n                    introduction of constructs with disputed semantics, by requiring aggregates to\n                    be stratified. We formally define the semantics of the extended language (called <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S1471068408003323_char1\"\/><\/jats:private-char>), and illustrate how it can be profitably used for representing\n                    knowledge. Furthermore, we analyze the computational complexity of <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S1471068408003323_char1\"\/><\/jats:private-char>, showing that the addition of aggregates does not bring a higher\n                    cost in that respect. Finally, we provide an implementation of <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S1471068408003323_char1\"\/><\/jats:private-char> in DLV\u2014a state-of-the-art DLP system\u2014and\n                    report on experiments which confirm the usefulness of the proposed extension\n                    also for the efficiency of computation.<\/jats:p>","DOI":"10.1017\/s1471068408003323","type":"journal-article","created":{"date-parts":[[2008,5,8]],"date-time":"2008-05-08T06:39:48Z","timestamp":1210228788000},"page":"545-580","source":"Crossref","is-referenced-by-count":47,"title":["Design and implementation of aggregate functions in the DLV\n                        system"],"prefix":"10.1017","volume":"8","author":[{"given":"WOLFGANG","family":"FABER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GERALD","family":"PFEIFER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"NICOLA","family":"LEONE","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TINA","family":"DELL'ARMI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GIUSEPPE","family":"IELPA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2008,11,1]]},"reference":[{"key":"S1471068408003323_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/11546207_10"},{"key":"S1471068408003323_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(84)90014-1"},{"key":"S1471068408003323_ref5","unstructured":"Calimeri F. , Faber W. , Leone N. and Perri S. 2005. Declarative and computational properties of logic programs with aggregates. In Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05). 406\u2013411."},{"key":"S1471068408003323_ref48","volume-title":"Principles of Database and Knowledge Base\n                    Systems","author":"Ullman","year":"1989"},{"key":"S1471068408003323_ref23","doi-asserted-by":"crossref","unstructured":"Gebser M. , Liu L. , Namasivayam G. , Neumann A. , Schaub T. and Truszczy\u0144ski M. 2007. The first answer set programming system competition. In Logic Programming and Nonmonotonic Reasoning\u20149th International Conference, LPNMR'07, C. Baral, G. Brewka, and J. Schlipf, Eds. Lecture Notes in Computer Science, vol. 4483. Springer-Verlag, Tempe, AZ, 3\u201317.","DOI":"10.1007\/978-3-540-72200-7_3"},{"key":"S1471068408003323_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46767-X_13"},{"key":"S1471068408003323_ref29","first-page":"280","volume-title":"Logic Programming and Nonmonotonic Reasoning\u20146th\n                        International Conference, LPNMR'01, Vienna, Austria","author":"Leone","year":"2001"},{"key":"S1471068408003323_ref41","first-page":"207","volume-title":"Proceedings of the 7th International Conference on Logic Programming\n                        and Non-Monotonic Reasoning (LPNMR-7)","author":"Pelov","year":"2004"},{"key":"S1471068408003323_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45632-5_16"},{"key":"S1471068408003323_ref42","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-934613-40-8.50009-9"},{"key":"S1471068408003323_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/11546207_40"},{"key":"S1471068408003323_ref32","first-page":"163","volume-title":"W(C)LP 19th Workshop on (Constraint) Logic Programming, Ulm,\n                    Germany","author":"Lierler","year":"2005"},{"key":"S1471068408003323_ref12","first-page":"290","volume-title":"Proceedings of the 4th International Conference on Logic Programming\n                        and Nonmonotonic Reasoning (LPNMR-97)","author":"Eiter","year":"1997"},{"key":"S1471068408003323_ref27","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502100"},{"key":"S1471068408003323_ref33","first-page":"701","volume-title":"Proceedings of the 20th National Conference on Artificial\n                        Intelligence (AAAI'05)","author":"Liu","year":"2005"},{"key":"S1471068408003323_ref34","first-page":"154","volume-title":"Proceedings of the 7th International Conference on Logic Programming\n                        and Non-Monotonic Reasoning (LPNMR-7)","author":"Marek","year":"2004"},{"key":"S1471068408003323_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530761"},{"key":"S1471068408003323_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/69.50907"},{"key":"S1471068408003323_ref40","unstructured":"Pelov N. 2004. Semantics of Logic Programs with Aggregates. Ph.D. thesis, Katholieke Univer-siteit Leuven, Leuven, Belgium."},{"key":"S1471068408003323_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"key":"S1471068408003323_ref16","unstructured":"Faber W. , Leone N. , Mateis C. and Pfeifer G. 1999. Using database optimization techniques for nonmonotonic reasoning. In Proceedings of the 7th International Workshop on Deductive Databases and Logic Programming (DDLP'99), INAP Organizing Committee, Ed. Prolog Association of Japan, 135\u2013139."},{"key":"S1471068408003323_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S1471068408003323_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543357"},{"key":"S1471068408003323_ref43","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1453"},{"key":"S1471068408003323_ref36","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116836"},{"key":"S1471068408003323_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-934613-40-8.50006-3"},{"key":"S1471068408003323_ref18","unstructured":"Faber W. , Leone N. and Pfeifer G. 2001. Experimenting with heuristics for answer set programming. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI) 2001. Morgan Kaufmann Publishers, Seattle, WA, USA, 635\u2013640."},{"key":"S1471068408003323_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001923"},{"key":"S1471068408003323_ref22","first-page":"386","volume-title":"Twentieth\n                        International Joint Conference on Artificial Intelligence\n                    (IJCAI-07)","author":"Gebser","year":"2007"},{"key":"S1471068408003323_ref7","unstructured":"Dell'Armi T. , Faber W. , Ielpa G. , Leone N. and Pfeifer G. 2003. Aggregate functions in DLV. In Proceedings ASP03\u2014Answer Set Programming: Advances in Theory and Implementation, M. de Vos and A. Provetti, Eds. Messina, Italy, 274\u2013288. Online at http:\/\/CEUR-WS.org\/Vol-78\/"},{"key":"S1471068408003323_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-1567-8_4"},{"key":"S1471068408003323_ref28","doi-asserted-by":"publisher","DOI":"10.1109\/69.729729"},{"key":"S1471068408003323_ref4","doi-asserted-by":"publisher","DOI":"10.1109\/69.877512"},{"key":"S1471068408003323_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(98)00057-8"},{"key":"S1471068408003323_ref31","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2630"},{"key":"S1471068408003323_ref35","first-page":"219","volume-title":"Proceedings of the 9th International Workshop on Non-Monotonic\n                        Reasoning (NMR'2002)","author":"Marek","year":"2002"},{"key":"S1471068408003323_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0000066"},{"key":"S1471068408003323_ref30","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"S1471068408003323_ref39","first-page":"107","volume-title":"Proceedings of the 5th International Conference on Logic Programming\n                        and Nonmonotonic Reasoning (LPNMR'99)","author":"Niemel\u00e4","year":"1999"},{"key":"S1471068408003323_ref44","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00187-X"},{"key":"S1471068408003323_ref19","first-page":"200","volume-title":"Proceedings of the 9th European Conference on\n                        Artificial Intelligence (JELIA 2004)","author":"Faber","year":"2004"},{"key":"S1471068408003323_ref45","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068406002936"},{"key":"S1471068408003323_ref46","unstructured":"Son T. C. , Pontelli E. and Elkabani I. 2005. On logic programming with aggregates. Technical Report NMSU-CS-2005-006, New Mexico State University."},{"key":"S1471068408003323_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01536399"},{"key":"S1471068408003323_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/11546207_4"},{"key":"S1471068408003323_ref14","unstructured":"Faber W. 2002. Enhancing Efficiency and Expressiveness in Answer Set Programming Systems. Ph.D. thesis, Institut f\u00fcr Informationssysteme, Technische Universit\u00e4t Wien."},{"key":"S1471068408003323_ref47","unstructured":"Syrj\u00e4nen T. 2002. Lparse 1.0 User's Manual. http:\/\/www.tcs.hut.fi\/Software\/smodels\/lparse.ps.gz."},{"key":"S1471068408003323_ref38","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90124-X"}],"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\/S1471068408003323","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T15:38:00Z","timestamp":1554046680000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068408003323\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":48,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["S1471068408003323"],"URL":"https:\/\/doi.org\/10.1017\/s1471068408003323","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,11]]}}}