[Back]

J. Fichte, S. Szeider:
"Backdoor Trees for Answer Set Programming";
Talk: 14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2017), Espoo, Finland; 2017-07-03 - 2017-07-06; in: "Proceedings of the 10th Workshop on Answer Set Programming and Other Computing Paradigms co-located with the 14th International Conference on Logic Programming and Nonmonotonic Reasoning (ASPOCP@LPNMR'17", B. Bogaerts, A. Harrison (ed.); (2017), ISSN: 1613-0073; 1 - 16.

We translate the concept of backdoor trees from SAT to propositional Answer Set Programming (ASP). By means of backdoor trees we can reduce a reasoning task for a general ASP instance to reasoning tasks on several tractable ASP instances. We demonstrate that the number of tractable ASP instances can be drastically reduced in comparison to a related approach based on strong backdoors.

Backdoor;Trees; for; Answer; Set; Programming; LPNMR;