Inlining external sources in answer set programs

DOI10.1017/S147106841800056XMaRDI QIDQ4957183zbMATH OpenOpenAlexFDO

Authors Christoph Redl

Publication date 3 September 2021

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

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

zbMATH Keywords

answer set programmingequivalenceexternal computationHEX-programsinlining

Mathematics Subject Classification ID

Logic programming (68N17)

Abstract: HEX-programs are an extension of answer set programs (ASP) with external sources. To this end, external atoms provide a bidirectional interface between the program and an external source. The traditional evaluation algorithm for HEX-programs is based on guessing truth values of external atoms and verifying them by explicit calls of the external source. The approach was optimized by techniques that reduce the number of necessary verification calls or speed them up, but the remaining external calls are still expensive. In this paper we present an alternative evaluation approach based on inlining of external atoms, motivated by existing but less general approaches for specialized formalisms such as DL-programs. External atoms are then compiled away such that no verification calls are necessary. The approach is implemented in the dlvhex reasoner. Experiments show a significant performance gain. Besides performance improvements, we further exploit inlining for extending previous (semantic) characterizations of program equivalence from ASP to HEX-programs, including those of strong equivalence, uniform equivalence and H, B -equivalence. Finally, based on these equivalence criteria, we characterize also inconsistency of programs wrt. extensions. Since well-known ASP extensions (such as constraint ASP) are special cases of HEX, the results are interesting beyond the particular formalism. Under consideration in Theory and Practice of Logic Programming (TPLP).

Recommendations

• Exploiting partial assignments for efficient evaluation of answer set programs with external source access
• Answer set programming with external sources
• Conflict-driven ASP solving with external sources
• Exploiting unfounded sets for HEX-program evaluation
• Efficient HEX-Program Evaluation Based on Unfounded Sets

Cites work

• A common view on strong, uniform, and other notions of equivalence in answer-set programming
• A general notion of equivalence for abstract argumentation
• A model building framework for answer set programming with external computations
• Answer Set Programming: A Primer
• Answer set solving with lazy nogood generation
• ASP modulo CSP: the clingcon system
• Combining answer set programming with description logics for the semantic web
• Computer Aided Verification
• Conflict-driven answer set solving: from theory to practice
• Conflict-driven ASP solving with external sources
• Constraint Answer Set Solving
• Domain expansion for ASP-programs with external sources
• Efficient HEX-Program Evaluation Based on Unfounded Sets
• Equivalence Between Answer-Set Programs Under (Partially) Fixed Input
• Evaluating Answer Set Programming with Non-Convex Recursive Aggregates
• Exploiting conjunctive queries in description logic programs
• scientific article; zbMATH DE number 25190 (Why is no real title available?)
• scientific article; zbMATH DE number 1946853 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• Logic Programming
• Logic Programming and Nonmonotonic Reasoning
• Logics in Artificial Intelligence
• Propagation via lazy clause generation
• Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs
• Rewriting recursive aggregates in answer set programming: back to monotonicity
• Semantics and complexity of recursive aggregates in answer set programming
• Strongly equivalent logic programs
• Towards practical deletion repair of inconsistent DL-programs
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family
• Tractable reasoning with DL-programs over Datalog-rewritable description logics

Cited in

(6)

• The Hexlite solver. Lightweight and efficient evaluation of HEX programs
• Explaining inconsistency in answer set programs and extensions
• HEX programs with action atoms
• Exploiting unfounded sets for HEX-program evaluation
• Exploiting partial assignments for efficient evaluation of answer set programs with external source access
• Conflict-driven ASP solving with external sources

Describes a project that uses

Uses Software

• Clingcon

This page was built for publication: Inlining external sources in answer set programs

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