Contributions to Proceedings:
T. DellŽArmi, W. Faber, G. Ielpa, N. Leone, G. Pfeifer:
"Aggregate Functions in Disjunctive Logic Programming: Semantics,Complexity,and Implementation in DLV";
in: "Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI) 2003",
Elsevier Science Publishers,
Disjunctive Logic Programming (DLP) is a very expressive formalism:
it allows to express every property of finite structures that is
decidable in the complexity class ΣP2 (NPNP).
Despite the high expressiveness of DLP, there are some simple properties, often arising in
which cannot be encoded in a simple and natural manner.
Among these, properties requiring to apply some arithmetic operators
(like sum, times, count) on a set of elements satisfying some conditions,
cannot be naturally expressed in DLP.
To overcome this deficiency,
in this paper we extend DLP by aggregate functions.
We formally define the semantics of the new language, named
We show the usefulness of the new constructs on relevant
We analyze the computational complexity of DLPA, showing
that the addition of aggregates does not bring a higher cost in that respect.
We provide an implementation of the DLPA 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.
Online library catalogue of the TU Vienna:
Created from the Publication Database of the Vienna University of Technology.