Omission-based abstraction for answer set programs

DOI10.1017/S1471068420000095MaRDI QIDQ4957218zbMATH OpenOpenAlexFDO

Authors Zeynep G. Saribatur, Thomas Eiter

Publication date 3 September 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

abstractionanswer set programminginconsistency explanationknowledge representationnonmonotonic reasoning

Mathematics Subject Classification ID

Logic programming (68N17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Knowledge representation (68T30)

Abstract: Abstraction is a well-known approach to simplify a complex problem by over-approximating it with a deliberate loss of information. It was not considered so far in Answer Set Programming (ASP), a convenient tool for problem solving. We introduce a method to automatically abstract ASP programs that preserves their structure by reducing the vocabulary while ensuring an over-approximation (i.e., each original answer set maps to some abstract answer set). This allows for generating partial answer set candidates that can help with approximation of reasoning. Computing the abstract answer sets is intuitively easier due to a smaller search space, at the cost of encountering spurious answer sets. Faithful (non-spurious) abstractions may be used to represent projected answer sets and to guide solvers in answer set construction. For dealing with spurious answer sets, we employ an ASP debugging approach to help with abstraction refinement, which determines atoms as badly omitted and adds them back in the abstraction. As a show case, we apply abstraction to explain unsatisfiability of ASP programs in terms of blocker sets, which are the sets of atoms such that abstraction to them preserves unsatisfiability. Their usefulness is demonstrated by experimental results.

Recommendations

• Abstraction for non-ground answer set programs
• scientific article; zbMATH DE number 4164177
• Abstract Solvers for Computing Cautious Consequences of ASP programs
• scientific article; zbMATH DE number 7047282
• Abstract Answer Set Solvers

Cites work

• A bird's-eye view of forgetting in answer-set programming
• A knowledge level account of forgetting
• A theory of abstraction
• A theory of diagnosis from first principles
• Abstract interpretation and application to logic programs
• Abstraction for non-ground answer set programs
• Algorithms for computing minimal unsatisfiable subsets of constraints
• Answer set programming based on propositional satisfiability
• Answer sets for consistent query answering in inconsistent databases
• Anytime answer set optimization via unsatisfiable core shrinking
• ASP-Core-2 input language format
• ASSAT: computing answer sets of a logic program by SAT solvers
• Automatically generating abstractions for planning
• Catching the Ouroboros: on debugging non-ground answer-set programs
• Cautious reasoning in ASP via minimal models and unsatisfiable cores
• Characterizations of the disjunctive stable semantics by partial evaluation
• Collective dynamics of `small-world' networks
• Counterexample-guided abstraction refinement for symbolic model checking
• Debugging ASP Programs by Means of ASP
• Design and results of the second international competition on computational models of argumentation
• Disjunctive stable models: Unfounded sets, fixpoint semantics, and computation
• Engineering an Incremental ASP Solver
• scientific article; zbMATH DE number 5914356 (Why is no real title available?)
• scientific article; zbMATH DE number 440477 (Why is no real title available?)
• scientific article; zbMATH DE number 25190 (Why is no real title available?)
• scientific article; zbMATH DE number 2090116 (Why is no real title available?)
• Interactive debugging of non-ground ASP programs
• Justifications for logic programs under answer set semantics
• Logic Programming
• Logic Programming
• Logic Programming and Nonmonotonic Reasoning
• Logics in Artificial Intelligence
• Merge-and-Shrink Abstraction
• Nested expressions in logic programs
• On the query complexity of selecting minimal sets for monotone predicates
• Planning in a hierarchy of abstraction spaces
• Semantic forgetting in answer set programming
• Strong equivalence made easy: nested expressions and weight constraints
• Strongly equivalent logic programs
• The design of the Seventh Answer Set Programming Competition
• The Design of the Sixth Answer Set Programming Competition
• The well-founded semantics for general logic programs
• Unfolding partiality and disjunctions in stable model semantics
• Unsatisfiability-based optimization in clasp
• When you must forget: Beyond strong persistence when forgetting in answer set programming

Cited in

(3)

• Abstraction for non-ground answer set programs
• Abstraction for non-ground answer set programs
• Forgetting in answer set programming -- a survey

Describes a project that uses

Uses Software

• ASSAT
• Potassco

This page was built for publication: Omission-based abstraction for answer set programs

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