Properties and Applications of Programs with Monotone and Convex Constraints

We study properties of programs with monotone and convex constraints. We extend to these formalisms concepts and results from normal logic programming. They include the notions of strong and uniform equivalence with their characterizations, tight programs and Fages Lemma, program completion and loop formulas. Our results provide an abstract account of properties of some recent extensions of logic programming with aggregates, especially the formalism of lparse programs. They imply a method to compute stable models of lparse programs by means of off-the-shelf solvers of pseudo-boolean constraints, which is often much faster than the smodels system.

• Publication year

  2006

• Venue

  Journal of Artificial Intelligence Research

• Publication date

  2006-09-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1613/jair.2009arXiv 1110.0023
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Next Steps in Propositional Horn Contraction

  2009cited 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

  2006influential reference
• Answer Sets for Logic Programs with Arbitrary Abstract Constraint Atoms

  2006cited by this paper
• Pbmodels - Software to Compute Stable Models by Pseudoboolean Solvers

  2005cited by this paper
• Answer Sets for Propositional Theories

  2005influential reference
• Properties of Programs with Monotone and Convex Constraints

  2005cited by this paper
• Stochastic Local Search: Foundations & Applications

  2004cited by this paper
• Under consideration for publication in Theory and Practice of Logic Programming 1 Constructive Circumscription

  2004influential reference
• Semantics of logic programs with aggregates

  2004influential reference
• Partial Stable Models for Logic Programs with Aggregates

  2004cited by this paper
• Logic Programs with Abstract Constraint Atoms

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

  2004influential reference
• Strong equivalence made easy: nested expressions and weight constraints

  2003influential reference
• Under consideration for publication in Theory and Practice of Logic Programming 1 Weight Constraints as Nested Expressions

  2003cited by this paper
• Knowledge Representation, Reasoning and Declarative Problem Solving

  2003cited by this paper
• Local-Search Techniques for Propositional Logic Extended with Cardinality Constraints

  2003influential reference
• Uniform Equivalence of Logic Programs under the Stable Model Semantics

  2003influential reference
• An Extensible SAT-solver

  2003cited by this paper
• Logic programming and knowledge representation—The A-Prolog perspective

  2002cited by this paper
• ASSAT: computing answer sets of a logic program by SAT solvers

  2002cited by this paper
• Reducing Strong Equivalence of Logic Programs to Entailment in Classical Propositional Logic

  2002influential reference
• Strongly equivalent logic programs

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

  2001cited by this paper
• Extending and implementing the stable model semantics

  2000influential reference
• Approximations, Stable Operators, Well-founded Fixpoints and Applications in Nonmonotonic Reasoning

  2000cited by this paper
• PBS: A Backtrack-Search Pseudo-Boolean Solver and Optimizer

  2000cited by this paper
• Logic-Based Artificial Intelligence

  2000cited by this paper
• APPROXIMATIONS, STABLE OPERATORS, WELL-FOUNDED FIXPOINTS AND APPLICATIONS IN NONMONOTONIC REASONING

  2000cited by this paper
• Stable Model Semantics of Weight Constraint Rules

  1999cited by this paper
• Solving Linear Pseudo-Boolean Constraint Problems with Local Search

  1997influential reference
• Consistency of Clark's Completion and Existence of Stable Models 2 Introduction and Notations

  1994influential reference
• Noise Strategies for Improving Local Search

  1994cited by this paper
• Logic Programming and Knowledge Representation

  1994cited by this paper
• Consistency of Clark's completion and existence of stable models

  1992cited by this paper
• Semantics of Logic Programs with Aggregates

  1991cited by this paper
• On the Semantics of Logic Programs

  1991cited by this paper
• The Magic of Duplicates and Aggregates

  1990cited by this paper
• The Stable Model Semantics for Logic Programming

  1988cited by this paper
• Logic Programming '85

  1985cited by this paper
• Logic and Data Bases

  1978cited by this paper

• A simple proof-theoretic characterization of stable models: Reduction to difference logic and experiments

  2024cites this paper
• A Simple Proof-Theoretic Characterization of Stable Models

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

  2021cites this paper
• Applying Visible Strong Equivalence in Answer-Set Program Transformations

  2020influential citation
• LP2PB: Translating Answer Set Programs into Pseudo-Boolean Theories

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

  2019cites this paper
• Aggregates in Answer Set Programming

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

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

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

  2016cites this paper
• Boolean Functions with Ordered Domains in Answer Set Programming

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

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

  2015cites this paper
• Semantics and Compilation of Answer Set Programming with Generalized Atoms

  2014cites this paper
• Embedding Functions into Disjunctive Logic Programs

  2013cites this paper
• Answer Set Programming and Other Computing Paradigms

  2013cites this paper
• Properties of Answer Set Programming with Convex Generalized Atoms

  2013influential citation
• Tableau Calculi for Logic Programs under Answer Set Semantics

  2013cites this paper
• Computing Loops with at Most One External Support Rule for Basic Logic Programs with Arbitrary Constraint Atoms

  2013cites this paper
• Answer Set Solving in Practice

  2012cites this paper
• Answer Set Programming via Mixed Integer Programming

  2012cites this paper
• Disjunctive Programs with Set Constraints

  2012cites this paper
• Applying Visible Strong Equivalence in Answer-Set Program Transformations

  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

  2012influential citation
• Strong Equivalence of Logic Programs with Abstract Constraint Atoms

  2011influential citation
• First-Order Stable Model Semantics and First-Order Loop Formulas

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

  2011cites this paper
• Weight constraint programs with evaluable functions

  2010influential citation
• Sampler Programs: The Stable Model Semantics of Abstract Constraint Programs Revisited

  2010cites this paper
• Logic programming with constraints

  2010cites this paper
• Well-Founded Semantics for Logic Programs with Aggregates: Implementation and Experimentation

  2010cites this paper
• Equivalence between Extended Datalog Programs - A Brief Survey

  2010cites this paper
• Level Mapping Induced Loop Formulas for Weight Constraint and Aggregate Logic Programs

  2010influential citation
• Under Consideration for Publication in Theory and Practice of Logic Programming on Elementary Loops of Logic Programs

  2010cites this paper
• Level Mapping Induced Loop Formulas for Weight Constraint and Aggregate Programs

  2009influential citation
• On Reductive Semantics of Aggregates in Answer Set Programming

  2009cites this paper
• Weight Constraint Programs with Functions

  2009influential citation
• A Default Approach to Semantics of Logic Programs with Constraint Atoms

  2009influential citation
• Loop Formulas for Logic Programs with Arbitrary Constraint Atoms

  2008cites this paper
• Lparse Programs Revisited: Semantics and Representation of Aggregates

  2008cites this paper
• Logic Programming for Knowledge Representation

  2007cites this paper
• Logic Programs with Abstract Constraints: Representaton, Disjunction and Complexities

  2007cites this paper
• Logic Programming for Knowledge Representation

  2007cites 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
• Under Consideration for Publication in Theory and Practice of Logic Programming Relating Weight Constraint and Aggregate Programs: Semantics and Representation

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