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_2 (= 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 DLPA), and illustrate how it can be profitably used for representing knowledge. Furthermore, we analyze the computational complexity of DLPA, showing that the addition of aggregates does not bring a higher cost in that respect. Finally, we provide an implementation of DLPA 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.

Design and Implementation of Aggregate Functions in the DLV System

FABER, WOLFGANG;LEONE, Nicola;GIUSEPPE IELPA
2008

Abstract

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_2 (= 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 DLPA), and illustrate how it can be profitably used for representing knowledge. Furthermore, we analyze the computational complexity of DLPA, showing that the addition of aggregates does not bring a higher cost in that respect. Finally, we provide an implementation of DLPA 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.
disjunctive logic programming; answer set programming; aggregates; knowledge representation; implementation
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/152252
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 76
  • ???jsp.display-item.citation.isi??? 56
social impact