Cautious reasoning in ASP via minimal models and unsatisfiable cores

DOI10.1017/S1471068418000145MaRDI QIDQ4559795zbMATH OpenOpenAlexDBLPWikidataFDO

Authors M. Alviano, Carmine Dodaro, Matti Järvisalo, Marco Maratea, Alessandro Previti

Publication date 4 December 2018

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.08480

zbMATH Keywords

answer set programmingquery answeringcautious reasoning

Mathematics Subject Classification ID

Knowledge representation (68T30) Logic programming (68N17)

Abstract: Answer Set Programming (ASP) is a logic-based knowledge representation framework, supporting---among other reasoning modes---the central task of query answering. In the propositional case, query answering amounts to computing cautious consequences of the input program among the atoms in a given set of candidates, where a cautious consequence is an atom belonging to all stable models. Currently, the most efficient algorithms either iteratively verify the existence of a stable model of the input program extended with the complement of one candidate, where the candidate is heuristically selected, or introduce a clause enforcing the falsity of at least one candidate, so that the solver is free to choose which candidate to falsify at any time during the computation of a stable model. This paper introduces new algorithms for the computation of cautious consequences, with the aim of driving the solver to search for stable models discarding more candidates. Specifically, one of such algorithms enforces minimality on the set of true candidates, where different notions of minimality can be used, and another takes advantage of unsatisfiable cores computation. The algorithms are implemented in WASP, and experiments on benchmarks from the latest ASP competitions show that the new algorithms perform better than the state of the art. (Under consideration for acceptance in TPLP).

Recommendations

• Anytime computation of cautious consequences in answer set programming
• Abstract Solvers for Computing Cautious Consequences of ASP programs
• Advances in WASP
• scientific article; zbMATH DE number 7047282
• Optimum stable model search: algorithms and implementation

Cites work

• scientific article; zbMATH DE number 1614696 (Why is no real title available?)
• scientific article; zbMATH DE number 25190 (Why is no real title available?)
• scientific article; zbMATH DE number 1368933 (Why is no real title available?)
• A tableau calculus for minimal model reasoning
• Advances in WASP
• Algorithms for computing backbones of propositional formulae
• Answer sets for consistent query answering in inconsistent databases
• Anytime answer set optimization via unsatisfiable core shrinking
• Anytime computation of cautious consequences in answer set programming
• Combining answer set programming and domain heuristics for solving hard industrial problems (application paper)
• Combining answer set programming with description logics for the semantic web
• Conflict-driven answer set solving: from theory to practice
• Consistent query answering via ASP from different perspectives: theory and practice
• Design and results of the Fifth Answer Set Programming Competition
• Disjunctive ASP with functions: decidable queries and effective computation
• Dynamic magic sets and super-coherent answer set programs
• GRASP: a search algorithm for propositional satisfiability
• Knowledge Representation, Reasoning and Declarative Problem Solving
• Logic Programming and Nonmonotonic Reasoning
• Logic programs with stable model semantics as a constraint programming paradigm
• Magic sets for disjunctive Datalog programs
• Model enumeration in propositional circumscription via unsatisfiable core analysis
• On the query complexity of selecting minimal sets for monotone predicates
• On the relation among answer set solvers
• Positive unit hyperresolution tableaux and their application to minimal model generation
• Solving satisfiability problems with preferences
• Taming primary key violations to query large inconsistent data via ASP
• The ASP system DLV2
• The DLV system for knowledge representation and reasoning
• The Sixth Answer Set Programming Competition

Cited in

(10)

• Pruning external minimality checking for ASP using semantic dependencies
• Anytime computation of cautious consequences in answer set programming
• Abstraction for non-ground answer set programs
• ASP and subset minimality: enumeration, cautious reasoning and MUSes
• Advances in WASP
• Abstract Solvers for Computing Cautious Consequences of ASP programs
• ASP for minimal entailment in a rational extension of SROEL
• Omission-based abstraction for answer set programs
• Unsatisfiable core analysis and aggregates for optimum stable model search
• Enhancing magic sets with an application to ontological reasoning

Describes a project that uses

Uses Software

• DLV2
• maxino
• pyglaf
• Datalog
• WASP
• DLV
• Gringo

This page was built for publication: Cautious reasoning in ASP via minimal models and unsatisfiable cores

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4559795)