Supportedly stable answer sets for logic programs with generalized atoms

Mario Alviano, Wolfgang Faber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

Answer Set Programming (ASP) is logic programming under the stable model or answer set semantics. During the last decade, this paradigm has seen several extensions by generalizing the notion of atom used in these programs. Among these, there are dl-atoms, aggregate atoms, HEX atoms, generalized quantifiers, and abstract constraints. In this paper we refer to these constructs collectively as generalized atoms. The idea common to all of these constructs is that their satisfaction depends on the truth values of a set of (non-generalized) atoms, rather than the truth value of a single (non-generalized) atom. Motivated by several examples, we argue that for some of the more intricate generalized atoms, the previously suggested semantics provide unintuitive results and provide an alternative semantics, which we call supportedly stable or SFLP answer sets. We show that it is equivalent to the major previously proposed semantics for programs with convex generalized atoms, and that it in general admits more intended models than other semantics in the presence of non-convex generalized atoms. We show that the complexity of supportedly stable answer sets is on the second level of the polynomial hierarchy, similar to previous proposals and to answer sets of disjunctive logic programs.

Original languageEnglish
Title of host publicationWeb Reasoning and Rule Systems - 9th International Conference, RR 2015, Proceedings
PublisherSpringer Verlag
Pages30-44
Number of pages15
Volume9209
ISBN (Print)9783319220017
DOIs
Publication statusPublished - 2015
Event9th International Conference on Web Reasoning and Rule Systems - Berlin, Germany
Duration: 4 Aug 20155 Aug 2015
Conference number: 9

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9209
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference9th International Conference on Web Reasoning and Rule Systems
Abbreviated titleRR 2015
CountryGermany
CityBerlin
Period4/08/155/08/15

Fingerprint

Answer Sets
Stable Set
Logic Programs
Atoms
Semantics
Generalized Quantifiers
Polynomial Hierarchy
Answer Set Programming
Stable Models
Logic programming
Logic Programming
Computer programming
Paradigm
Polynomials

Cite this

Alviano, M., & Faber, W. (2015). Supportedly stable answer sets for logic programs with generalized atoms. In Web Reasoning and Rule Systems - 9th International Conference, RR 2015, Proceedings (Vol. 9209, pp. 30-44). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9209). Springer Verlag. https://doi.org/10.1007/978-3-319-22002-4_4
Alviano, Mario ; Faber, Wolfgang. / Supportedly stable answer sets for logic programs with generalized atoms. Web Reasoning and Rule Systems - 9th International Conference, RR 2015, Proceedings. Vol. 9209 Springer Verlag, 2015. pp. 30-44 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{7b9111388a304817ae7ead594519f813,
title = "Supportedly stable answer sets for logic programs with generalized atoms",
abstract = "Answer Set Programming (ASP) is logic programming under the stable model or answer set semantics. During the last decade, this paradigm has seen several extensions by generalizing the notion of atom used in these programs. Among these, there are dl-atoms, aggregate atoms, HEX atoms, generalized quantifiers, and abstract constraints. In this paper we refer to these constructs collectively as generalized atoms. The idea common to all of these constructs is that their satisfaction depends on the truth values of a set of (non-generalized) atoms, rather than the truth value of a single (non-generalized) atom. Motivated by several examples, we argue that for some of the more intricate generalized atoms, the previously suggested semantics provide unintuitive results and provide an alternative semantics, which we call supportedly stable or SFLP answer sets. We show that it is equivalent to the major previously proposed semantics for programs with convex generalized atoms, and that it in general admits more intended models than other semantics in the presence of non-convex generalized atoms. We show that the complexity of supportedly stable answer sets is on the second level of the polynomial hierarchy, similar to previous proposals and to answer sets of disjunctive logic programs.",
author = "Mario Alviano and Wolfgang Faber",
year = "2015",
doi = "10.1007/978-3-319-22002-4_4",
language = "English",
isbn = "9783319220017",
volume = "9209",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "30--44",
booktitle = "Web Reasoning and Rule Systems - 9th International Conference, RR 2015, Proceedings",

}

Alviano, M & Faber, W 2015, Supportedly stable answer sets for logic programs with generalized atoms. in Web Reasoning and Rule Systems - 9th International Conference, RR 2015, Proceedings. vol. 9209, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9209, Springer Verlag, pp. 30-44, 9th International Conference on Web Reasoning and Rule Systems, Berlin, Germany, 4/08/15. https://doi.org/10.1007/978-3-319-22002-4_4

Supportedly stable answer sets for logic programs with generalized atoms. / Alviano, Mario; Faber, Wolfgang.

Web Reasoning and Rule Systems - 9th International Conference, RR 2015, Proceedings. Vol. 9209 Springer Verlag, 2015. p. 30-44 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9209).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Supportedly stable answer sets for logic programs with generalized atoms

AU - Alviano, Mario

AU - Faber, Wolfgang

PY - 2015

Y1 - 2015

N2 - Answer Set Programming (ASP) is logic programming under the stable model or answer set semantics. During the last decade, this paradigm has seen several extensions by generalizing the notion of atom used in these programs. Among these, there are dl-atoms, aggregate atoms, HEX atoms, generalized quantifiers, and abstract constraints. In this paper we refer to these constructs collectively as generalized atoms. The idea common to all of these constructs is that their satisfaction depends on the truth values of a set of (non-generalized) atoms, rather than the truth value of a single (non-generalized) atom. Motivated by several examples, we argue that for some of the more intricate generalized atoms, the previously suggested semantics provide unintuitive results and provide an alternative semantics, which we call supportedly stable or SFLP answer sets. We show that it is equivalent to the major previously proposed semantics for programs with convex generalized atoms, and that it in general admits more intended models than other semantics in the presence of non-convex generalized atoms. We show that the complexity of supportedly stable answer sets is on the second level of the polynomial hierarchy, similar to previous proposals and to answer sets of disjunctive logic programs.

AB - Answer Set Programming (ASP) is logic programming under the stable model or answer set semantics. During the last decade, this paradigm has seen several extensions by generalizing the notion of atom used in these programs. Among these, there are dl-atoms, aggregate atoms, HEX atoms, generalized quantifiers, and abstract constraints. In this paper we refer to these constructs collectively as generalized atoms. The idea common to all of these constructs is that their satisfaction depends on the truth values of a set of (non-generalized) atoms, rather than the truth value of a single (non-generalized) atom. Motivated by several examples, we argue that for some of the more intricate generalized atoms, the previously suggested semantics provide unintuitive results and provide an alternative semantics, which we call supportedly stable or SFLP answer sets. We show that it is equivalent to the major previously proposed semantics for programs with convex generalized atoms, and that it in general admits more intended models than other semantics in the presence of non-convex generalized atoms. We show that the complexity of supportedly stable answer sets is on the second level of the polynomial hierarchy, similar to previous proposals and to answer sets of disjunctive logic programs.

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

U2 - 10.1007/978-3-319-22002-4_4

DO - 10.1007/978-3-319-22002-4_4

M3 - Conference contribution

SN - 9783319220017

VL - 9209

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 30

EP - 44

BT - Web Reasoning and Rule Systems - 9th International Conference, RR 2015, Proceedings

PB - Springer Verlag

ER -

Alviano M, Faber W. Supportedly stable answer sets for logic programs with generalized atoms. In Web Reasoning and Rule Systems - 9th International Conference, RR 2015, Proceedings. Vol. 9209. Springer Verlag. 2015. p. 30-44. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-22002-4_4