Optimizing Answer Set Computation via Heuristic-Based Decomposition

DOI10.1017/S1471068419000036zbMATH Open1472.68024arXiv1812.09718MaRDI QIDQ4957190FDOQ4957190

Jessica Zangari, Francesco Calimeri, Simona Perri

Publication date: 3 September 2021

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

Abstract: Answer Set Programming (ASP) is a purely declarative formalism developed in the field of logic programming and nonmonotonic reasoning: computational problems are encoded by logic programs whose answer sets, corresponding to solutions, are computed by an ASP system. Different, semantically equivalent, programs can be defined for the same problem; however, performance of systems evaluating them might significantly vary. We propose an approach for automatically transforming an input logic program into an equivalent one that can be evaluated more efficiently. One can make use of existing tree-decomposition techniques for rewriting selected rules into a set of multiple ones; the idea is to guide and adaptively apply them on the basis of proper new heuristics, to obtain a smart rewriting algorithm to be integrated into an ASP system. The method is rather general: it can be adapted to any system and implement different preference policies. Furthermore, we define a set of new heuristics tailored at optimizing grounding, one of the main phases of the ASP computation; we use them in order to implement the approach into the ASP system DLV, in particular into its grounding subsystem I-DLV, and carry out an extensive experimental activity for assessing the impact of the proposal. Under consideration in Theory and Practice of Logic Programming (TPLP).

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

zbMATH Keywords

answer set programmingnonmonotonic reasoningdatabasesknowledge representationlogic programmingsemantic web reasoning

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• GASP: Answer Set Programming with Lazy Grounding
• Advances in WASP
• Multi-shot ASP solving with clingo
• The ASP system DLV2
• Lpopt: a rule optimization tool for answer set programming
• Extending and implementing the stable model semantics
• Propositional semantics for disjunctive logic programs
• The DLV system for knowledge representation and reasoning
• Graph minors. II. Algorithmic aspects of tree-width
• Reasoning with minimal models: efficient algorithms and applications
• Conflict-driven answer set solving: from theory to practice
• Magic sets for disjunctive Datalog programs
• Answer set programming based on propositional satisfiability
• Unfolding partiality and disjunctions in stable model semantics
• Graph-Theoretic Concepts in Computer Science
• Logic Programming and Nonmonotonic Reasoning
• The design of the Seventh Answer Set Programming Competition
• The Intelligent Grounder of DLV
• The Design of the Sixth Answer Set Programming Competition
• Design and results of the Fifth Answer Set Programming Competition
• The Impact of Treewidth on Grounding and Solving of Answer Set Programs
• Progress in clasp Series 3
• Enhancing DLV instantiator by backjumping techniques
• Blending lazy-grounding and CDNL search for answer-set solving
• Preprocessing of Complex Non-Ground Rules in Answer Set Programming
• The power of non-ground rules in Answer Set Programming
• Experimenting with parallelism for the instantiation of ASP programs
• Parallel instantiation of ASP programs: techniques and experiments
• ASPeRiX, a first-order forward chaining approach for answer set computing

Cited In (9)

• Boosting Answer Set Optimization with Weighted Comparator Networks
• Combining Heuristics for Configuration Problems Using Answer Set Programming
• Lpopt: a rule optimization tool for answer set programming
• Incremental Answer Set Programming with Overgrounding
• Title not available (Why is that?)
• Precomputing Datalog Evaluation Plans in Large-Scale Scenarios
• Incremental maintenance of overgrounded logic programs with tailored simplifications
• Estimating grounding sizes of logic programs under answer set semantics
• Domain-Specific Heuristics in Answer Set Programming: A Declarative Non-Monotonic Approach

Uses Software

• Gringo
• clasp
• GASP
• WASP
• Clingo
• Datalog
• htd
• Lpopt
• OMiGA
• DLV2

This page was built for publication: Optimizing Answer Set Computation via Heuristic-Based Decomposition

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