Talks and Poster Presentations (with Proceedings-Entry):
J. Fichte, A. Meier, I. Schindler:
"Strong Backdoors for Default Logic";
Talk: Theory and Application of Satisfiability Testing -- SAT,
Bordeaux, France;
2016-07-05
- 2016-07-08; in: "Proceedings of SAT 2016: Theory and Applications of Satisfiability Testing - SAT 2016",
N. Creignou, D. Le Berre (ed.);
(2016),
ISBN: 978-3-319-40969-6;
45
- 59.
English abstract:
In this paper, we introduce a notion of backdoors to Reiter's propositional default logic and study structural properties of it. Also we consider the problems of backdoor detection (parameterised by the solution size) as well as backdoor evaluation (parameterised by the size of the given backdoor), for various kinds of target classes (cnf, horn, krom, monotone, positive-unit). We show that backdoor detection is fixed-parameter tractable for the considered target classes, and backdoor evaluation is either fixed-parameter tractable, in para-Delta P2, or in para-NP, depending on the target class.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-319-40970-2_4
Related Projects:
Project Head Stefan Woltran:
START
Created from the Publication Database of the Vienna University of Technology.