Optimizing Answer Set Computation via Heuristic-Based Decomposition. Issue 4 (28th February 2019)

• Record Type: Journal Article
• Authors: CALIMERI, FRANCESCO; PERRI, SIMONA; ZANGARI, JESSICA
• Is Part Of: Theory and practice of logic programming. Volume 19:Issue 4(2019)
• Page Start: 603
• Page End: 628
• Publication Date: 2019-02-28
• Subjects: knowledge representation and nonmonotonic reasoning, -- logic programming methodology and applications, -- databases and semantic web reasoning, -- Answer Set Programming; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068419000036
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: Answer Set Programming (ASP) is a purely declarative formalism developed in the field of logic programming and non-monotonic 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 ℐ-DLV, and carry out an extensive experimental activity for assessing the impact of the proposal.