Rewriting recursive aggregates in answer set programming: Back to monotonicity

Mario Alviano, Wolfgang Faber, Martin Gebser

Research output: Contribution to journalArticle

20 Citations (Scopus)

Abstract

Aggregation functions are widely used in answer set programming for representing and reasoning on knowledge involving sets of objects collectively. Current implementations simplify the structure of programs in order to optimize the overall performance. In particular, aggregates are rewritten into simpler forms known as monotone aggregates. Since the evaluation of normal programs with monotone aggregates is in general on a lower complexity level than the evaluation of normal programs with arbitrary aggregates, any faithful translation function must introduce disjunction in rule heads in some cases. However, no function of this kind is known. The paper closes this gap by introducing a polynomial, faithful, and modular translation for rewriting common aggregation functions into the simpler form accepted by current solvers. A prototype system allows for experimenting with arbitrary recursive aggregates, which are also supported in the recent version 4.5 of the grounder gringo, using the methods presented in this paper.

LanguageEnglish
Pages559-573
Number of pages15
JournalTheory and Practice of Logic Programming
Volume15
Issue number4-5
DOIs
Publication statusPublished - 3 Sep 2015

Fingerprint

Answer Set Programming
Rewriting
Monotonicity
Aggregation Function
Faithful
Monotone
Agglomeration
Evaluation
Arbitrary
Low Complexity
Simplify
Reasoning
Optimise
Polynomials
Prototype
Polynomial

Cite this

Alviano, Mario ; Faber, Wolfgang ; Gebser, Martin. / Rewriting recursive aggregates in answer set programming : Back to monotonicity. In: Theory and Practice of Logic Programming. 2015 ; Vol. 15, No. 4-5. pp. 559-573.
@article{c3b43a984807494d94abecc0d52c00f4,
title = "Rewriting recursive aggregates in answer set programming: Back to monotonicity",
abstract = "Aggregation functions are widely used in answer set programming for representing and reasoning on knowledge involving sets of objects collectively. Current implementations simplify the structure of programs in order to optimize the overall performance. In particular, aggregates are rewritten into simpler forms known as monotone aggregates. Since the evaluation of normal programs with monotone aggregates is in general on a lower complexity level than the evaluation of normal programs with arbitrary aggregates, any faithful translation function must introduce disjunction in rule heads in some cases. However, no function of this kind is known. The paper closes this gap by introducing a polynomial, faithful, and modular translation for rewriting common aggregation functions into the simpler form accepted by current solvers. A prototype system allows for experimenting with arbitrary recursive aggregates, which are also supported in the recent version 4.5 of the grounder gringo, using the methods presented in this paper.",
keywords = "aggregation functions, and modular translation, answer set programming, faithful, polynomial",
author = "Mario Alviano and Wolfgang Faber and Martin Gebser",
year = "2015",
month = "9",
day = "3",
doi = "10.1017/S1471068415000228",
language = "English",
volume = "15",
pages = "559--573",
journal = "Theory and Practice of Logic Programming",
issn = "1471-0684",
publisher = "Cambridge University Press",
number = "4-5",

}

Rewriting recursive aggregates in answer set programming : Back to monotonicity. / Alviano, Mario; Faber, Wolfgang; Gebser, Martin.

In: Theory and Practice of Logic Programming, Vol. 15, No. 4-5, 03.09.2015, p. 559-573.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Rewriting recursive aggregates in answer set programming

T2 - Theory and Practice of Logic Programming

AU - Alviano, Mario

AU - Faber, Wolfgang

AU - Gebser, Martin

PY - 2015/9/3

Y1 - 2015/9/3

N2 - Aggregation functions are widely used in answer set programming for representing and reasoning on knowledge involving sets of objects collectively. Current implementations simplify the structure of programs in order to optimize the overall performance. In particular, aggregates are rewritten into simpler forms known as monotone aggregates. Since the evaluation of normal programs with monotone aggregates is in general on a lower complexity level than the evaluation of normal programs with arbitrary aggregates, any faithful translation function must introduce disjunction in rule heads in some cases. However, no function of this kind is known. The paper closes this gap by introducing a polynomial, faithful, and modular translation for rewriting common aggregation functions into the simpler form accepted by current solvers. A prototype system allows for experimenting with arbitrary recursive aggregates, which are also supported in the recent version 4.5 of the grounder gringo, using the methods presented in this paper.

AB - Aggregation functions are widely used in answer set programming for representing and reasoning on knowledge involving sets of objects collectively. Current implementations simplify the structure of programs in order to optimize the overall performance. In particular, aggregates are rewritten into simpler forms known as monotone aggregates. Since the evaluation of normal programs with monotone aggregates is in general on a lower complexity level than the evaluation of normal programs with arbitrary aggregates, any faithful translation function must introduce disjunction in rule heads in some cases. However, no function of this kind is known. The paper closes this gap by introducing a polynomial, faithful, and modular translation for rewriting common aggregation functions into the simpler form accepted by current solvers. A prototype system allows for experimenting with arbitrary recursive aggregates, which are also supported in the recent version 4.5 of the grounder gringo, using the methods presented in this paper.

KW - aggregation functions

KW - and modular translation

KW - answer set programming

KW - faithful

KW - polynomial

UR - http://www.scopus.com/inward/record.url?scp=84948396425&partnerID=8YFLogxK

U2 - 10.1017/S1471068415000228

DO - 10.1017/S1471068415000228

M3 - Article

VL - 15

SP - 559

EP - 573

JO - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

SN - 1471-0684

IS - 4-5

ER -