Look-back Techniques for ASP Programs with Aggregates

Wolfgang Faber, Nicola Leone, Marco Maratea, Francesco Ricca

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

The introduction of aggregates has been one of the most relevant language extensions to Answer Set Programming (ASP). Aggregates are very expressive, they allow to represent many problems in a more succinct and elegant way compared to aggregate-free programs. A significant amount of research work has been devoted to aggregates in the ASP community in the last years, and relevant research results on ASP with aggregates have been published, on both theoretical and practical sides. The high expressiveness of aggregates (eliminating aggregates often causes a quadratic blow-up in program size) requires suitable evaluation methods and optimization techniques for an efficient implementation. Nevertheless, in spite of the above-mentioned research developments, aggregates are treated in a quite straightforward way in most ASP systems. In this paper, we explore the exploitation of look-back techniques for an efficient implementation of aggregates. We define a reason calculus for backjumping in ASP programs with aggregates. Furthermore, we describe how these reasons can be used in order to guide look-back heuristics for programs with aggregates. We have implemented both the new reason calculus and the proposed heuristics in the DLV system, and have carried out an experimental analysis on publicly available benchmarks which shows significant performance benefits.
Original languageEnglish
Pages (from-to)379-413
Number of pages35
JournalFundamenta Informaticae
Volume107
Issue number4
DOIs
Publication statusPublished - 2011
Externally publishedYes

Fingerprint

Dive into the research topics of 'Look-back Techniques for ASP Programs with Aggregates'. Together they form a unique fingerprint.

Cite this