Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | Theory and Applications of Satisfiability Testing – SAT 2016 - 19th International Conference, Proceedings |
| Herausgeber/-innen | Daniel Le Berre, Nadia Creignou |
| Erscheinungsort | Cham |
| Seiten | 45-59 |
| Seitenumfang | 15 |
| ISBN (elektronisch) | 978-3-319-40970-2 |
| Publikationsstatus | Veröffentlicht - 2016 |
| Veranstaltung | 19th International Conference on Theory and Applications of Satisfiability Testing, SAT 2016 - Bordeaux, Frankreich Dauer: 5 Juli 2016 → 8 Juli 2016 |
Publikationsreihe
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Band | 9710 |
| ISSN (Print) | 0302-9743 |
| ISSN (elektronisch) | 1611-3349 |
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-Δ2, or in para-NP, depending on the target class. Acknowledgements. The first author gratefully acknowledges support by the Austrian Science Fund (FWF), Grant Y698. He is also affiliated with the Institute of Computer Science and Computational Science at University of Potsdam, Germany. The second and third author gratefully acknowledge support by the German Research Foundation (DFG), Grant ME 4279/1-1. The authors thank Jonni Virtema for pointing out Lemma 6 and Sebastian Ordyniak for discussions on Lemma 11. The authors acknowledge the helpful comments of the anonymous reviewers.
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
Theory and Applications of Satisfiability Testing – SAT 2016 - 19th International Conference, Proceedings. Hrsg. / Daniel Le Berre; Nadia Creignou. Cham, 2016. S. 45-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 9710).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review
}
TY - GEN
T1 - Strong Backdoors for Default Logic
AU - Fichte, Johannes Klaus
AU - Meier, Arne
AU - Schindler, Irina
N1 - Funding Information: The first author gratefully acknowledges support by the Austrian Science Fund (FWF), Grant Y698. He is also affiliated with the Institute of Computer Science and Computational Science at University of Potsdam, Germany. The second and third author gratefully acknowledge support by the German Research Foundation (DFG), Grant ME 4279/1-1. The authors thank Jonni Virtema for pointing out Lemma and Sebastian Ordyniak for discussions on Lemma . The authors acknowledge the helpful comments of the anonymous reviewers.
PY - 2016
Y1 - 2016
N2 - 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-Δ2, or in para-NP, depending on the target class. Acknowledgements. The first author gratefully acknowledges support by the Austrian Science Fund (FWF), Grant Y698. He is also affiliated with the Institute of Computer Science and Computational Science at University of Potsdam, Germany. The second and third author gratefully acknowledge support by the German Research Foundation (DFG), Grant ME 4279/1-1. The authors thank Jonni Virtema for pointing out Lemma 6 and Sebastian Ordyniak for discussions on Lemma 11. The authors acknowledge the helpful comments of the anonymous reviewers.
AB - 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-Δ2, or in para-NP, depending on the target class. Acknowledgements. The first author gratefully acknowledges support by the Austrian Science Fund (FWF), Grant Y698. He is also affiliated with the Institute of Computer Science and Computational Science at University of Potsdam, Germany. The second and third author gratefully acknowledge support by the German Research Foundation (DFG), Grant ME 4279/1-1. The authors thank Jonni Virtema for pointing out Lemma 6 and Sebastian Ordyniak for discussions on Lemma 11. The authors acknowledge the helpful comments of the anonymous reviewers.
UR - http://www.scopus.com/inward/record.url?scp=84977484703&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-40970-2_4
DO - 10.1007/978-3-319-40970-2_4
M3 - Conference contribution
SN - 9783319409696
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 45
EP - 59
BT - Theory and Applications of Satisfiability Testing – SAT 2016 - 19th International Conference, Proceedings
A2 - Le Berre, Daniel
A2 - Creignou, Nadia
CY - Cham
T2 - 19th International Conference on Theory and Applications of Satisfiability Testing, SAT 2016
Y2 - 5 July 2016 through 8 July 2016
ER -