Rewriting recursive aggregates in answer set programming: back to monotonicity
From MaRDI portal
Publication:4592997
DOI10.1017/S1471068415000228zbMATH Open1379.68034arXiv1507.03923OpenAlexW3104110719MaRDI QIDQ4592997FDOQ4592997
Martin Gebser, Wolfgang Faber, M. Alviano
Publication date: 9 November 2017
Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)
Abstract: Aggregation functions are widely used in answer set programming for representing and reasoning on knowledge involving sets of objects collectively. Current implementations simplify the structure of programs in order to optimize the overall performance. In particular, aggregates are rewritten into simpler forms known as monotone aggregates. Since the evaluation of normal programs with monotone aggregates is in general on a lower complexity level than the evaluation of normal programs with arbitrary aggregates, any faithful translation function must introduce disjunction in rule heads in some cases. However, no function of this kind is known. The paper closes this gap by introducing a polynomial, faithful, and modular translation for rewriting common aggregation functions into the simpler form accepted by current solvers. A prototype system allows for experimenting with arbitrary recursive aggregates, which are also supported in the recent version 4.5 of the grounder extsc{gringo}, using the methods presented in this paper. To appear in Theory and Practice of Logic Programming (TPLP), Proceedings of ICLP 2015.
Full work available at URL: https://arxiv.org/abs/1507.03923
Recommendations
- Evaluating Answer Set Programming with Non-Convex Recursive Aggregates
- Semantics and complexity of recursive aggregates in answer set programming
- Logics in Artificial Intelligence
- On the Complexity of Answer Set Programming with Aggregates
- On Reductive Semantics of Aggregates in Answer Set Programming
Cites Work
- Extending and implementing the stable model semantics
- On the computational cost of disjunctive logic programming: Propositional case
- Combining answer set programming with description logics for the semantic web
- Title not available (Why is that?)
- Weight constraints as nested expressions
- Strong equivalence made easy: nested expressions and weight constraints
- Conflict-driven ASP solving with external sources
- Efficient HEX-Program Evaluation Based on Unfounded Sets
- Semantics and complexity of recursive aggregates in answer set programming
- Strongly equivalent logic programs
- Conflict-driven answer set solving: from theory to practice
- FLP answer set semantics without circular justifications for general logic programs
- Well-founded and stable semantics of logic programs with aggregates
- Answer set programming based on propositional satisfiability
- A Constructive semantic characterization of aggregates in answer set programming
- Design and implementation of aggregate functions in the DLV system
- Correct reasoning. Essays on logic-based AI in honour of Vladimir Lifschitz
- On the complexity of pattern matching for highly compressed two-dimensional texts.
- Title not available (Why is that?)
- Logic programs with propositional connectives and aggregates
- The Complexity Boundary of Answer Set Programming with Generalized Atoms under the FLP Semantics
- Vicious Circle Principle and Logic Programs with Aggregates
- Normalizing Cardinality Rules Using Merging and Sorting Constructions
- Some (in)translatability results for normal logic programs and propositional theories
- Logic programs with abstract constraint atoms: the role of computations
- Anytime Computation of Cautious Consequences in Answer Set Programming
- Improving the Normalization of Weight Rules in Answer Set Programs
- Relating weight constraint and aggregate programs: semantics and representation
- Title not available (Why is that?)
Cited In (13)
- Inlining External Sources in Answer Set Programs
- Model enumeration in propositional circumscription via unsatisfiable core analysis
- ASP-Core-2 Input Language Format
- On Reductive Semantics of Aggregates in Answer Set Programming
- Unsatisfiable Core Analysis and Aggregates for Optimum Stable Model Search
- Anytime answer set optimization via unsatisfiable core shrinking
- Solution Enumeration by Optimality in Answer Set Programming
- Enhancing Magic Sets with an Application to Ontological Reasoning
- Recursive rules with aggregation: a simple unified semantics
- Vicious circle principle, aggregates, and formation of sets in ASP based languages
- Multi-shot ASP solving with clingo
- Shared aggregate sets in answer set programming
- Evaluating Answer Set Programming with Non-Convex Recursive Aggregates
Uses Software
This page was built for publication: Rewriting recursive aggregates in answer set programming: back to monotonicity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592997)
