Design and Implementation of Aggregate Functions in the DLV System

Details Design and Implementation of Aggregate Functions in the DLV System Design and Implementation of Aggregate Functions in the DLV System

2008-02-21

arxiv.org/abs/0802.3137v1

Computer Science

Artificial Intelligence

34 pages, 7 figures. This article has been accepted for publication in Theory and Practice of Logic Programming, Cambridge Uni

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Design and Implementation of Aggregate Functions in the DLV System does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Design and Implementation of Aggregate Functions in the DLV System, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Design and Implementation of Aggregate Functions in the DLV System will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-580053