Logic programs with propositional connectives and aggregates

Answer set programming (ASP) is a logic programming paradigm that can be used to solve complex combinatorial search problems. Aggregates are an ASP construct that plays an important role in many applications. Defining a satisfactory semantics of aggregates turned out to be a difficult problem, and in this article we propose a new approach, based on an analogy between aggregates and propositional connectives. First we extend the definition of an answer set/stable model to cover arbitrary propositional theories; then we define aggregates on top of them both as primitive constructs and as abbreviations for formulas. Our definition of an aggregate combines expressiveness and simplicity, and it inherits many theorems about programs with nested expressions, such as theorems about strong equivalence and splitting.

• Publication year

  2008

• Venue

  TOCL

• Publication date

  2008-12-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1970398.1970401arXiv 0812.1462
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Combining decidability paradigms for existential rules

  2013cited by this paper
• Annals of Pure and Applied Logic

  2012cited by this paper
• On Reductive Semantics of Aggregates in Answer Set Programming

  2009cited by this paper
• Propositional theories are strongly equivalent to logic programs

  2007cited by this paper
• A New Perspective on Stable Models

  2007cited by this paper
• Expressiveness of answer set languages

  2007cited by this paper
• A Logic Program Characterization of Causal Theories

  2007cited by this paper
• Under consideration for publication in Theory and Practice of Logic Programming 1 Well-founded and Stable Semantics of Logic Programs with Aggregates

  2006cited by this paper
• Answer Sets for Logic Programs with Arbitrary Abstract Constraint Atoms

  2006cited by this paper
• Introduction

  2006cited by this paper
• A generalization of the Lin-Zhao theorem

  2006cited by this paper
• Mathematical Foundations of Answer Set Programming

  2005cited by this paper
• Answer Sets for Propositional Theories

  2005influential reference
• Safe beliefs for propositional theories

  2005influential reference
• Declarative and Computational Properties of Logic Programs with Aggregates

  2005cited by this paper
• Recursive Aggregates in Disjunctive Logic Programs: Semantics and Complexity

  2004influential reference
• Definitions in Answer Set Programming: (Extended Abstract)

  2003cited by this paper
• Reconstructing the Evolutionary History of Indo-European Languages Using Answer Set Programming

  2003cited by this paper
• Translation of Aggregate Programs to Normal Logic Programs

  2003cited by this paper
• Strong equivalence made easy: nested expressions and weight constraints

  2003cited by this paper
• Under consideration for publication in Theory and Practice of Logic Programming 1 Weight Constraints as Nested Expressions

  2003influential reference
• Ultimate Approximations in Nonmonotonic Knowledge Representation Systems

  2002influential reference
• Annals of Mathematics and Artificial Intelligence

  2002influential reference
• Declarative Specification and Solution of Combinatorial Auctions Using Logic Programming

  2001cited by this paper
• Strongly equivalent logic programs

  2001influential reference
• Answer Set Programming and Bounded Model Checking

  2001cited by this paper
• Specification of Workflow Process Using the Action Description Language C

  2001cited by this paper
• Extending the Smodels system with cardinality and weight constraints

  2001cited by this paper
• Reasoning about Policies using Logic Programs

  2001cited by this paper
• Encodings for Equilibrium Logic and Logic Programs with Nested Expressions

  2001cited by this paper
• Ultimate Well-Founded and Stable Semantics for Logic Programs with Aggregates

  2001cited by this paper
• Formalizing (and Reasoning About) the Specifications of Workflows

  2000cited by this paper
• Wire Routing and Satisfiability Planning

  2000cited by this paper
• DES: a Challenge Problem for Nonmonotonic Reasoning Systems

  2000cited by this paper
• Developing a Declarative Rule Language for Applications in Product Configuration

  1999cited by this paper
• Logic programs with stable model semantics as a constraint programming paradigm

  1999cited by this paper
• From Here to There: Stable Negation in Logic Programming

  1999cited by this paper
• Answer Set Planning (Abstract)

  1999cited by this paper
• Nested expressions in logic programs

  1999influential reference
• Answer Set Planning

  1999cited by this paper
