# Optimizing Answer Set Computation via Heuristic-Based Decomposition

arXiv: https://arxiv.org/abs/1812.09718 · HTML: https://mlsanity.com/paper/1812.09718/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2018.

## Built on by (most cited first, 5 of 5)

- [ASP-based Multi-shot Reasoning via DLV2 with Incremental Grounding](https://mlsanity.com/paper/2412.17143/) (2024)
- [System Predictor: Grounding Size Estimator for Logic Programs under Answer Set Semantics](https://mlsanity.com/paper/2303.17018/) (2023)
- [Enhancing Datalog Reasoning with Hypertree Decompositions](https://mlsanity.com/paper/2305.06854/) (2023)
- [Data Augmentation: a Combined Inductive-Deductive Approach featuring Answer Set Programming](https://mlsanity.com/paper/2310.14413/) (2023)
- [Automated Hybrid Grounding Using Structural and Data-Driven Heuristics](https://mlsanity.com/paper/2507.17493/) (2025)

## Abstract (arXiv)

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).