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 Dive into the research topics of 'Supportedly stable answer sets for logic programs with generalized atoms'. Together they form a unique fingerprint.

  • 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