Look-back Techniques for ASP Programs with Aggregates

Wolfgang Faber, Nicola Leone, Marco Maratea, Francesco Ricca

Research output: Contribution to journalArticle

3 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

Answer Set Programming
Efficient Implementation
Calculus
Heuristics
Computer systems programming
Expressiveness
Experimental Analysis
Evaluation Method
Research and Development
Exploitation
Blow-up
Optimization Techniques
Benchmark

Cite this

Faber, W., Leone, N., Maratea, M., & Ricca, F. (2011). Look-back Techniques for ASP Programs with Aggregates. Fundamenta Informaticae, 107(4), 379-413. https://doi.org/10.3233/FI-2011-408
Faber, Wolfgang ; Leone, Nicola ; Maratea, Marco ; Ricca, Francesco. / Look-back Techniques for ASP Programs with Aggregates. In: Fundamenta Informaticae. 2011 ; Vol. 107, No. 4. pp. 379-413.
@article{21c4edf2abf448a2acb06c9fbf700072,
title = "Look-back Techniques for ASP Programs with Aggregates",
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.",
keywords = "Knowledge representation and reasoning, Nonomonotonic reasoning, Answer set programming, Heuristics, Aggregates",
author = "Wolfgang Faber and Nicola Leone and Marco Maratea and Francesco Ricca",
year = "2011",
doi = "10.3233/FI-2011-408",
language = "English",
volume = "107",
pages = "379--413",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "4",

}

Faber, W, Leone, N, Maratea, M & Ricca, F 2011, 'Look-back Techniques for ASP Programs with Aggregates', Fundamenta Informaticae, vol. 107, no. 4, pp. 379-413. https://doi.org/10.3233/FI-2011-408

Look-back Techniques for ASP Programs with Aggregates. / Faber, Wolfgang; Leone, Nicola; Maratea, Marco; Ricca, Francesco.

In: Fundamenta Informaticae, Vol. 107, No. 4, 2011, p. 379-413.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Look-back Techniques for ASP Programs with Aggregates

AU - Faber, Wolfgang

AU - Leone, Nicola

AU - Maratea, Marco

AU - Ricca, Francesco

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Knowledge representation and reasoning

KW - Nonomonotonic reasoning

KW - Answer set programming

KW - Heuristics

KW - Aggregates

UR - https://content.iospress.com/journals/fundamenta-informaticae/156/2

U2 - 10.3233/FI-2011-408

DO - 10.3233/FI-2011-408

M3 - Article

VL - 107

SP - 379

EP - 413

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 4

ER -