• Fully Local and Efficient Evaluation of Alternating Fixed Points (Extended Abstract)

  1998cited by this paper
• Stable models and an alternative logic programming paradigm

  1998cited by this paper
• Causal Theories of Action and Change

  1997cited by this paper
• Encoding Planning Problems in Nonmonotonic Logic Programs

  1997cited by this paper
• Foundations of Logic Programming

  1997influential reference
• Non-Monotonic Extensions of Logic Programming

  1996cited by this paper
• A New Logical Characterisation of Stable Models and Answer Sets

  1996influential reference
• Splitting a Logic Program

  1994cited by this paper
• Complexity Results for Disjunctive Logic Programming and Application to Nonmonotonic Logics

  1993influential reference
• Classical negation in logic programs and disjunctive databases

  1991influential reference
• Autoepistemic logic

  1991cited by this paper
• Foundations of Logic Programming

  1984cited by this paper
• Under consideration for publication in Theory and Practice of Logic Programming 1 Characterizations of Stable Model Semantics for Logic Programs with Arbitrary Constraint Atoms

  year unknowninfluential reference

• Bounded satisfiability checking of FOL∗\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {FOL}^*$$\end{document} f

  2025cites this paper
• LPMLN, Weak Constraints, and P-log

  2025cites this paper
• Witnesses for Answer Sets of Basic Logic Programs

  2025cites this paper
• Bypassing the ASP Bottleneck: Hybrid Grounding by Splitting and Rewriting

  2024cites this paper
• Recursive Aggregates as Intensional Functions in Answer Set Programming: Semantics and Strong Equivalence

  2024cites this paper
• Plingo: A System for Probabilistic Reasoning in Answer Set Programming

  2024cites this paper
• Operator-based semantics for choice programs: is choosing losing? (full version)

  2024cites this paper
• AMO-aware Aggregates in Answer Set Programming

  2024cites this paper
• Design and implementation of modern CDCL ASP solvers

  2024cites this paper
• Recursive Aggregates as Intensional Functions

  2023cites this paper
• plingo: A system for probabilistic reasoning in clingo based on lpmln

  2022cites this paper
• Axiomatization of Aggregates in Answer Set Programming

  2022cites this paper
• The Possibilistic Horn Non-Clausal Knowledge Bases

  2021cites this paper
• Aggregate Semantics for Propositional Answer Set Programs

  2021influential citation
• Analyzing Semantics of Aggregate Answer Set Programming Using Approximation Fixpoint Theory

  2021cites this paper
• Quantitative and Stream Extensions of Answer Set Programming

  2021cites this paper
• On the Foundations of Grounding in Answer Set Programming

  2021influential citation
• Operating Room (Re)Scheduling with Bed Management via ASP

  2021cites this paper
• An ASP semantics for Constraints involving Conditional Aggregates

  2020influential citation
• Complexity results for probabilistic answer set programming

  2020cites this paper
• ASP ($\mathcal A \mathcal C$): Answer Set Programming with Algebraic Constraints

  2020cites this paper
• Unsatisfiable Core Analysis and Aggregates for Optimum Stable Model Search

  2020cites this paper
• An Introduction to Answer Set Programming and Some of Its Extensions

  2020cites this paper
• Reasoning Web. Declarative Artificial Intelligence: 16th International Summer School 2020, Oslo, Norway, June 24–26, 2020, Tutorial Lectures

  2020cites this paper
• Modular Answer Set Programming as a Formal Specification Language

  2020cites this paper
• Recursive Rules with Aggregation: A Simple Unified Semantics

  2020cites this paper
• A Uniform Treatment of Aggregates and Constraints in Hybrid ASP

  2020influential citation
• Computing secure sets in graphs using answer set programming

  2020cites this paper
• Lower Bound Founded Logic of Here-and-There

  2019cites this paper
• Exploiting Partial Knowledge in Declarative Domain-Specific Heuristics for ASP

  2019cites this paper
• Enhancing Lazy Grounding with Lazy Normalization in Answer-Set Programming

  2019cites this paper
• Chain Answer Sets for Logic Programs with Generalized Atoms

  2019cites this paper
• Vicious circle principle, aggregates, and formation of sets in ASP based languages

  2019influential citation
