Design and Implementation of Aggregate Functions in the DLV System
| dc.creator | Faber, Wolfgang | |
| dc.creator | Pfeifer, Gerald | |
| dc.creator | Leone, Nicola | |
| dc.creator | Dell'Armi, Tina | |
| dc.creator | Ielpa, Giuseppe | |
| dc.date | 2008-02-21 | |
| dc.date.accessioned | 2026-07-07T09:22:31Z | |
| dc.date.available | 2026-07-07T09:22:31Z | |
| dc.description | 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 SigmaP2 (= 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, times, or count) on a set or multiset of elements, which satisfy some conditions, cannot be naturally expressed in classic DLP. To overcome this deficiency, we extend DLP by aggregate functions in a conservative way. In particular, we avoid the introduction of constructs with disputed semantics, by requiring aggregates to be stratified. We formally define the semantics of the extended language (called DLP^A), and illustrate how it can be profitably used for representing knowledge. Furthermore, we analyze the computational complexity of DLP^A, showing that the addition of aggregates does not bring a higher cost in that respect. Finally, we provide an implementation of DLP^A in DLV -- a state-of-the-art DLP system -- and report on experiments which confirm the usefulness of the proposed extension also for the efficiency of computation. | |
| dc.description | 34 pages, 7 figures. This article has been accepted for publication in Theory and Practice of Logic Programming, Cambridge University Press | |
| dc.identifier | https://arxiv.org/abs/0802.3137 | |
| dc.identifier | http://arxiv.org/abs/0802.3137 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/155400 | |
| dc.subject | Artificial Intelligence | |
| dc.subject | Logic in Computer Science | |
| dc.subject | I.2.3; I.2.4; D.3.1; D.1.6 | |
| dc.title | Design and Implementation of Aggregate Functions in the DLV System | |
| dc.type | text |