The power of non-ground rules in Answer Set Programming

DOI10.1017/S1471068416000338MaRDI QIDQ4593042zbMATH OpenFDO

Authors Manuel Bichler, Michael Morak, Stefan Woltran

Publication date 9 November 2017

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

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

zbMATH Keywords

answer set programmingnon-ground rulesrewritingrule decomposition

Mathematics Subject Classification ID

Logic programming (68N17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: Answer set programming (ASP) is a well-established logic programming language that offers an intuitive, declarative syntax for problem solving. In its traditional application, a fixed ASP program for a given problem is designed and the actual instance of the problem is fed into the program as a set of facts. This approach typically results in programs with comparably short and simple rules. However, as is known from complexity analysis, such an approach limits the expressive power of ASP; in fact, an entire NP-check can be encoded into a single large rule body of bounded arity that performs both a guess and a check within the same rule. Here, we propose a novel paradigm for encoding hard problems in ASP by making explicit use of large rules which depend on the actual instance of the problem. We illustrate how this new encoding paradigm can be used, providing examples of problems from the first, second, and even third level of the polynomial hierarchy. As state-of-the-art solvers are tuned towards short rules, rule decomposition is a key technique in the practical realization of our approach. We also provide some preliminary benchmarks which indicate that giving up the convenient way of specifying a fixed program can lead to a significant speed-up. This paper is under consideration for acceptance into TPLP.

Recommendations

• Preprocessing of complex non-ground rules in answer set programming
• On structural analysis of non-ground answer-set programs
• Abstraction for non-ground answer set programs
• Abstraction for non-ground answer set programs
• Complexity of Rule Redundancy in Non-ground Answer-Set Programming over Finite Domains
• Program Correspondence under the Answer-Set Semantics: The Non-ground Case
• Constraint answer set programming without grounding
• Evaluating Answer Set Programming with Non-Convex Recursive Aggregates

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Abduction from logic programs: Semantics and complexity
• Complex optimization in answer set programming
• Complexity of Finding Embeddings in a k-Tree
• Complexity results for answer set programming with bounded predicate arities and implications
• Conflict-driven answer set solving: from theory to practice
• Enhancing search-based QBF solving by dynamic blocked clause elimination
• GASP: Answer set programming with lazy grounding
• Generalized hypertree decompositions: NP-hardness and tractable variants
• scientific article; zbMATH DE number 1368933 (Why is no real title available?)
• Lazy model expansion by incremental grounding
• On the complexity of single-rule datalog queries.
• On the computational cost of disjunctive logic programming: Propositional case
• Preprocessing of complex non-ground rules in answer set programming
• Towards automated integration of guess and check programs in answer set programming: a meta-interpreter and applications
• Unfolding partiality and disjunctions in stable model semantics

Cited in

(19)

• Complexity results for answer set programming with bounded predicate arities and implications
• Towards automated integration of guess and check programs in answer set programming: a meta-interpreter and applications
• Evaluating Answer Set Programming with Non-Convex Recursive Aggregates
• Combining answer set programming and domain heuristics for solving hard industrial problems (application paper)
• Optimizing answer set computation via heuristic-based decomposition
• Solving Advanced Argumentation Problems with Answer Set Programming
• selp: a single-shot epistemic logic program solver
• scientific article; zbMATH DE number 7455725 (Why is no real title available?)
• Beyond NP: quantifying over answer sets
• An Answer Set Solver for non-Herbrand Programs: Progress Report
• Preprocessing of complex non-ground rules in answer set programming
• Logic Programming and Nonmonotonic Reasoning
• Complexity of Rule Redundancy in Non-ground Answer-Set Programming over Finite Domains
• Declarative Problem Solving Using Answer Set Semantics
• Program Correspondence under the Answer-Set Semantics: The Non-ground Case
• Domain-Specific Heuristics in Answer Set Programming: A Declarative Non-Monotonic Approach
• Abstraction for non-ground answer set programs
• Abstraction for non-ground answer set programs
• Reasoning on with Defeasibility in ASP

Describes a project that uses

Uses Software

• GASP

This page was built for publication: The power of non-ground rules in Answer Set Programming

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