• Enhancing Magic Sets with an Application to Ontological Reasoning

  2019cites this paper
• Inconsistency Proofs for ASP: The ASP - DRUPE Format

  2019cites this paper
• Automated Reasoning with Restricted Intensional Sets

  2019cites this paper
• Algorithms for solving optimization problems in answer set programming

  2018cites this paper
• Aggregates in Answer Set Programming

  2018influential citation
• Translating LPOD and CR-Prolog2 into standard answer set programs

  2018cites this paper
• Towards Lazy Grounding with Lazy Normalization in Answer-Set Programming - Extended Abstract

  2018cites this paper
• Lower Bound Founded Logic of Here-and-There : A Preliminary Report

  2018cites this paper
• Shared aggregate sets in answer set programming

  2018cites this paper
• Functional ASP with Intensional Sets: Application to Gelfond-Zhang Aggregates

  2018influential citation
• Answer Set Programming from a Logical Point of View

  2018cites this paper
• Stepwise debugging of answer-set programs*

  2017cites this paper
• On the Relationships Among Probabilistic Extensions of Answer Set Semantics

  2017influential citation
• LPMLN, Weak Constraints, and P-log

  2017cites this paper
• MLN , Weak Constraints , and P-log

  2017influential citation
• Gelfond-Zhang Aggregates as Propositional Formulas

  2017influential citation
• Logic Programming and Nonmonotonic Reasoning

  2017influential citation
• Boolean Functions with Ordered Domains in Answer Set Programming

  2016influential citation
• Modeling and Language Extensions

  2016cites this paper
• Weak Constraints , and Plog

  2016cites this paper
• Reasoning About Policies in Security-Aware Service Discovery Using Answer Set Programming

  2016influential citation
• A Characterization of the Semantics of Logic Programs with Aggregates

  2016cites this paper
• Evaluating Answer Set Programming with Non-Convex Recursive Aggregates

  2016influential citation
• Anytime answer set optimization via unsatisfiable core shrinking

  2016cites this paper
• On the Properties of GZ-Aggregates in Answer Set Programming

  2016cites this paper
• From Non-Convex Aggregates to Monotone Aggregates in ASP

  2016influential citation
• Grounding Recursive Aggregates: Preliminary Report

  2016cites this paper
• Supportedly Stable Answer Sets for Logic Programs with Generalized Atoms

  2015cites this paper
• Belief Change in Nonmonotonic Multi-Context Systems

  2013cites this paper
• Decidability and Implementation of Parametrized Logic Programs

  2013cites this paper
• FIRST-ORDER ANSWER SET PROGRAMMING AND CLASSICAL FIRST-ORDER LOGIC

  2013cites this paper
• Forgetting in Logic Programs under Strong Equivalence

  2012cites this paper
• An FLP-Style Answer-Set Semantics for Abstract-Constraint Programs with Disjunctions

  2012cites this paper
• Ordered completion for logic programs with aggregates

  2012cites this paper
• The loop formula based semantics of description logic programs

  2012cites this paper
• A Well-Founded Semantics for Basic Logic Programs with Arbitrary Abstract Constraint Atoms

  2012cites this paper
• Unfounded Sets and Well-Founded Semantics of Answer Set Programs with Aggregates

  2011influential citation
• Interpolable Formulas in Equilibrium Logic and Answer Set Programming

  2011influential citation
• International Journal of Approximate Reasoning

  year unknowncites this paper
• Under Consideration for Publication in Theory and Practice of Logic Programming Rewriting Recursive Aggregates in Answer Set Programming: Back to Monotonicity

  year unknowncites this paper
• Under Consideration for Publication in Theory and Practice of Logic Programming Complexity and Compilation of Gz-aggregates in Answer Set Programming

  year unknowncites this paper
• Formal Verification of Answer Set Programs Containing Advanced Language Constructs

  year unknowncites this paper
• Proceedings of the 22nd Rcra International Work- Shop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion Program Chairs Program Committee Contents Regular Papers Evaluating Answer Set Programming with Non-convex Recursive Aggregates Jwasp: a New Java-based Asp

  year unknowncites this paper