OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Gelfond-Zhang aggregates as propositional formulas

Cabalar, Pedro and Fandinno, Jorge and Schaub, Torsten and Schellhorn, Sebastian Gelfond-Zhang aggregates as propositional formulas. (2019) Artificial Intelligence, 274. 26-43. ISSN 0004-3702

[img]
Preview
(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
525kB

Official URL: https://doi.org/10.1016/j.artint.2018.10.007

Abstract

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 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.

Item Type:Article
HAL Id:hal-02452472
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Universität Potsdam (GERMANY)
Other partners > Universidade da Coruña - UDC (SPAIN)
Laboratory name:
Funders:
Xunta de Galicia (SPAIN) - Ministerio de Economía, Industria y Competitividad - MINECO (SPAIN) - Centre International de Mathématiques et Informatique de Toulouse - CIMIT (FRANCE) - Deutsche Forschungsgemeinschaft - DFG (GERMANY)
Statistics:download
Deposited On:23 Jan 2020 13:44

Repository Staff Only: item control page