Stable-unstable semantics: Beyond NP with normal logic programs

DOI10.1017/S1471068416000387MaRDI QIDQ4593043zbMATH OpenFDO

Authors Bart Bogaerts, Tomi Janhunen, Shahab Tasharrofi

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

zbMATH Keywords

disjunctive logic programmingpolynomial hierarchyquantified Boolean formulas

Mathematics Subject Classification ID

Logic programming (68N17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: Standard answer set programming (ASP) targets at solving search problems from the first level of the polynomial time hierarchy (PH). Tackling search problems beyond NP using ASP is less straightforward. The class of disjunctive logic programs offers the most prominent way of reaching the second level of the PH, but encoding respective hard problems as disjunctive programs typically requires sophisticated techniques such as saturation or meta-interpretation. The application of such techniques easily leads to encodings that are inaccessible to non-experts. Furthermore, while disjunctive ASP solvers often rely on calls to a (co-)NP oracle, it may be difficult to detect from the input program where the oracle is being accessed. In other formalisms, such as Quantified Boolean Formulas (QBFs), the interface to the underlying oracle is more transparent as it is explicitly recorded in the quantifier prefix of a formula. On the other hand, ASP has advantages over QBFs from the modeling perspective. The rich high-level languages such as ASP-Core-2 offer a wide variety of primitives that enable concise and natural encodings of search problems. In this paper, we present a novel logic programming--based modeling paradigm that combines the best features of ASP and QBFs. We develop so-called combined logic programs in which oracles are directly cast as (normal) logic programs themselves. Recursive incarnations of this construction enable logic programming on arbitrarily high levels of the PH. We develop a proof-of-concept implementation for our new paradigm. This paper is under consideration for acceptance in TPLP.

Recommendations

• On stable-like semantics for logic programs
• On the Expressibility of Stable Logic Programming
• On the expressibility of stable logic programming
• A note on the stable model semantics for logic programs
• On the relations between stable and well-founded semantics of logic programs
• scientific article; zbMATH DE number 25192
• On the existence and unicity of stable models in normal residuated logic programs
• On the existence of stable models of non-stratified logic programs
• Expressiveness of logic programs under the general stable model semantics
• Paraconsistent Stable Semantics for Extended Disjunctive Programs

Cites work

• A Tarskian informal semantics for answer set programming
• Abstract gringo
• Complex optimization in answer set programming
• Design and results of the Fifth Answer Set Programming Competition
• scientific article; zbMATH DE number 6003856 (Why is no real title available?)
• scientific article; zbMATH DE number 25190 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1368933 (Why is no real title available?)
• Inferring phylogenetic trees using answer set programming
• Integrating ASP into ROS for reasoning in robots
• Logic programs with stable model semantics as a constraint programming paradigm
• Normalizing cardinality rules using merging and sorting constructions
• On a generalization of quantifiers
• On the computational cost of disjunctive logic programming: Propositional case
• Optimizing phylogenetic supertrees using answer set programming
• Predicate logic as a modeling language: modeling and solving some machine learning and data mining problems with IDP3
• Progress in clasp series 3
• Propositional semantics for disjunctive logic programs
• Simulating Dynamic Systems Using Linear Time Calculus Theories
• Solving parity games by a reduction to SAT
• The DLV system for knowledge representation and reasoning
• 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
• Well-Founded Semantics and the Algebraic Theory of Non-monotone Inductive Definitions

Cited in

(10)

• Two SAT solvers for solving quantified Boolean formulas with an arbitrary number of quantifier alternations
• Knowledge representation analysis of graph mining
• Solving problems in the polynomial hierarchy with ASP(Q)
• Writing declarative specifications for clauses
• The Seventh Answer Set Programming Competition: Design and Results
• Solving Advanced Argumentation Problems with Answer Set Programming
• Beyond NP: quantifying over answer sets
• Predicate-calculus-based logics for modeling and solving search problems
• Explainability via short formulas: the case of propositional logic with implementation
• An efficient solver for ASP(Q)

Describes a project that uses

Uses Software

• ROSoClingo
• Gringo
• DLV
• clasp
• IDP3

This page was built for publication: Stable-unstable semantics: Beyond NP with normal logic programs

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