Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
J. Fichte, A. Meier, I. Schindler:
"Strong Backdoors for Default Logic";
Vortrag: Theory and Application of Satisfiability Testing -- SAT,
Bordeaux, France;
05.07.2016
- 08.07.2016; in: "Proceedings of SAT 2016: Theory and Applications of Satisfiability Testing - SAT 2016",
N. Creignou, D. Le Berre (Hrg.);
(2016),
ISBN: 978-3-319-40969-6;
S. 45
- 59.
Kurzfassung englisch:
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.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-319-40970-2_4
Zugeordnete Projekte:
Projektleitung Stefan Woltran:
START
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.