TY  - JOUR
A1  - Fichte, Johannes Klaus
A1  - Szeider, Stefan
T1  - Backdoors to tractable answer set programming
JF  - Artificial intelligence
N2  - Answer Set Programming (ASP) is an increasingly popular framework for declarative programming that admits the description of problems by means of rules and constraints that form a disjunctive logic program. In particular, many Al problems such as reasoning in a nonmonotonic setting can be directly formulated in ASP. Although the main problems of ASP are of high computational complexity, complete for the second level of the Polynomial Hierarchy, several restrictions of ASP have been identified in the literature, under which ASP problems become tractable.
 In this paper we use the concept of backdoors to identify new restrictions that make ASP problems tractable. Small backdoors are sets of atoms that represent "clever reasoning shortcuts" through the search space and represent a hidden structure in the problem input. The concept of backdoors is widely used in theoretical investigations in the areas of propositional satisfiability and constraint satisfaction. We show that it can be fruitfully adapted to ASP. We demonstrate how backdoors can serve as a unifying framework that accommodates several tractable restrictions of ASP known from the literature. Furthermore, we show how backdoors allow us to deploy recent algorithmic results from parameterized complexity theory to the domain of answer set programming. (C) 2015 Elsevier B.V. All rights reserved.
KW  - Answer set programming
KW  - Backdoors
KW  - Computational complexity
KW  - Parameterized complexity
KW  - Kernelization
Y1  - 2015
U6  - https://doi.org/10.1016/j.artint.2014.12.001
SN  - 0004-3702
SN  - 1872-7921
VL  - 220
SP  - 64
EP  - 103
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Hecher, Markus
T1  - Treewidth-aware reductions of normal ASP to SAT
BT  - is normal ASP harder than SAT after all?
JF  - Artificial intelligence
N2  - Answer Set Programming (ASP) is a paradigm for modeling and solving problems for knowledge representation and reasoning. There are plenty of results dedicated to studying the hardness of (fragments of) ASP. So far, these studies resulted in characterizations in terms of computational complexity as well as in fine-grained insights presented in form of dichotomy-style results, lower bounds when translating to other formalisms like propositional satisfiability (SAT), and even detailed parameterized complexity landscapes. A generic parameter in parameterized complexity originating from graph theory is the socalled treewidth, which in a sense captures structural density of a program. Recently, there was an increase in the number of treewidth-based solvers related to SAT. While there are translations from (normal) ASP to SAT, no reduction that preserves treewidth or at least keeps track of the treewidth increase is known. In this paper we propose a novel reduction from normal ASP to SAT that is aware of the treewidth, and guarantees that a slight increase of treewidth is indeed sufficient. Further, we show a new result establishing that, when considering treewidth, already the fragment of normal ASP is slightly harder than SAT (under reasonable assumptions in computational complexity). This also confirms that our reduction probably cannot be significantly improved and that the slight increase of treewidth is unavoidable. Finally, we present an empirical study of our novel reduction from normal ASP to SAT, where we compare treewidth upper bounds that are obtained via known decomposition heuristics. Overall, our reduction works better with these heuristics than existing translations. (c) 2021 Elsevier B.V. All rights reserved.
KW  - Answer set programming
KW  - Treewidth
KW  - Parameterized complexity
KW  - Complexity
KW  - analysis
KW  - Tree decomposition
KW  - Treewidth-aware reductions
Y1  - 2022
U6  - https://doi.org/10.1016/j.artint.2021.103651
SN  - 0004-3702
SN  - 1872-7921
VL  - 304
PB  - Elsevier
CY  - Amsterdam
ER  -