Gelfond-Zhang aggregates as propositional formulas
- Answer Set Programming (ASP) has become a popular and widespread paradigm for practical Knowledge Representation thanks to its expressiveness and the available enhancements of its input language. One of such enhancements is the use of aggregates, for which different semantic proposals have been made. In this paper, we show that any ASP aggregate interpreted under Gelfond and Zhang's (GZ) semantics can be replaced (under strong equivalence) by a propositional formula. Restricted to the original GZ syntax, the resulting formula is reducible to a disjunction of conjunctions of literals but the formulation is still applicable even when the syntax is extended to allow for arbitrary formulas (including nested aggregates) in the condition. Once GZ-aggregates are represented as formulas, we establish a formal comparison (in terms of the logic of Here-and-There) to Ferraris' (F) aggregates, which are defined by a different formula translation involving nested implications. In particular, we prove that if we replace an F-aggregate by aAnswer Set Programming (ASP) has become a popular and widespread paradigm for practical Knowledge Representation thanks to its expressiveness and the available enhancements of its input language. One of such enhancements is the use of aggregates, for which different semantic proposals have been made. In this paper, we show that any ASP aggregate interpreted under Gelfond and Zhang's (GZ) semantics can be replaced (under strong equivalence) by a propositional formula. Restricted to the original GZ syntax, the resulting formula is reducible to a disjunction of conjunctions of literals but the formulation is still applicable even when the syntax is extended to allow for arbitrary formulas (including nested aggregates) in the condition. Once GZ-aggregates are represented as formulas, we establish a formal comparison (in terms of the logic of Here-and-There) to Ferraris' (F) aggregates, which are defined by a different formula translation involving nested implications. In particular, we prove that if we replace an F-aggregate by a GZ-aggregate in a rule head, we do not lose answer sets (although more can be gained). This extends the previously known result that the opposite happens in rule bodies, i.e., replacing a GZ-aggregate by an F-aggregate in the body may yield more answer sets. Finally, we characterize a class of aggregates for which GZ- and F-semantics coincide.…
Verfasserangaben: | Pedro CabalarORCiDGND, Jorge FandinnoORCiD, Torsten H. SchaubORCiDGND, Sebastian SchellhornORCiD |
---|---|
DOI: | https://doi.org/10.1016/j.artint.2018.10.007 |
ISSN: | 0004-3702 |
ISSN: | 1872-7921 |
Titel des übergeordneten Werks (Englisch): | Artificial intelligence |
Verlag: | Elsevier |
Verlagsort: | Amsterdam |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Jahr der Erstveröffentlichung: | 2019 |
Erscheinungsjahr: | 2019 |
Datum der Freischaltung: | 19.11.2020 |
Freies Schlagwort / Tag: | Aggregates; Answer Set Programming |
Band: | 274 |
Seitenanzahl: | 18 |
Erste Seite: | 26 |
Letzte Seite: | 43 |
Fördernde Institution: | Xunta de Galicia, SpainXunta de Galicia [GPC-ED431B 2016/035, 2016-2019 ED431G/01]; MINECO, Spain [TIN 2013-42149-P, TIN 2017-84453-P]; Centre International de Mathernatiques et Informatique de Toulouse [ANR-11-LABEX-0040-CIMI, ANR-11-IDEX-0002-02]; DFGGerman Research Foundation (DFG) [SCHA 550/9] |
Organisationseinheiten: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
Peer Review: | Referiert |
Publikationsweg: | Open Access |
Open Access / Green Open-Access |