The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Semantics and complexity of recursive aggregates in answer set programming
Open accessAbstract
The addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). They strengthen the modelling power of ASP in terms of natural and concise problem representations. Previous semantic definitions typically agree in the case of non-recursive aggregates, but the picture is less clear for aggregates involved in recursion. Some proposals explicitly avoid recursive aggregates, most others differ, and many of them do not satisfy desirable criteria, such as minimality or coincidence with answer sets in the aggregate-free case. In this paper we define a semantics for programs with arbitrary aggregates (including monotone, antimonotone, and nonmonotone aggregates) in the full ASP language allowing also for disjunction in the head (disjunctive logic programming - DLP). This semantics is a genuine generalization of the answer set semantics for DLP, it is defined by a natural variant of the Gelfond-Lifschitz transformation, and treats aggregate and non-aggregate literals in a uniform way. This novel transformation is interesting per se also in the aggregate-free case, since it is simpler than the original transformation and does not need to differentiate between positive and negative literals. We prove that our semantics guarantees the minimality (and therefore the incomparability) of answer sets, and we demonstrate that it coincides with the standard answer set semantics on aggregate-free programs. Moreover, we carry out an in-depth study of the computational complexity of the language. The analysis pays particular attention to the impact of syntactical restrictions on programs in the form of limited use of aggregates, disjunction, and negation. While the addition of aggregates does not affect the complexity of the full DLP language, it turns out that their presence does increase the complexity of normal (i.e., non-disjunctive) ASP programs up to the second level of the polynomial hierarchy. However, we show that there are large classes of aggregates the addition of which does not cause any complexity gap even for normal programs, including the fragment allowing for arbitrary monotone, arbitrary antimonotone, and stratified (i.e., non-recursive) nonmonotone aggregates. The analysis provides some useful indications on the possibility to implement aggregates in existing reasoning engines.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Circumscription—A form of non-monotonic reasoning
McCarthy, J. (1980) · Artificial Intelligence · doi:10.1016/0004-3702(80)90011-9 · Cited by 2,017
Towards a Theory of Declarative Knowledge
Apt, K. R., Blair, H. A., & Walker, A. (1988) · Foundations of Deductive Databases and Logic Programming · doi:10.1016/b978-0-934613-40-8.50006-3 · Cited by 1,151
Cited by
Conflict-driven answer set solving: From theory to practice
Gebser, M., Kaufmann, B., & Schaub, T. (2012) · Artificial Intelligence · doi:10.1016/j.artint.2012.04.001 · Cited by 327
Exploiting Answer Set Programming with External Sources for Meta-Interpretive Learning
KAMINSKI, T., EITER, T., & INOUE, K. (2018) · Theory and Practice of Logic Programming · doi:10.1017/s1471068418000261 · Cited by 29
Schüller, P., & Benz, M. (2018) · Machine Learning · doi:10.1007/s10994-018-5708-2 · Cited by 21
Metadata
- Authors
- Faber, W., Pfeifer, G., & Leone, N.
- Venue
- Artificial Intelligence
- Publisher
- Elsevier BV
- Published
- 2011-01
- Volume
- 175
- Issue
- 1
- Pages
- 278-298
- ISSN
- 0004-3702 (ISSN-L)
- OpenAlex
- W2064864283
- Cited by
- 240
- References
- 2
- FWCI
- 19.04
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Semantics and complexity of recursive aggregates in answer set programming. https://app.cochat.ai/papers/10.1016/j.artint.2010.04.002
- The paper
- Faber, W., Pfeifer, G., & Leone, N. (2011). Semantics and complexity of recursive aggregates in answer set programming. Artificial Intelligence. https://doi.org/10.1016/j.artint.2010.04.002
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.