Complexity and compilation of GZ-aggregates in answer set programming
From MaRDI portal
Publication:4592998
DOI10.1017/S147106841500023XzbMATH Open1379.68035arXiv1507.03922OpenAlexW3101449588MaRDI QIDQ4592998FDOQ4592998
Authors: M. Alviano, N. Leone 
Publication date: 9 November 2017
Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)
Abstract: Gelfond and Zhang recently proposed a new stable model semantics based on Vicious Circle Principle in order to improve the interpretation of logic programs with aggregates. The paper focuses on this proposal, and analyzes the complexity of both coherence testing and cautious reasoning under the new semantics. Some surprising results highlight similarities and differences versus mainstream stable model semantics for aggregates. Moreover, the paper reports on the design of compilation techniques for implementing the new semantics on top of existing ASP solvers, which eventually lead to realize a prototype system that allows for experimenting with Gelfond-Zhang's aggregates. To appear in Theory and Practice of Logic Programming (TPLP), Proceedings of ICLP 2015.
Full work available at URL: https://arxiv.org/abs/1507.03922
Recommendations
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?)
- Efficient HEX-Program Evaluation Based on Unfounded Sets
- Semantics and complexity of recursive aggregates in answer set programming
- Logic Programming and Nonmonotonic Reasoning
- 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
- A Constructive semantic characterization of aggregates in answer set programming
- Design and implementation of aggregate functions in the DLV system
- Properties and applications of programs with monotone and convex constraints
- 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
Cited In (10)
- Semantics and complexity of recursive aggregates in answer set programming
- Model enumeration in propositional circumscription via unsatisfiable core analysis
- On Reductive Semantics of Aggregates in Answer Set Programming
- Anytime answer set optimization via unsatisfiable core shrinking
- On the Complexity of Answer Set Programming with Aggregates
- 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: Complexity and compilation of GZ-aggregates in answer set programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592998)
