The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 1 of 10
Back to Result List

Backdoors to tractable answer set programming

  • 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 backdoorsAnswer 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.show moreshow less

Export metadata

Additional Services

Search Google Scholar Statistics
Metadaten
Author details:Johannes Klaus FichteORCiD, Stefan Szeider
DOI:https://doi.org/10.1016/j.artint.2014.12.001
ISSN:0004-3702
ISSN:1872-7921
Title of parent work (English):Artificial intelligence
Publisher:Elsevier
Place of publishing:Amsterdam
Publication type:Article
Language:English
Year of first publication:2015
Publication year:2015
Release date:2017/03/27
Tag:Answer set programming; Backdoors; Computational complexity; Kernelization; Parameterized complexity
Volume:220
Number of pages:40
First page:64
Last Page:103
Funding institution:European Research Council [239962]; Austrian Science Fund (FWF) [Y698]
Organizational units:Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science
Peer review:Referiert
Institution name at the time of the publication:Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik
Accept ✔
This website uses technically necessary session cookies. By continuing to use the website, you agree to this. You can find our privacy policy here.