Answer Set Programming Modulo Acyclicity

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Standard

Answer Set Programming Modulo Acyclicity. / Bomanson, Jori; Gebser, Martin; Janhunen, Tomi; Kaufmann, Benjamin; Schaub, Torsten.

julkaisussa: Fundamenta Informaticae, Vuosikerta 147, Nro 1, 2016, s. 63-91.

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Harvard

Bomanson, J, Gebser, M, Janhunen, T, Kaufmann, B & Schaub, T 2016, 'Answer Set Programming Modulo Acyclicity' Fundamenta Informaticae, Vuosikerta. 147, Nro 1, Sivut 63-91. https://doi.org/10.3233/FI-2016-1398

APA

Vancouver

Author

Bomanson, Jori ; Gebser, Martin ; Janhunen, Tomi ; Kaufmann, Benjamin ; Schaub, Torsten. / Answer Set Programming Modulo Acyclicity. Julkaisussa: Fundamenta Informaticae. 2016 ; Vuosikerta 147, Nro 1. Sivut 63-91.

Bibtex - Lataa

@article{13b31dcd8be247d39d5bf5760d801a58,
title = "Answer Set Programming Modulo Acyclicity",
abstract = "Acyclicity constraints are prevalent in knowledge representation and applications where acyclic data structures such as DAGs and trees play a role. Recently, such constraints have been considered in the satisfiability modulo theories (SMT) framework, and in this paper we carry out an analogous extension to the answer set programming (ASP) paradigm. The resulting formalism, ASP modulo acyclicity, offers a rich set of primitives to express constraints related to recursive structures. In the technical results of the paper, we relate the new generalization with standard ASP by showing (i) how acyclicity extensions translate into normal rules, (ii) how weight constraint programs can be instrumented by acyclicity extensions to capture stability in analogy to unfounded set checking, and (iii) how the gap between supported and stable models is effectively closed in the presence of such an extension. Moreover, we present an efficient implementation of acyclicity constraints by incorporating a respective propagator into the state-of-the-art ASP solver CLASP. The implementation provides a unique combination of traditional unfounded set checking with acyclicity propagation. In the experimental part, we evaluate the interplay of these orthogonal checks by equipping logic programs with supplementary acyclicity constraints. The performance results show that native support for acyclicity constraints is a worthwhile addition, furnishing a complementary modeling construct in ASP itself as well as effective means for translation-based ASP solving.",
author = "Jori Bomanson and Martin Gebser and Tomi Janhunen and Benjamin Kaufmann and Torsten Schaub",
year = "2016",
doi = "10.3233/FI-2016-1398",
language = "English",
volume = "147",
pages = "63--91",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
number = "1",

}

RIS - Lataa

TY - JOUR

T1 - Answer Set Programming Modulo Acyclicity

AU - Bomanson, Jori

AU - Gebser, Martin

AU - Janhunen, Tomi

AU - Kaufmann, Benjamin

AU - Schaub, Torsten

PY - 2016

Y1 - 2016

N2 - Acyclicity constraints are prevalent in knowledge representation and applications where acyclic data structures such as DAGs and trees play a role. Recently, such constraints have been considered in the satisfiability modulo theories (SMT) framework, and in this paper we carry out an analogous extension to the answer set programming (ASP) paradigm. The resulting formalism, ASP modulo acyclicity, offers a rich set of primitives to express constraints related to recursive structures. In the technical results of the paper, we relate the new generalization with standard ASP by showing (i) how acyclicity extensions translate into normal rules, (ii) how weight constraint programs can be instrumented by acyclicity extensions to capture stability in analogy to unfounded set checking, and (iii) how the gap between supported and stable models is effectively closed in the presence of such an extension. Moreover, we present an efficient implementation of acyclicity constraints by incorporating a respective propagator into the state-of-the-art ASP solver CLASP. The implementation provides a unique combination of traditional unfounded set checking with acyclicity propagation. In the experimental part, we evaluate the interplay of these orthogonal checks by equipping logic programs with supplementary acyclicity constraints. The performance results show that native support for acyclicity constraints is a worthwhile addition, furnishing a complementary modeling construct in ASP itself as well as effective means for translation-based ASP solving.

AB - Acyclicity constraints are prevalent in knowledge representation and applications where acyclic data structures such as DAGs and trees play a role. Recently, such constraints have been considered in the satisfiability modulo theories (SMT) framework, and in this paper we carry out an analogous extension to the answer set programming (ASP) paradigm. The resulting formalism, ASP modulo acyclicity, offers a rich set of primitives to express constraints related to recursive structures. In the technical results of the paper, we relate the new generalization with standard ASP by showing (i) how acyclicity extensions translate into normal rules, (ii) how weight constraint programs can be instrumented by acyclicity extensions to capture stability in analogy to unfounded set checking, and (iii) how the gap between supported and stable models is effectively closed in the presence of such an extension. Moreover, we present an efficient implementation of acyclicity constraints by incorporating a respective propagator into the state-of-the-art ASP solver CLASP. The implementation provides a unique combination of traditional unfounded set checking with acyclicity propagation. In the experimental part, we evaluate the interplay of these orthogonal checks by equipping logic programs with supplementary acyclicity constraints. The performance results show that native support for acyclicity constraints is a worthwhile addition, furnishing a complementary modeling construct in ASP itself as well as effective means for translation-based ASP solving.

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

U2 - 10.3233/FI-2016-1398

DO - 10.3233/FI-2016-1398

M3 - Article

VL - 147

SP - 63

EP - 91

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1

ER -

ID: 9779477