Cautious reasoning in ASP via minimal models and unsatisfiable cores
From MaRDI portal
Publication:4559795
DOI10.1017/S1471068418000145zbMATH Open1451.68267DBLPjournals/tplp/AlvianoDJM18arXiv1804.08480OpenAlexW2963164881WikidataQ62043797 ScholiaQ62043797MaRDI QIDQ4559795FDOQ4559795
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)
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).
Full work available at URL: https://arxiv.org/abs/1804.08480
Recommendations
Cites Work
- Advances in WASP
- The ASP system DLV2
- Combining answer set programming with description logics for the semantic web
- On the query complexity of selecting minimal sets for monotone predicates
- Title not available (Why is that?)
- Algorithms for computing backbones of propositional formulae
- The DLV system for knowledge representation and reasoning
- Solving satisfiability problems with preferences
- Answer sets for consistent query answering in inconsistent databases
- On the relation among answer set solvers
- Conflict-driven answer set solving: from theory to practice
- Magic sets for disjunctive Datalog programs
- Logic programs with stable model semantics as a constraint programming paradigm
- GRASP: a search algorithm for propositional satisfiability
- Title not available (Why is that?)
- Logic Programming and Nonmonotonic Reasoning
- Positive unit hyperresolution tableaux and their application to minimal model generation
- A tableau calculus for minimal model reasoning
- The Sixth Answer Set Programming Competition
- Design and results of the Fifth Answer Set Programming Competition
- Knowledge Representation, Reasoning and Declarative Problem Solving
- Dynamic magic sets and super-coherent answer set programs
- Taming primary key violations to query large inconsistent data via ASP
- Combining answer set programming and domain heuristics for solving hard industrial problems (application paper)
- Title not available (Why is that?)
- Anytime computation of cautious consequences in answer set programming
- Model enumeration in propositional circumscription via unsatisfiable core analysis
- Anytime answer set optimization via unsatisfiable core shrinking
- Consistent query answering via ASP from different perspectives: theory and practice
- Disjunctive ASP with functions: decidable queries and effective computation
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
Uses Software
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)
