Partial Compilation of ASP Programs

DOI10.1017/S1471068419000231zbMATH Open1434.68072arXiv1907.10469OpenAlexW2963672115WikidataQ127174332 ScholiaQ127174332MaRDI QIDQ5108506

F. Ricca, Carmine Dodaro, Bernardo Cuteri, Peter Schüller

Publication date: 4 May 2020

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

Abstract: Answer Set Programming (ASP) is a well-known declarative formalism in logic programming. Efficient implementations made it possible to apply ASP in many scenarios, ranging from deductive databases applications to the solution of hard combinatorial problems. State-of-the-art ASP systems are based on the traditional ground&solve approach and are general-purpose implementations, i.e., they are essentially built once for any kind of input program. In this paper, we propose an extended architecture for ASP systems, in which parts of the input program are compiled into an ad-hoc evaluation algorithm (i.e., we obtain a specific binary for a given program), and might not be subject to the grounding step. To this end, we identify a condition that allows the compilation of a sub-program, and present the related partial compilation technique. Importantly, we have implemented the new approach on top of a well-known ASP solver and conducted an experimental analysis on publicly-available benchmarks. Results show that our compilation-based approach improves on the state of the art in various scenarios, including cases in which the input program is stratified or the grounding blow-up makes the evaluation unpractical with traditional ASP systems.

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

zbMATH Keywords

answer set programmingcompilationgrounding bottleneck

Mathematics Subject Classification ID

Logic programming (68N17) Theory of compilers and interpreters (68N20)

Cites Work

• GASP: Answer Set Programming with Lazy Grounding
• System aspmt2smt: Computing ASPMT Theories by SMT Solvers
• Advances in WASP
• Constraint answer set solver EZCSP and why integration schemas matter
• Extending and implementing the stable model semantics
• Modularity Aspects of Disjunctive Stable Models
• The DLV system for knowledge representation and reasoning
• Optimization Methods for the Partner Units Problem
• ASP modulo CSP: The clingcon system
• The Intelligent Grounder of DLV
• Answer Set Programming: A Primer
• Efficiently Querying RDF(S) Ontologies with Answer Set Programming
• A model building framework for answer set programming with external computations
• Progress in clasp Series 3
• Taming primary key violations to query large inconsistent data via ASP
• Generating explanations for biomedical queries
• Blending lazy-grounding and CDNL search for answer-set solving
• Efficiently Coupling the I-DLV Grounder with ASP Solvers
• Combining Answer Set Programming and domain heuristics for solving hard industrial problems (Application Paper)
• The External Interface for Extending WASP
• A logic-based question answering system for cultural heritage
• Optimizing phylogenetic supertrees using answer set programming
• Combining Heuristics for Configuration Problems Using Answer Set Programming
• ASPeRiX, a first-order forward chaining approach for answer set computing
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• Look-back techniques for ASP programs with aggregates
• Advancing Lazy-Grounding ASP Solving Techniques – Restarts, Phase Saving, Heuristics, and More
• Title not available (Why is that?)
• DualGrounder: lazy instantiation via clingo multi-shot framework

Uses Software

• Gringo
• clasp
• GASP
• WASP
• Clingcon
• Clingo
• ASPMT2SMT
• Datalog
• ezcsp
• DLV2

This page was built for publication: Partial Compilation of ASP Programs

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