The good, the bad, and the odd: cycles in answer-set programs

DOI10.1007/978-3-642-31467-4_6zbMATH Open1372.68052arXiv1205.3663OpenAlexW1815595989MaRDI QIDQ5200464FDOQ5200464

Johannes K. Fichte

Publication date: 6 November 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Backdoors of answer-set programs are sets of atoms that represent clever reasoning shortcuts through the search space. Assignments to backdoor atoms reduce the given program to several programs that belong to a tractable target class. Previous research has considered target classes based on notions of acyclicity where various types of cycles (good and bad cycles) are excluded from graph representations of programs. We generalize the target classes by taking the parity of the number of negative edges on bad cycles into account and consider backdoors for such classes. We establish new hardness results and non-uniform polynomial-time tractability relative to directed or undirected cycles.

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

zbMATH Keywords

nonmonotonic reasoninganswer-set programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic programming (68N17)

Cited In (3)

• A multiparametric view on answer set programming
• Backdoors to Satisfaction
• Backdoors to tractable answer set programming

   Recommendations

• Backdoors to tractable answer set programming 👍 👎
• Strong Backdoors for Default Logic 👍 👎
• Backdoors to Normality for Disjunctive Logic Programs 👍 👎
• Backdoors to acyclic SAT 👍 👎
• Answer set solver backdoors 👍 👎

This page was built for publication: The good, the bad, and the odd: cycles in answer-set programs

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