[Back]

T. Dell´Armi, W. Faber, G. Ielpa, N. Leone, G. Pfeifer:
"Aggregate Functions in DLV";
in: "Answer Set Programming - Advances in Theory and Implementation", M. De Vos, A. Provetti (ed.); CEUR-WS.org, 2003, ISSN: 1613-0073, 274 - 288.

Disjunctive Logic Programming (DLP) is a very expressive formalism:
it allows for expressing every property of finite structures that is
decidable in the complexity class Σ^P₂ (= NP^NP) . Despite this high expressiveness, there are some simple properties, often arising in real-world applications, which cannot be encoded in a
simple and natural manner. Especially properties that require the use
of arithmetic operators (like sum, count, or min) on a set of elements
satisfying some conditions, cannot be naturally expressed in classic
DLP.

To overcome this deficiency, we extend DLP by aggregate functions. In
contrast to a previous proposal, we also consider the case of
unstratified aggregates. We formally define the semantics of the new
language (called DLP^A) by means of a generalization of the
Gelfond-Lifschitz transformation, and illustrate the use of the new
constructs on relevant knowledge-based problems. We analyze the
computational complexity of DLP^A, showing that the addition of
aggregates does not bring a higher cost in that respect. And we
provide an implementation of DLP^A in DLV -- the state-of-the-art
DLP system -- and report on experiments which confirm the usefulness
of the proposed extension also for the efficiency of the computation.

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04404476

http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS//Vol-78/asp03-final-dellarmi.pdf