Conflict-driven ASP solving with external sources

DOI10.1017/S1471068412000233MaRDI QIDQ4911141zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Thomas Eiter, Michael Fink, Thomas Krennwallner, Christoph Redl

Publication date 13 March 2013

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

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

zbMATH Keywords

answer set programmingconflict-driven clause learningnonmonotonic reasoning

Mathematics Subject Classification ID

Logic programming (68N17)

Abstract: Answer Set Programming (ASP) is a well-known problem solving approach based on nonmonotonic logic programs and efficient solvers. To enable access to external information, HEX-programs extend programs with external atoms, which allow for a bidirectional communication between the logic program and external sources of computation (e.g., description logic reasoners and Web resources). Current solvers evaluate HEX-programs by a translation to ASP itself, in which values of external atoms are guessed and verified after the ordinary answer set computation. This elegant approach does not scale with the number of external accesses in general, in particular in presence of nondeterminism (which is instrumental for ASP). In this paper, we present a novel, native algorithm for evaluating HEX-programs which uses learning techniques. In particular, we extend conflict-driven ASP solving techniques, which prevent the solver from running into the same conflict again, from ordinary to HEX-programs. We show how to gain additional knowledge from external source evaluations and how to use it in a conflict-driven algorithm. We first target the uninformed case, i.e., when we have no extra information on external sources, and then extend our approach to the case where additional meta-information is available. Experiments show that learning from external sources can significantly decrease both the runtime and the number of considered candidate compatible sets.

Recommendations

• Answer set programming with external sources
• Exploiting partial assignments for efficient evaluation of answer set programs with external source access
• Answer set programming with external source access
• A model building framework for answer set programming with external computations
• Inlining external sources in answer set programs

Cites work

• Answer set programming and plan generation
• Answer set programming based on propositional satisfiability
• ASSAT: computing answer sets of a logic program by SAT solvers
• BerkMin: A fast and robust SAT-solver
• Combining answer set programming with description logics for the semantic web
• Exploiting conjunctive queries in description logic programs
• Extending and implementing the stable model semantics
• Logic programs with stable model semantics as a constraint programming paradigm
• Semantics and complexity of recursive aggregates in answer set programming
• The DLV system for knowledge representation and reasoning

Cited in

(22)

• Pruning external minimality checking for answer set programs using semantic dependencies
• The Hexlite solver. Lightweight and efficient evaluation of HEX programs
• Explaining inconsistency in answer set programs and extensions
• FLP answer set semantics without circular justifications for general logic programs
• Domain expansion for ASP-programs with external sources
• On abstract modular inference systems and solvers
• HEX programs with action atoms
• Exploiting unfounded sets for HEX-program evaluation
• Clause-learning for modular systems
• Exploiting answer set programming with external sources for meta-interpretive learning
• Exploiting partial assignments for efficient evaluation of answer set programs with external source access
• Rewriting recursive aggregates in answer set programming: back to monotonicity
• A model building framework for answer set programming with external computations
• The<scp>dlvhex</scp>system for knowledge representation: recent advances (system description)
• \textit{clingcon}: the next generation
• On relation between constraint answer set programming and satisfiability modulo theories
• On the Implementation of Weight Constraint Rules in Conflict-Driven ASP Solvers
• Inlining external sources in answer set programs
• Answer set programming with external source access
• Multi-shot ASP solving with clingo
• Answer set programming with external sources
• Logic Programming and Nonmonotonic Reasoning

Describes a project that uses

Uses Software

• Potassco

This page was built for publication: Conflict-driven ASP solving with external sources

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